Testing whether sums of cubes are Fibonacci numbers 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.

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&lt;=uLimit;a++)    //Outer Loop, 1 to maximum
   for(long b=1;b&lt;=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 deliberate; I need them to get the necessary precision. Is there anything other than my variable types that I could change to gain better efficiency?
You could change the order of your loops.

Loop over the Fibonacci numbers - there is only O(log N) of these less than N.

Then loop down from to cbrt(N) to cbrt(N/2) looking for the highest of the two cubes in its sum.