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.


Comments are closed