Project Euler #4 - finding the largest palindrome from the product of two n-digit numbers

Question

Project Euler Problem #4: "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."

The code works well enough until trying to find the largest palindrome of two eight digit numbers. I found a similar question in C++, but there are some differences:

1. The main function takes two integers to determine the number of digits of the factors used to produce the products. This allows us to find the largest palindrome for a two digit number and a five digit number or two eight digit numbers.
2. Two for loops then create the multiplicand and multiplier. I think this could be done better.
3. The outer for loop iterates over the multiplicand to decrement it each time the inner for loop has completed.
4. The inner for loop iterates over the multiplier so that inside this loop every possible product from the multiplicand and multiplier are evaluated. This is where I think the largest gains from optimization will come from. I don't think that every product needs to be produced or evaluated to find the largest palindrome nor do I think it requires an inner/outer loop to do so.
5. The product is then turned into a string so that the first and last values can be compared for equality.
6. If they are equal the comparison repeats again after removing the compared values until three or less values are left where the first and last values are equal.
7. The product is then stored as the largest result if it is greater than the previous result.
8. Finally, the result is returned after all the loops have finished.

I am interested in finding ways to optimize this code.

console.log(largestPalindromeOfTwoFactors(8, 8));
function largestPalindromeOfTwoFactors(multiplicand, multiplier{//Accepts the number of digits of the multipland and the number of digits of         the multiplier
        var  multiplicandString = "";
        var multiplierString = "";
    for(var i = 0; i < multiplicand; i++){
         multiplicandString = multiplicandString.concat(""+9); // 9, 99, 999
    }
    for(var j = 0; j < multiplier; j++){
         multiplierString = multiplierString.concat(""+9); // 9, 99, 999
    }
    var product = 0;    
    var result = 0;
    multiplicand = parseInt(multiplicandString); //999, 998...
    for(multiplicand;  multiplicand > 0; multiplicand--){ //Loop 999 times
       multiplier = parseInt(multiplierString); //999, 998...
       for(multiplier; multiplier > 0; multiplier--){//Loop 998001 times
          product = multiplicand * multiplier; //999*999,999*998...998*999,998*998...
          var stringProduct = (''+product);// 90909
          var strLength = stringProduct.length; //Make sure not to modify actual string
          for(strLength; strLength >= 1; strLength--){ //For the length of string
            if( stringProduct[0] == stringProduct[stringProduct.length-1]) //If 90909: 9==9, 090:0==0, 9:9==9
            {
              if(stringProduct.length <= 3){//allow for 090                 
                if(product > result){ //if product is larger than existing result replace it with new larger number
                  result = product;
                } 
              }   
              stringProduct = stringProduct.slice(1, -1);//take off the first and last numbers
            }            
          }
        }
    }
  return result;
}

Answer 1

Javascript numbers are stored in IEE754 format that can precisely represent numbers up to 2^53 - 1 (9007199254740991), so it's impossible to use the built-in Javascript arithmetic to get actual digits for a lot of two 8-digit number products (for example, 94,906,266 * 94,906,266 exceeds the abovementioned maximum).

There are several BigNumber libraries for JavaScript, but I'll only give an answer for the case of 7 digits and less. A brute-force enumeration with a couple of optimization is quite fast for n<7 compared to the original OP code that took 1370 ms for 3 digits and 3+ minutes for 4 digits.

function largestPalindromeOfTwoFactors(len1, len2) {
    // calculate number range for n digits:  10^(n-1)..10^n-1 (e.g. 10-99)

    // 'a' (outer loop) will be the largest multiplicand
    var maxA = Math.pow(10, Math.max(len1, len2)) - 1 |0;
    var minA = (maxA + 1) / 10 |0;

    // 'b' (inner loop) will be the smallest multiplicand
    var maxB = Math.pow(10, Math.min(len1, len2)) - 1 |0;
    var minB = (maxB + 1) / 10 |0;

    var maxMul = 0, maxMulA, maxMulB;

    for (var a = maxA; a >= minA; a--) {
        // in case len1==len2 only process 'b' smaller than current 'a'
        // as the larger numbers were already checked when used for 'a'
        for (var b = Math.min(a, maxB); b >= minB; b--) {
            var mul = a * b;
            if (mul <= maxMul) {
                // no need to continue, we'll never exceed maxMul with a smaller 'b'
                break;
            }
            var mulStr = mul.toString();
            for (var i = mulStr.length-1, j=0; i>=j && mulStr[i] == mulStr[j]; i--, j++) {}
            if (i <= j) {
                maxMul = mul, maxMulA = a, maxMulB = b;
                // 'a' smaller than current 'b' won't produce a bigger product
                minA = Math.max(minA, b);
            }
        }
    }
    // retain the order of input parameters' magnitudes: 2,3 -> 99, 951
    return [maxMul, len1 < len2 ? maxMulB : maxMulA, len1 < len2 ? maxMulA : maxMulB];
}

Test run:

for (var i=1; i<=7; i++) {
    var start = Date.now();
    console.log('%o in %d ms', largestPalindromeOfTwoFactors(i, i), Date.now() - start);
}

[9, 9, 1] in 0 ms
[9009, 99, 91] in 0 ms
[906609, 993, 913] in 2 ms
[99000099, 9999, 9901] in 1 ms
[9966006699, 99979, 99681] in 551 ms
[999000000999, 999999, 999001] in 171 ms
[99956644665999, 9998017, 9997647] in 162363 ms <<<<<< ughhhh

Notes:

• There are much better algorithms.
• 090 isn't a number, 90 is, so the former and the likes are not palindromes.