Fastest algorithm to find the largest palindrome that is the product of 2 numbers with the same number of digits

  1. It gets faster if you fix that x>=y, so 99*91 and 91*99 will not be tested and found separately
  2. When a palindrome is found, the inner loop can exit (as it is counting downwards, all palindromes it may find for the same x are certainly smaller than the "current" one)
  3. If the current product is smaller than the current maximum, the inner loop can also exit
  4. If x*x is smaller than the current maximum, the outer loop can exit too

def palindrome(maxInt):
    maxpal=0
    for x in range(maxInt,0,-1):
        if x*x<maxpal:                         # 4.
            break
        for y in range(x,0,-1):                # 1.
            num=x*y
            if num<maxpal:                     # 3.
                break
            if str(num) == str(num)[::-1]:
                maxpal=num
                break                          # 2.
    return maxpal

(Of course 3. could be in the range, for y in range(x,maxpal//x,-1): perhaps)

  1. Strictly said, it should only check y-s having the same number of digits as x, which was not addressed yet, but ** and a downwards-rounded log10() can do that after all.

My current complete code:

import math,time

def palindrome(maxInt):
    maxpal=0
    for x in range(maxInt,0,-1):
        if x*x<maxpal:                                                     # 4.
            break
        for y in range(x,max(maxpal//x,10**int(math.log10(x))-1),-1):      # 1. 3. 5.
            num=x*y
            if str(num) == str(num)[::-1]:
                maxpal=num
                break                                                      # 2.
    return maxpal

start=time.time()
print(palindrome(9))
print(palindrome(99))
print(palindrome(999))
print(palindrome(9999))
print(palindrome(99999))
print(palindrome(999999))
print("%d seconds" % (time.time()-start))

Example output:

9
9009
906609
99000099
9966006699
999000000999
0.731034 seconds