[Tutor] Fwd: Re: largest palindrome number
Chris Fuller
cfuller084 at thinkingplanet.net
Tue Aug 30 21:37:37 CEST 2011
I played around with this puzzle a bit. I made a palindrome function a bit
like Bob's, only i iterated through the string (stopping at the first mismatch)
instead of doing the whole thing at once.
The rest of the code is even more amenable to speedups. The first thing I saw
was the outer "i" loop can start at 100, rather than one. I also saw that
using PNum = max(palindrome(i*j), PNum) would replace a half dozen lines in
the first try. But I discarded this approach. I figured it would be much
faster to work backwards from 999*999, stopping at the first palindrome that
was the product of two three digit numbers.
This code is quite terse, and uses some advanced features (generator
functions, shortcutting), but I'll try to explain it.
n = 999*999
while True:
if palindrome(n) and \
any( (100<=i<1000 and 100<=n/i<1000 for i in \
(j for j in range(1,1+int(n**.5)) if n%j==0))):
break
else:
n -= 1
print n
The inner "j" loop simply finds factors of n (n**.5 is the square root of n);
the outer loop checks to see if the factor and its complementary factor are
three digit numbers. The generator expressions (like list comprehensions, but
bounded by parentheses) only calculate one true/false check on a single factor
at a time. The any() built-in function returns as soon as it encounters are
true value, so a lot of computation is avoided versus checking all the factors
and their three-digit status.
A note on the "if palindrome(n) and \" line. Python (and C. and most
languages) will stop computing through and and statement if the first
expression is false, and likewise for an or statement if the first statement is
true. This is the same way any() and all() work, only these functions can
operate on iterators of arbitrary length. So by putting the less
computationally intensive palindrome check first, a few more cpu cycles are
saved.
I got around an order of magnitude speedup with this code.
Cheers
More information about the Tutor
mailing list