Archive for December, 2009

Problem 4 ver. 4: optimization

December 18th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

Find the largest palindrome made from the product of two 3-digit numbers.

And the last scratch for now. It is possible to prove that 11 divides a palindromic number. Indeed,

N = \sum_{i=0}^k (10^{2k-i+1} d_i + 10^i d_i) = \sum 10^i d_i (10^{2(k-i)+1} + 1) = \sum 10^i d_i m_i

and here m_i is a multiple of 11 (divisibility by 11 criterion).

The factor 11 can belong to a - and in this case we step just 1 in b. But if 11 doesn't divide a, then we can increase b by 11 each time.

  1.         (define (find-largest-palindrome-using-11 k)
  2.            (let ([m (- (^ 10 k) 1)] [m/10 (^ 10 (- k 1))])
  3.              (let ([m-11 (* 11 (div m 11))])
  4.                (define (iter a b largest-palindrome)
  5.                  (if (< a m/10) largest-palindrome
  6.                      (let ([step (if (= 0 (mod a 11)) 1 11)]
  7.                            [next-a-11? (= 0 (mod (- a 1) 11))])
  8.                        (if (< b m/10) (iter (- a 1) (if next-a-11? m m-11) largest-palindrome)
  9.                            (let ([n (* a b)])
  10.                              (if (<= n largest-palindrome) (iter (- a 1) m largest-palindrome)
  11.                                  (if (palindrome-number? n) (iter (- a 1) m n)
  12.                                      (iter a (- b step) largest-palindrome))))))))
  13.                (iter m m 0))))

This speeds up the previous result around ten times, leaving an asymptotic behavior the same. The memory use is the same O(1).

Let's look at results:
k = 2 => N = 9009
k = 3 => N = 906609
k = 4 => N = 99000099
k = 5 => N = 9966006699
k = 6 => N = 999000000999
k = 7 => N = 99956644665999
k = 8 => N = 9999000000009999
...
We could improve our algo drastically, if proven that the sought-for palindrome is less or equal n - \sqrt n (and mirrored). I have the feeling that for even k it is equal. But I don't know how to prove it. (I calculated for k = 10 and this does not hold, N = 99999834000043899999).

Problem 4 ver. 3: optimization

December 17th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

Find the largest palindrome made from the product of two 3-digit numbers.

An author, however, advises a simpler approach. As we are looking for a palindrome a*b, let's iterate a and b in a top-down direction. After finding some palindrome, impose it as a top boundary for palindromes, that is, iterating in the inner loop for b, we stop when a*b cannot be large than that anymore. If we found a new palindrome, it will replace the boundary. Stop condition is finishing the outer loop in a, i.e. when it drops to 2-digits number (k-1, generally speaking).

  1.         (define (find-largest-palindrome-with-cutoffs k)
  2.            (let ([m (- (^ 10 k) 1)] [m/10 (^ 10 (- k 1))])
  3.              (define (iter a b largest-palindrome)
  4.                (if (< a m/10) largest-palindrome
  5.                    (if (< b m/10) (iter (- a 1) m largest-palindrome)
  6.                        (let ([n (* a b)])
  7.                          (if (<= n largest-palindrome) (iter (- a 1) m largest-palindrome)
  8.                              (if (palindrome-number? n) (iter (- a 1) m n)
  9.                                  (iter a (- b 1) largest-palindrome)))))))
  10.              (iter m m 0)))

Complexity in memory now is just O(1). Performance complexity by my impression is better than in the previous variant. The outer loop has n - n/10 steps, so it cannot be less than O(n). Assuming that a desired palindrome (left half of it, actually) lies close to n - \sqrt n (which should be proved, strictly speaking), we make no more than n \cdot \sqrt n = n^{3/2} operations until find it, and no more than the same n^{3/2} afterwards.

This is the worst case, however, and I hope that we find some worse-than-ideal palindrome quick enough. Suppose, we can use the estimate n - \sqrt n ab origin, i.e. the inequality f \cdot g < \sqrt n \cdot \sqrt n = n holds, where f = n - a, g = n - b. Then we can calculate an estimate of operations as area under a curve y = n / x:

\int_1^n \frac n x dx = n \cdot \ln n

So, the actual algo performance is between O(n \ln n) and O(n^\frac 3 2).