2
\$\begingroup\$

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<=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 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?

\$\endgroup\$

migrated from stackoverflow.com Jun 9 '14 at 4:02

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ cache the powers. fill an array with the cubes from 1 to your limit. and don't recalculate them in the nested cycle. \$\endgroup\$ – ra2085 Jun 9 '14 at 3:39
  • \$\begingroup\$ @ra2085 interesting idea, but how much memory does an array of BigInteger with 9223372036854775807 elements require? \$\endgroup\$ – Brian J. Fink Jun 9 '14 at 3:47
  • 2
    \$\begingroup\$ It'd probably be easier to optimize this at the algorithm level, and not the code level. This is as bruteforce as you're going to get, and you may get some wins by reducing the math instead of worrying about programming overhead. \$\endgroup\$ – Makoto Jun 9 '14 at 3:51
  • \$\begingroup\$ It's in beta, but that doesn't mean it's a good site to post to. Lots of good advice going on there if you have a good question. And it seems to be doing pretty well \$\endgroup\$ – awksp Jun 9 '14 at 3:52
  • \$\begingroup\$ hehe, a lot, but you can always do it in batches. Divide and conquer! \$\endgroup\$ – ra2085 Jun 9 '14 at 3:54
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't it be inefficient to invent my own cube root algorithm that works with BigInteger or BigDecimal? \$\endgroup\$ – Brian J. Fink Jun 9 '14 at 4:27
  • \$\begingroup\$ Also I would need an efficient way to generate the Fibonacci sequence. It just seemed like the better option to use the Mobius test on the individual cases of sums of cubes, even though there's more of them. \$\endgroup\$ – Brian J. Fink Jun 9 '14 at 4:38
  • 1
    \$\begingroup\$ You can generate the Fibbonacci numbers sequentially using the usual F_n=F_{n-1}+F_{n-2} in this case - you wont get much faster than that ;) \$\endgroup\$ – Michael Anderson Jun 9 '14 at 5:05
  • 1
    \$\begingroup\$ @BrianJ.Fink It might be sufficient to approximate the cube root with a few iterations of Newton's method or something, because the search space savings are almost certainly worth it \$\endgroup\$ – awksp Jun 9 '14 at 5:56
  • 1
    \$\begingroup\$ Looping down from cbrt(N) to cbrt(N/2) to find the larger item of a pair of cubes will be more efficient (by a factor of almost 4) than looping up . . . \$\endgroup\$ – Neil Slater Jul 1 '15 at 9:49
2
\$\begingroup\$

I don't think your code will ever finish executing. Just looping from 1 to Long.MAX_VALUE (Convenient way to get long's max value) will take a stupid amount of time, even if you do no calculation:2^63 - 1 iterations, lets assume 1 billion per second. = 9223372036 seconds = 292 years. And thats with a billion per second, just one loop, not two. BigDecimals are slow, and the inner loop basically squares the amount of time it will take...

If you ever decide to lower your limit and make it a bit more feasible, do what a commenter said and precalculate the cubes, instead of doing it again and again in the inner loop. This would probably save a significant amount of time, as BigDecimals are quite slow. If you did your cubing with BigIntegers it might be faster. Even with these optimizations, you will never finish with the current max value.

If you ever do want this to run even faster, I would suggest programming it in C++ using the GMP library for highly optimized arbitrary precision math. You could even write some C++ and then use it from java with JNI.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.