Problem: A palindormic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009, which is 91 times 99 . Find the largest palindrome made from the product of two 3-digit numbers.

### Python Solution

There are a couple of ways to do this in Python (that I can think of) and I’m going to test some things out first, just to see which performs better. In the following block of code, I’ve written two functions. One checks if a number is a palindrome by reversing the digits arithmetically. The second function tests the same thing by casting the integer as a string and using a list slice to reverse the characters. Let’s see which one is faster.

import time   def is_palindrome1(num): reversed = 0 original = num   if num < 10: return True if num % 10 == 0: return False   while num >= 1: reversed = (reversed * 10) + (num % 10) num = num/10   if original == reversed: return True else: return False   def is_palindrome2(num): if str(num)==str(num)[::-1]: return True else: return False   start = time.time() for i in range(1000,1000000): a = is_palindrome1(i) elapsed = (time.time() - start)   print "first function took %s seconds" % elapsed   start = time.time() for i in range(1000,1000000): a = is_palindrome2(i) elapsed = (time.time() - start)   print "second function took %s seconds" % elapsed

Running this little block of code, which tests all numbers between 1,000 and 999,999, we get the following result.

first function took 3.07841110229 seconds second function took 1.60997390747 seconds

For the python solution, we’ll stick to the second function. When we attempt the Cython solution, we’ll come back and see which performs better again. For now, here’s a Python solution.

import time   def find_max_palindrome(min=100,max=999): max_palindrome = 0 for a in range(min,max + 1): for b in range(a + 1, max + 1): # avoid duplicates prod = a*b if prod > max_palindrome and str(prod)==(str(prod)[::-1]): max_palindrome = prod return max_palindrome   start = time.time() L = find_max_palindrome() elapsed = (time.time() - start)   print "%s found in %s seconds" % (L,elapsed)

There are a few things to notice here. First, I’m only concerned with the maximum palindrome, and so I don’t spend any time storing other palindromes once they are known to be non-maximum. Also, the if statement first checks if the given product is larger than the maximum known palindrome before using the string cast and list slice (which are more expensive) to check whether or not the number is even a palindrome. This should speed up our code a bit since the greater than comparison will often fail, regardless of whether the product in question is a palindrome. When we run this, we get the following.

906609 found in 0.134979963303 seconds

We could speed this up a tiny bit by writing our own iterators.

import time   def find_max_palindrome(min=100,max=999): max_palindrome = 0 a = 999 while a > 99: b = 999 while b >= a: prod = a*b if prod > max_palindrome and str(prod)==(str(prod)[::-1]): max_palindrome = prod b -= 1 a -= 1 return max_palindrome   start = time.time() L = find_max_palindrome() elapsed = (time.time() - start)   print "%s found in %s seconds" % (L,elapsed)

This gives us the following, which yields roughly 88% the runtime of the original.

906609 found in 0.119297981262 seconds

### Cython Solution

We’ll take our fastest Python solution and rewrite it in Cython. It looks like this.

%cython   import time   cdef find_max_palindrome(unsigned int min=100,unsigned int max=999): cdef unsigned int max_palindrome = 0 cdef unsigned int prod, b, a = 999 while a > 99: b = 999 while b >= a: prod = a*b if prod > max_palindrome and str(prod)==(str(prod)[::-1]): max_palindrome = prod b -= 1 a -= 1 return max_palindrome   start = time.time() L = find_max_palindrome() elapsed = (time.time() - start)   print "%s found in %s seconds" % (L,elapsed)

Executing that gives the following result.

906609 found in 0.00826597213745 seconds

Thus, the initial Cython version is roughly 14.43 times as fast as the Python version. But, here we’re using Python’s string casting and list slicing capabilities, whereas a compiled C code is probably going to be more efficient if we perform our arithmetic palindrome checking. Let’s see.

%cython   import time   cdef is_palindrome(unsigned int num): cdef unsigned int reversed = 0 cdef unsigned int original = num   if num < 10: return True if num % 10 == 0: return False   while num >= 1: reversed = (reversed * 10) + (num % 10) num = num/10   if original == reversed: return True else: return False   cdef find_max_palindrome(): cdef unsigned int max_palindrome = 0 cdef unsigned int a = 999 cdef unsigned int b = 999 cdef unsigned int prod   while a > 99: b = 999 while b >= a: prod = a*b if prod > max_palindrome and is_palindrome(prod): max_palindrome = prod b = b -1 a = a - 1   return max_palindrome   start = time.time() L = find_max_palindrome() elapsed = (time.time() - start)   print "%s found in %s seconds" % (L,elapsed)

Executing this, we obtain the following.

906609 found in 0.00146412849426 seconds

This is basically what I had expected: The arithmetic version is much faster in Cython. Now, our Cython code runs roughly 81.5 times as fast as our Python code.

### C Solution

Let’s see exactly how much faster we can make this in C. (I expect it to be significantly faster.)

#include <stdio.h> #include <stdlib.h> #include <time.h>   int is_palindrome(unsigned int num) { unsigned int reversed = 0; unsigned int original = num;   if (num < 10) return 1; if (num % 10 == 0) return 0;   while (num >= 1) { reversed = (reversed * 10) + (num % 10); num = num/10; }   if (original == reversed) return 1; else return 0; }   int main(int argc, char **argv) { float ratio = 1./CLOCKS_PER_SEC; clock_t t1 = clock(); unsigned int max_palindrome = 0; unsigned int a, b, prod;   unsigned long int c = 10000;   while (c > 0) { a = 999; while (a > 99) { b = 999; while (b >= a) { prod = a*b; if (prod > max_palindrome && is_palindrome(prod)) { max_palindrome = prod; } b--; } a--; } c--; }   clock_t t2 = clock(); printf("%d found in %f seconds for 10,000 iterations\n", max_palindrome, \ ratio*(long)t1+ratio*(long)t2);   return 0; }

Notice that we’re going to attempt 10,000 iterations here. When executed, after compiling in GCC with a “-O3″ optimization flag, we get the following.

906609 found in 3.740000 seconds for 10,000 iterations

So, each iteration is running in about 0.000374 seconds. This means that the C code is roughly 3.903 times as fast as the Cython and 319 times as fast as the Python.