Archive for November, 2009

Problem 4 ver. 2: optimization

November 29th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

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

Last time we had a straightforward algo with O(n^2) complexity and at least O(n) memory use. Now let's enhance that. Instead of iterating over multipliers it's reasonable to iterate over palindromes, starting from the largest. I.e. over sequence 999999, 998899, 997799, and so on.

Remark. The largest product of two 3-digit numbers is 999 * 999 = 998001. So, in principle, we could start from the palindrome 997799. But this saves just 2 iterations.

Having a palindrome m, we factorize it and look at all the subsets of the factorization. Assume, we have one subset already. Let's name the product of those factors as p. If this number p has k digits (k = 3 for now) and the number m/p has k digits, than we found the palindrome, which is a product of two k-digit numbers.

In Scheme that will be written as:

  1.         (define (find-largest-palindrome-via-factorization k)
  2.            (define (correct-length? m) (= (length (digits m)) k))
  3.            (define (iter l) (let* ([n (make-number-from-digits (append (reverse l) l))]
  4.                                    [factors (map mul-list (subsets (factorize n minimal-factor-sqrt-complexity)))]
  5.                                    [factors (filter correct-length? factors)]
  6.                                    [factors (filter (lambda (m) (correct-length? (/ n m))) factors)])
  7.                               (if (null? factors) (iter (digits (- (make-number-from-digits l) 1))) n)))
  8.            ;(display (list n '= (car factors) '* (/ n (car factors)))))))
  9.            (iter (one-number-multiple-times 9 k)))

Here I used a few new util functions:

  1.         (define (make-number-from-radix list k)
  2.            (define (iter l f) (if (null? l) 0 (+ (* (car l) f) (iter (cdr l) (* f k)))))
  3.            (iter list 1))
  4.          (define (make-number-from-digits list) (make-number-from-radix list 10))

which make numbers out of their base-k representation.

Complexity now is hard to calculate. The worst case scenario gives quite a bad upper boundary. However, the worst case will never be realized.

Looking at what it gives out (9009, 906609, 99000099, 9966006699, 999000000999, ...), I could guess that the required palindrome is found after roughly \sqrt n iterations. So, in total I hope for less than O(n^2) complexity.

The memory use depends on factorizations - we store one whenever a palindrome is taken and lose it when proceed with the next palindrome.