Project Euler #4: palindromic number

Question

The problem statement for Project Euler Problem 4 is as follows:

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.

I'm looking to make this code more efficient, especially the while loop. I'm using a variable to pass into the function so that the answer to ints of various lengths can be determined. It's been the most efficient that I've been able to come up with. Any suggestions?

def largestPalindromeProduct(digits):
 num=int(digits*"9")
 maxPalindrome=0
 i=int(num)
 floor=int(num/10) if digits > 1 else -1
 while i > floor:
 j=i
 while j > floor:
 val=str(i*j)
 if val==val[::-1]:
 floor=j
 maxPalindrome=max(maxPalindrome,i*j)
 j-=1
 i-=1
 return maxPalindrome
print(largestPalindromeProduct(3))

Answer 1

@toolic has suggested studying other postings on this site (to see algorithms developed by others.)

---

Vestigial obscuration

Tell your rubber duck about the past and present utility of the variables num and i.

The drive to get the code to work can lead to stale fragments or statements that can be merely perplexing when examined days later.

Human appendix vagaries, however, make one aware that these things are better out than in.

---

Blind spot

The inner loop decrements j, then re-computes a product with i (which is also slowly decrementing.)

Consider:
97 * 5 =わ 97 +たす 97 +たす 97 +たす 97 +たす 97 and
97 * 4 =わ 97 +たす 97 +たす 97 +たす 97 and
97 * 3 = 97 + 97 + 97 and
...
The latter sequence of values could be computed by simply repeatedly subtracting the 'outer loop value' (in this case, i) from a product computed once before the inner loop starts.

One source suggests multiply operations can require 3 to 5 times more time to complete than simple add or subtract.

While it is likely insignificant in this instance, finding how to shave 10ns off a computation to run on an "exa-Flop" supercomputer may be worthy of a paper in a prestigious journal. Today's AI developments require squillions of calculations be performed.

---

Doing the hard yards

More significant is converting every candidate value to a string for testing as a palindrome.
Converting base 2 values to base 10 does not come cheaply. The typical repeated divide and modulo operations of binary to base-10 conversion can consume a lot of execution time!

If processing speed is desirable, and the algorithm is the best one can write, coding a purpose-built function to quickly check/reject values might be warranted. (eg: Would it be reasonable if, after isolating the 'units' digit that turned out to be 0, a palindromic 6 digit value had been formed? If not, why continue to dissect the rest of the base-10 digits?)

Determining and comparing the digits in pairs (1:6, 2:5, 3:4) would frequently allow early detection of a non-palindromic value saving processing cycles that are destined to be worthless.

Strings are a few of my favourite things... But they aren't the optimal tool for every circumstance.

---

Will str() always work?

Let's step into an alternate reality in which the challenge is to list ALL palindromic numbers that are the product of two "3 digit" numbers.

In many realms, '0' is used as a "lead digit" in what are commonly referred to as "numbers". (My cellphone number begins "0427...". James Bond's employee ID is "007".)

The obvious way for a program to generate candidate values (products) to sieve for "palindromes" is with binary multiplication.

If we accept that "099" and "100" represent two 3 digit numbers, their decimal product is 9900 which str() would return as "9900".

Perhaps the more correct version (in the realm of the problem) would be "009900" which is decidedly a six digit palindrome.

To be on the safe side, the OP's string-ification should probably be

// val=str(i*j)
 val=f"{i*j:06}" # Want six digits, even if leading zeros

---

Harrumph...

Even though the relevant function is quite short, I believe it is generally considered bad practice to alter the 'target boundary' of a loop within the body of that same loop. The casual reader makes assumptions about the amount of processing required, perhaps without recognising that the goal post is being shifted.

Appropriate break statements would be self-documenting code; or, minimally, a comment should be present highlighting this aberration and would preclude incorrect assumptions being made.

---

Tweaking...

Thinking about this section

 while j > floor:
 val=str(i*j) # <<<<<
 if val==val[::-1]: # <<<<<
 ...

Consider the machine cycles consumed by the two marked steps. As discussed, converting a binary value to a string of digits is not free. As well, the seeming check for the string being palindromic will involve some amount of looping and branching.

Homework: Explain the (minor) advantage of the following alteration

 while j > floor and i*j > maxPalindrome:

Tempted by the prospect of stepping over some iterations, one begins to see the complexities that result from other lines of code that may change the loops' finish line on-the-fly...

• Fe2O3: Final comment: "efficiency", although virtuous, is not really a valid consideration in this particular exercise. There's no utility to this code other than determining one (unchanging) answer. Once determined, the code could be thrown away. For fun, however, it might be worth investigating "Double Dabble" conversion of binary to decimal (BCD) for determination of a candidate's palindrome-isity... Lots of simple bitwise operations instead of built-in division and modulo juggernauts.

Answer 2

Fast

I'm looking to make this code more efficient.

The good news is that it already runs very quickly.

Flexible

It is great that you created a function which takes an input parameter to easily allow you to run and test the 2 in the Euler problem statement, as well as other values. For example, I easily added these calls:

print(largestPalindromeProduct(2))
print(largestPalindromeProduct(4))

Documentation

The PEP 8 style guide recommends adding a docstring for the function. This would include:

• The description of the Euler problem
• A description of the digits input, such as what range of values are valid
• What type of value is returned (an integer)

Layout

Indentation is great, but it would be nicer to have consistent spacing around operators.
The black program can be used to automatically format the code.

Simpler

There is no need to call int in the following line because you already assured num is an int. Change:

i=int(num)

to:

i = num

Naming

PEP-8 also recommends snake_case for variable and function names.

• largestPalindromeProduct would be largest_palindrome_product
• maxPalindrome would be max_palindrome

Comment

This line could benefit from a comment:

 if val==val[::-1]:

such as:

 if val == val[::-1]: # check if string is a palindrome

DRY

The expression i*j appears twice. You could assign it to a variable and give the variable a meaningful name like:

product = i * j

That could possibly speed things up by a small amount.

val is not a very descriptive name. Perhaps:

product = i * j
product_string = str(product)

Algorithm

As far as the algorithm goes, you could refer to other Python Euler Problem #4 questions

Answer 3

A small suggestion not covered by toolic's otherwise fantastic answer.

 floor=int(num/10) if digits > 1 else -1

int(num/10) is equivalent (assuming Python 3) to using the // integer division operator with num // 10:

 floor = num // 10 if digits > 1 else -1