13/09/2015

[Java] Better Fibonacci algorithms

The last time we saw a good Fibonacci algorithm, which is better than the textbook one, but still falls short of its duties for numbers around 100.

So here are a couple others algorithms which can efficiently compute big Fibonacci numbers correctly. I was able to test them up to around 10 millions, after which it took more than 30 seconds on my machine to produce a solution, which wasn't always correct.

12/09/2015

[Java] Good Fibonacci algorithm

Here is an efficient implementation of the Fibonacci algorithm by Michael Goodrich. I found it to be very fast and you should think about using it instead of the textbook implementation of the algorithm which is highly unoptimized and will start crashing pretty much immediately when you raise the number you want to compute by little.

 public static long[] fibGood(int n) {  
   if (n < = 1) {  
     long[] answer = {n,0};  
     return answer;  
   } else {  
     long[] tmp = fibGood(n-1);  
     long[] answer = {tmp[0] + tmp[1], tmp[0]};  
     return answer;  
   }  
 }  


You will have the answer for fibGood(n) in fibGood(n)[0]