Largest Palindrome Product - Project Euler #4

Question

This is my code for Project Euler Problem #4

The question:

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.

My code:

function problem4(){ let product = 1; let largest = 1; for(let i = 100; i<1000; i++){ for(let j = i; j<1000; j++){ product = i*j; if(("" + product) == ("" + product).split("").reverse().join("")){ largest = Math.max(largest, product);} } } return largest; } console.log(problem4());

At present, it takes 311.5649999999732 ms for execution, but I think it can be better. So how can I make it more efficient and faster?

Answer 1

How about this small modification that could potentially make it faster if the answer is large enough.

function problem4(){ let product = 1; let largest = 1; for(let i = 999; i>=100; i--){ for(let j = 999; j>=i && i*j>largest; j--){ product = i*j; if(("" + product) == ("" + product).split("").reverse().join("")){ largest = Math.max(largest, product);} } } return largest; } console.log(problem4()); 

Answer 2

Smarter brute force

You have two major slow points.

1. You are checking numbers from the smallest towards the largest. That means that you can not use any found palindromes to help you avoid calculations. Ie there is no need to check if a product is a palindrome if it is smaller than the current biggest found.

2. The method you use to check if a number is a palindrome is slow. Using a faster numerical test will provide a significant performance increase.

A better palindrome checker

The following function is on average 3 times faster than the method you use. Simply using it in your could would reduce the time from 311ms down to near 100ms.

function isPalindrome(num) { var top = Math.pow(10, Math.log10(num) | 0), bot = 1; while (top >= bot) { if ((num / top % 10 | 0) !== (num / bot % 10 | 0)) { return false } top /= 10; bot *= 10; } return true; } 

Pick the low hanging fruit

The palindrome that you are after is most likely near the high numbers.

Using iterators that count from 1000 down we can avoid checking products if they are lower than any found max.

We also know that because we are counting down, each iterator will only be stepping over smaller products. Using this we can break from the inner or outer iterator as soon as we find a product that is smaller than the max found palindrome.

Example

The following solution is still a brute force method.

It finds the palindrome in 1.3ms, iterating over 5267 products, checking 5224 of them for palindromes.

Compared to your function that iterated over 405,450 products and checked each for palindromes. Little wonder it took nearly one third of a second to do.

function problem(){ const minNum = 100, range = 899; const isPalindrome = num => { var top = Math.pow(10, Math.log10(num) | 0), bot = 1; while (top >= bot) { if ((num / top % 10 | 0) !== (num / bot % 10 | 0)) { return false } top /= 10; bot *= 10; } return true; } var i = range, max = minNum * minNum, j, iVal; while (i--) { iVal = i + minNum; j = i + 1; if (iVal * (j - 1 + minNum) < max) { break } while (j--) { const product = iVal * (j + minNum); if (product <= max) { break } if (isPalindrome(product)) { max = Math.max(max, product) } } } return max; } 

Under 1ms

The above function is still slow. 1.3ms is forever in computer time. I have a feeling this can get down to about 0.6ms. I checked to see how many of the 5267 products iterated over were smaller than the max palindrome.

3088 (58%) checked products were smaller than the result. It is likely a different pattern of iteration steps can avoid many of these.

Answer 3

It is worth pointing out that if you are trying to improve the performance of your code, you can focus your code on exactly the problem you want to solve.

Standardize your timing

If I told you a function ran in 400 ms on my machine would you prefer it over your 311 ms version? What if my machine is an OOOOOOLD 32-bit laptop?

Always provide a timing framework. That way I can check the performance of my code versus your code, using your framework. I've included one below based on the performance module.

Focus on the problem

You aren't looking for "any palindrome" or "any number that is a palindrome." You are looking for "any number that is the product of two 3-digit numbers which is a palindrome." Take advantage of that!

You know that the smallest 3-digit number is 100, and the largest is 999. So the smallest product will be 10,000 and the largest product will be <1,000,000. Thus, the palindrome in question is either a 5-digit number or a 6-digit number. Write your code to that specification:

const is_palindrome = num => { if (num >= 100000) { let t0 = num % 10; let t5 = num / 100000 | 0; if (t5 != t0) return false; let t1 = num / 10 % 10 | 0; let t4 = num / 10000 % 10 | 0; if (t4 != t1) return false; let t2 = num / 100 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t2) return false; } else { let t0 = num % 10; let t4 = num / 10000 | 0; if (t4 != t0) return false; let t1 = num / 10 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t1) return false; } return true; } 

Be lazy

As Jorge F. points out, you are looking for the largest palindromic number. So why start at the small end of the range? For some product X * Y, you know that if Y1 > Y2, then X * Y1 > X * Y2. So always try the higher number first! And if you find a palindrome, then you're done with all the other Y2's that might be smaller than your Y1, so move on to the next X.

for (var x = 999; x >= 100; --x) for (var y = 999; y >= x; --y) { 

Laziness: fail early

Also as Jorge shows, you can quit if the product ever gets smaller than your present largest value:

for (var x = 999; x >= 100; --x) { if (x * 999 <= largest) break; for (var y = 999; y >= x; --y) { if (x * y <= largest) break; 

Explore the optimizer!

Finally, one thing worth considering is that you don't really know how the particular optimizer your javascript engine is running will work. So it's worth trying to manually perform some improvements to see if it helps. One improvement you could perform is to notice that you are always multiplying by one less number:

x * 999 x * 998 x * 997 

Which is really just the same as subtracting x from the previous result:

product = x * 999 product -= x product -= x 

Why not make that your inner loop and see if performance improves? FWIW, on my machine, it made a small difference (sometimes -2, sometimes -1 from _jf version). I'm not sure if that's real, or just a result of getting things into the cache. Let me know what your timings look like.

Results: Function OK? Timing(ms) Eagle Y 2095 Jorge Fernández Y 17 Blindman67 Y 10 aghast_bm Y 5 aghast_jf Y 4 aghast_nomult Y 2 

function profile(name, fn) { let t0 = performance.now(); let result = fn(); // Run some more, for more timing! fn(); fn(); fn(); let t1 = performance.now(); return [name, result, (t1-t0)]; } function p4_eagle(){ let product = 1; let largest = 1; for(let i = 100; i<1000; i++){ for(let j = i; j<1000; j++){ product = i*j; if(("" + product) == ("" + product).split("").reverse().join("")){ largest = Math.max(largest, product);} } } return largest; } function p4_jorge_fernandez(){ let product = 1; let largest = 1; for(let i = 999; i>=100; i--){ for(let j = 999; j>=i && i*j>largest; j--){ product = i*j; if(("" + product) == ("" + product).split("").reverse().join("")){ largest = Math.max(largest, product);} } } return largest; } function p4_blindman67(){ const minNum = 100, range = 899; const isPalindrome = num => { var top = Math.pow(10, Math.log10(num) | 0), bot = 1; while (top >= bot) { if ((num / top % 10 | 0) !== (num / bot % 10 | 0)) { return false } top /= 10; bot *= 10; } return true; } var i = range, max = minNum * minNum, j, iVal; while (i--) { iVal = i + minNum; j = i + 1; if (iVal * (j - 1 + minNum) < max) { break } while (j--) { const product = iVal * (j + minNum); if (product <= max) { break } if (isPalindrome(product)) { max = Math.max(max, product) } } } return max; } function p4_aghast_bm(){ const is_palindrome = num => { if (num >= 100000) { let t0 = num % 10; let t5 = num / 100000 | 0; if (t5 != t0) return false; let t1 = num / 10 % 10 | 0; let t4 = num / 10000 % 10 | 0; if (t4 != t1) return false; let t2 = num / 100 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t2) return false; } else { let t0 = num % 10; let t4 = num / 10000 | 0; if (t4 != t0) return false; let t1 = num / 10 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t1) return false; } return true; } const minNum = 100, range = 899; var i = range, max = minNum * minNum, j, iVal; while (i--) { iVal = i + minNum; j = i + 1; if (iVal * (j - 1 + minNum) < max) { break } while (j--) { const product = iVal * (j + minNum); if (product <= max) { break } if (is_palindrome(product)) { max = Math.max(max, product) } } } return max; } function p4_aghast_jf(){ const is_palindrome = num => { if (num >= 100000) { let t0 = num % 10; let t5 = num / 100000 | 0; if (t5 != t0) return false; let t1 = num / 10 % 10 | 0; let t4 = num / 10000 % 10 | 0; if (t4 != t1) return false; let t2 = num / 100 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t2) return false; } else { let t0 = num % 10; let t4 = num / 10000 | 0; if (t4 != t0) return false; let t1 = num / 10 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t1) return false; } return true; } let product = 1; let largest = 1; for(let i = 999; i>=100; i--){ for(let j = 999; j>=i && i*j>largest; j--){ product = i*j; if (is_palindrome(product)) { largest = Math.max(largest, product); } } } return largest; } function p4_aghast_nomult(){ const is_palindrome = num => { if (num >= 100000) { let t0 = num % 10; let t5 = num / 100000 | 0; if (t5 != t0) return false; let t1 = num / 10 % 10 | 0; let t4 = num / 10000 % 10 | 0; if (t4 != t1) return false; let t2 = num / 100 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t2) return false; } else { let t0 = num % 10; let t4 = num / 10000 | 0; if (t4 != t0) return false; let t1 = num / 10 % 10 | 0; let t3 = num / 1000 % 10 | 0; if (t3 != t1) return false; } return true; } let largest = 1; for (let i = 999; i >= 100; --i) { if (i * 999 <= largest) break; for (let product = i * 999; product >= i * i; product -= i) { if (product <= largest) break; if (is_palindrome(product)) { largest = product; break; } } } return largest; } //////////////////////////////////////////////////////////// var details = [ ['Eagle', p4_eagle], ['Jorge Fernández', p4_jorge_fernandez], ['Blindman67', p4_blindman67], ['aghast_bm', p4_aghast_bm], ['aghast_jf', p4_aghast_jf], ['aghast_nomult', p4_aghast_nomult], ]; var results = []; for (deets of details) { let [name, fn] = deets; results.push(profile(name, fn)); } let correct = results[0][1]; const tab = "\t"; const pad = " ".repeat(20); var msg = "Results:\n" + ("Function" + pad).slice(0, 20) + "OK?" + tab + "Timing(ms)\n"; for (res of results) { let [name, answer, time] = res; msg += (name + pad).slice(0, 20) + (correct == answer ? "Y" : "No!") + tab + time + "\n"; } //alert(msg); console.log(msg);

Answer 4

In general, prefer to use the narrowest possible scope for variables. Old-school JavaScript is an exception for technical reasons to do with its scope rules being rather unusual and catching out people who were used to other languages: let was introduced to address that problem.

In short, product should be declared inside the loop over j.

Also, given the way it's used, it makes reasonable sense for it to be "" + i*j so that the conversion from number to string is only done once.

---

 if(("" + product) == ("" + product).split("").reverse().join("")){ largest = Math.max(largest, product);} } } 

What happened to the whitespace there?

---

So how can I make it more efficient and faster?

Often the key to making something much faster is to use a completely different approach.

The challenge requires you to

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

but it doesn't tell you how to do that.

One approach is to look at products of 3-digit numbers, filter to palindromes, and find the largest product which passes the filter. This is the approach you've taken, and the one taken by all of the answers so far.

Another approach is to look at 6-digit palindromes in reverse order and filter to products of 3-digit numbers:

for (let d50 = 900009; d50 > 0; d50 -= 100001) { for (let d41 = 90090; d41 >= 0; d41 -= 10010) { for (let d32 = 9900; d32 >= 0; d32 -= 1100) { let palindrome = d50 + d41 + d32; for (let x = Math.ceil(palindrome / 999); x < 1000 && x * x <= palindrome; x++) { if (palindrome % x === 0) { return palindrome; } } } } } 

In my benchmarking this is twice as fast as the fastest proposal so far in this thread, and I haven't even micro-optimised it. (To do that: replace x * x with x2, initialised to x * x and then updated as x2 += 2*x + 1).