# Efficiency problem

• November 4th, 2011, 09:49 AM
mccolem
Efficiency problem
I have the following problem to solve:

Find the largest palindromic number made from the product of two N-digit numbers.

This is my class to find the largest palindromic number:

Code java:

```  public class LargestPalindromeNumber {   private long factorLength, highValue, max = 0, factor1 = 0, factor2 = 0;   public LargestPalindromeNumber(long n){   factorLength = n; // number of digits in each factor highValue = (long) (Math.pow(10, factorLength) - 1); // highest value a factor can have   }         public long getLargestPalindrome1(){   for( long i = highValue; i > highValue/10 ; i = i - 1){   if(i < factor2) return max;   for(long j = i ; j > highValue / 10; j = j - 1 ){   if(i % 11 == 0 || j % 11 == 0){   if(i*j < max) j = highValue/10;     else{   if(isPalindrome(i * j)){ max = i * j; factor1 = i; factor2 = j; j = highValue/10;   } } } }// end second for loop   }// end first for loop   return max;   }// end getLargestPalindrome()     // Checks whether a number is a palindrome public boolean isPalindrome(long n){   long reverse = 0; long value = n;   while(n > 0){   reverse = (reverse * 10) + (n % 10);   n = n / 10;   }// end while   return(value == reverse);   }// end isPalindrome     // Returns the value of factor1 public long getFactor1(){ return factor1; }     // Returns the value of factor2 public long getFactor2(){ return factor2; }     }// end LargestPalindromeNumber class```

This is my main class:

Code java:

```  import tcdIO.*;   public class Main {     public static void main(String[] args) {   Terminal window; LargestPalindromeNumber bigPal; long ndigit;   window = new Terminal("Find the Largest Palindromic Number");   window.println("This program finds the largest palindromic number that is a product of two N-Digit numbers.\n"); window.println();   ndigit = window.readInt("Enter the number of digits in the factors : "); bigPal = new LargestPalindromeNumber(ndigit);     window.println(); window.println("The largest palindromic number that is a "); window.println("product of two " + ndigit + " digit numbers is: "); window.println(); window.println( "" + bigPal.getLargestPalindrome1() ); window.println(); window.println("whose factors are : " + bigPal.getFactor1() + " and " + bigPal.getFactor2() + ".");   }// end main()   }// end Main class```

Q: Can you suggest ways to improve the efficiency of this code as it takes a long time to get an answer when i enter 9-digit by 9-digit factors, in fact I haven't waited for it to produce an answer yet.

Note:
1) The palindromic numbers I am searching for will be divisible by 11.
2) It works fine up until 8-digit by 8-digit numbers.
• November 4th, 2011, 02:34 PM
Freaky Chris
Re: Efficiency problem
Have you considered counting insteps of 11?

Chris
• November 4th, 2011, 02:56 PM
mccolem
Re: Efficiency problem
I have tried that already but its complicated because if the factors are even number digits e.g. 99, I have to decrease i by 11 and j by 1, but if it is an odd number of digits e.g. 999 I have to decrease i by 1 and j by 11. Which sounds simple to implement but it is difficult to insure every possible combination of i * j is checked.

I'll try again though.

Edit: Also I let my program run until it found the 9-digit * 9-digit largest palindrome. It took 5/6 minutes and I am fairly sure I cannot compute any palindromes for n-digit factors greater than this as it would result in a number bigger than long can handle. Could you confirm that for me.

Thanks.
• November 4th, 2011, 03:10 PM
Freaky Chris
Re: Efficiency problem
I see, I think I may have missed some bits here sorry.

However, given that you iterate in reverse, starting at max values, that means as soon as you calculate a palindrome, you have the largest possible. So you can stop looping? Or have a missed the point again, and should just crawl into bed lol!

Edit: Maximum value of long is deffined by Long.MAX_VALUE == 2^63 -1

Chris
• November 4th, 2011, 03:30 PM
mccolem
Re: Efficiency problem
Quote:

Originally Posted by Freaky Chris
I see, I think I may have missed some bits here sorry.

However, given that you iterate in reverse, starting at max values, that means as soon as you calculate a palindrome, you have the largest possible. So you can stop looping? Or have a missed the point again, and should just crawl into bed lol!

Edit: Maximum value of long is deffined by Long.MAX_VALUE == 2^63 -1

Chris

Code :

```  public long getLargestPalindrome1(){   for( long i = highValue; i > highValue/10 ; i = i - 1){   if(i < factor2) return max; //Here the method exits if i is smaller than the smallest factor of the current largest palindrome   for(long j = i ; j > highValue / 10; j = j - 1 ){   if(i % 11 == 0 || j % 11 == 0){   if(i*j < max) j = highValue/10; //Here the j loop terminates if i*j is less than the current largest palindrome     else{   if(isPalindrome(i * j)){ max = i * j; factor1 = i; factor2 = j; j = highValue/10;   } } } }// end second for loop   }// end first for loop   return max;   }// end getLargestPalindrome()```

I think I have addressed what you are talking about above. I am still trying to incorporate stepping down by 11 into the method so I'll post when get something.

Also the first palindrome I get is not necessarily the largest.

e.g. 2-digit factors, the answer is 9009 whose factors are 99 and 91
e.g. 3-digit factors, the answer is 906609 whose factors are 993 and 913.

I would of found a palindrome with i = 999 and j = some integer first but 993*913 was bigger than it.
• November 4th, 2011, 03:38 PM
Freaky Chris
Re: Efficiency problem
if you loop from highVal to highVal/10 for i and the same for j

you should always come across the largest possible palindrome first.

Chris
• November 4th, 2011, 03:44 PM
mccolem
Re: Efficiency problem
If I do that for 3-digit factors, the first palindrome I find is

995*583 = 580085

which is smaller than 993*913 = 906609