Possible optimizations for Project Euler #4 algorithm

Question

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

Even though the algorithm is fast enough for the problem at hand, I'd like to know if I missed any obvious optimizations.

from __future__ import division
from math import sqrt

def createPalindrome(m):
    m = str(m) + str(m)[::-1]
    return int(m)

def problem4():
    for x in xrange(999,99,-1):
        a = createPalindrome(x)
        for i in xrange(999,int(sqrt(a)),-1):
            j = a/i
            if (j < 1000) and (j % 1 == 0):
                c = int(i * j)
                return c

Answer 1

Look here for Ideas

In C++ I do it like this:

int euler004()
    {
    // 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.
    const int N=3;
    const int N2=N<<1;
    int min,max,a,b,c,i,j,s[N2],aa=0,bb=0,cc=0;
    for (min=1,a=1;a<N;a++) min*=10; max=(min*10)-1;
    i=-1;
    for (a=max;a>=min;a--)
     for (b=a;b>=min;b--)
        {
        c=a*b; if (c<cc) continue;
        for (j=c,i=0;i<N2;i++) { s[i]=j%10; j/=10; }
        for (i=0,j=N2-1;i<j;i++,j--)
         if (s[i]!=s[j]) { i=-1; break; }
        if (i>=0) { aa=a; bb=b; cc=c; }
        }
    return cc; // cc is the output
    }

• no need for sqrt ...
• the subcall to createPalindrome can slow things down due to heap/stack trashing
• string manipulation m = str(m) + str(m)[::-1] is slow
• string to int conversion can be faster if you do it your self on fixed size array
• mine implementation runs around 1.7ms but big portion of that time is the App output and formating (AMD 3.2GHz 32bit app on W7 x64)...

[edit1] implementing your formula

int euler004()
    {
    int i,c,cc,c0,a,b;
    for (cc=0,i=999,c0=1100*i;i>=100;i--,c0-=1100)
        {
        c=c0-(990*int(i/10))-(99*int(i/100));
        for(a=999;a>=300;a--)
         if (c%a==0)
            {
            b=c/a;
            if ((b>=100)&&(b<1000)) { cc=c; i=0; break; }
            }
        }
    return cc;
    }

• this takes ~0.4 ms

[edit2] further optimizations

//---------------------------------------------------------------------------
int euler004()
    {
    // 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.
    int i0,i1,i2,c0,c1,c,cc=0,a,b,da;
    for (c0=  900009,i0=9;i0>=1;i0--,c0-=100001)    // first digit must be non zero so <1,9>
    for (c1=c0+90090,i1=9;i1>=0;i1--,c1-= 10010)    // all the rest <0,9>
    for (c =c1+ 9900,i2=9;i2>=0;i2--,c -=  1100)    // c is palindrome from 999999 to 100001
     for(a=999;a>=948;a-- )
      if (c%a==0)
        {
        // biggest palindrome is starting with 9
        // so smallest valid result is 900009
        // it is odd and sqrt(900009)=948 so test in range <948,999>
        b=c/a;
        if ((b>=100)&&(b<1000)) { cc=c; i0=0; i1=0; i2=0; break; }
        }
    return cc;
    }
//---------------------------------------------------------------------------

• this is too fast for me to properly measure the time (raw time is around 0.037 ms)
• removed the divisions and multiplications from palindrome generation
• changed the ranges after some numeric analysis and thinking while waiting for bus
• the first loop can be eliminated (result starts with 9)