How do I make this nested for loop, testing sums of cubes, more efficient?
- by Brian J. Fink
I'm trying to iterate through all the combinations of pairs of positive long integers in Java and testing the sum of their cubes to discover if it's a Fibonacci number. I'm currently doing this by using the value of the outer loop variable as the inner loop's upper limit, with the effect being that the outer loop runs a little slower each time. Initially it appeared to run very quickly--I was up to 10 digits within minutes. But now after 2 full days of continuous execution, I'm only somewhere in the middle range of 15 digits. At this rate it may end up taking a whole year just to finish running this program. The code for the program is below:
import java.lang.*;
import java.math.*;
public class FindFib
{
public static void main(String args[])
{
long uLimit=9223372036854775807L; //long maximum value
BigDecimal PHI=new BigDecimal(1D+Math.sqrt(5D)/2D); //Golden Ratio
for(long a=1;a<=uLimit;a++) //Outer Loop, 1 to maximum
for(long b=1;b<=a;b++) //Inner Loop, 1 to current outer
{
//Cube the numbers and add
BigDecimal c=BigDecimal.valueOf(a).pow(3).add(BigDecimal.valueOf(b).pow(3));
System.out.print(c+" "); //Output result
//Upper and lower limits of interval for Mobius test: [c*PHI-1/c,c*PHI+1/c]
BigDecimal d=c.multiply(PHI).subtract(BigDecimal.ONE.divide(c,BigDecimal.ROUND_HALF_UP)),
e=c.multiply(PHI).add(BigDecimal.ONE.divide(c,BigDecimal.ROUND_HALF_UP));
//Mobius test: if integer in interval (floor values unequal) Fibonacci number!
if (d.toBigInteger().compareTo(e.toBigInteger())!=0)
System.out.println(); //Line feed
else
System.out.print("\r"); //Carriage return instead
}
//Display final message
System.out.println("\rDone. ");
}
}
Now the use of BigDecimal and BigInteger was delibrate; I need them to get the necessary precision. Is there anything other than my variable types that I could change to gain better efficiency?
