Project Euler #4 "Largest Palindrome product" in Python

Question

Given

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

Solution

import time

def reverse(num):
    dreverse = 0
    while (num > 0):
        dreverse = dreverse * 10 + num % 10
        num /= 10
    return dreverse

def is_palindrome(num):
    if (num < 0):
        raise ValueError('Non-negative integers only')
    return num == reverse(num)

def main():
    largest_palindrome = 0
    lower = 999
    while lower >= 100:
        upper = 999
        while upper >= lower:
            if upper * lower <= largest_palindrome:
                break
            if is_palindrome(upper * lower):
                largest_palindrome = upper * lower
            upper -= 1
        lower -= 1
    return largest_palindrome

start_time = time.time()
print main()
print("--- %s seconds ---" % (time.time() - start_time))
o/p: 906609
--- 0.0150721073151 seconds ---     

I am including timing metric from now on. This solution seems \$O(N^2)\$. Can I improve it further?

Answer 1

You are recomputing the product upper * lower three times:

    while upper >= lower:
        if upper * lower <= largest_palindrome:
            break
        if is_palindrome(upper * lower):
            largest_palindrome = upper * lower

You should save it in a variable:

    while upper >= lower:
        product = upper*lower
        if product <= largest_palindrome:
            break
        if is_palindrome(product):
            largest_palindrome = product

Also, how about this version of is_palindrome:

def is_palindrome(n):
  s = str(n)
  return (s == s[::-1])

Update

Replace your loops with for and xrange:

largest = 0
for lower in xrange(999,99,-1):
    for upper in xrange(999,lower-1,-1):
        ...

It makes the intent of your code a lot clearer, and it is easier to correctly write the loop.

(The following is note quite right)

Finally, if upper*lower <= largest_palindrome, you actually return from the function:

        if upper * lower <= largest_palindrome:
            return largest_palindrome

The return will essentially break out of both while loops. Using just break will only break out of the inner loop. Of course, the remaining cases will execute very quickly since they will only last one iteration of the inner loop, but it is still a good optimization to know about.

Answer 2

I am going to suggest a solution that is 20x less perfomant than yours, because Python was really made to optimize programmer's time, not execution time. It should be noted that my solution is still under a second of execution time.

---

def is_palindrome(string):
    return string == ''.join(reversed(string))

A number is just a kind of string, so I wrote a more general (and, yes, slower) function to check for palindromes. The number should be converted to string before being passed in to the function.

The main body of this program is really close to natural langauge, it is just:

print(max(i * j for i in range(500, 999) for j in range(500, 999) 
                if is_palindrome(i * j)))

it uses a generator expression, so the usage of memory is O(1) and the time complexity is O(N^2) as in your solution.

Almost all the time is spent in the is_palindrome function, using your function would make this as fast as your solution.