Java Program Fibonacci Sequence

Question

I am writing a "simple" program to determine the Nth number in the Fibonacci sequence. Ex: the 7th number in the sequence is: 13. I have finished writing the program, it works, but beginning at the 40th number it begins to delay, and takes longer, and longer. My program has to go to the 100th spot in the series.

How can I fix this so it doesn't take so long? This is very basic program, so I don't know all the fancy syntax codes.. my formula is:

if n =1 || n = 0
   return n;

else 
    return F(n-1) + F(n-2);

This works great until it goes past the 40th term. What other statement do I have to add to make it go quicker for higher numbers??

Solution 1

The problem is that because you are using simple recursion, you re-evaluate F(n) multiple times, so your execution time is exponential.

There are two simple ways to fix this:

1) Cache values of F(n) when they are evaluated the first time. Check the cache first before evaluating F(n) to see if you have already calculated it for this n.

2) Use an iterative approach: Calculate F(1), F(2), F(3), etc... until you reach the number you need.

Solution 2

The issue is that your algorithm, while mathematically pure (and nice) isn't very good.
For every number it wants to calculate, it has to calculate two lower ones which in turn have to calculate two lower ones, etc. Your current algorithm has a Big O notation complexity of about O(1.6ⁿ), so for very large numbers (100 for example) it takes a long time.

This book, Structure and Interpretation of Computer programs has a nice diagram: showing what happens when you generate fib 5 with your algorithm

_{(source: mit.edu)}

The simplest thing to do is to store F - 1 and F - 2, so that you don't have to calculate them from scratch every time. In other words, rather than using recursion, use a loop. Than means that the complexity of the algorithm goes from O(1.6ⁿ) to O(n).

Solution 3

There are a number of solutions. The most straightforward is to use memoization. There's also Binet's formula which will give you the nth fibonacci number in constant time.

For memoization, you store your results for F[a_i] in a map or list of some kind. In the naive recursion, you compute F[4] hundreds of thousands of times, for example. By storing all these results as you find them, the recursion ceases to proceed like a tree and looks like the straightforward iterative solution.

If this isn't homework, use Binet's formula. It's the fastest method available.

Solution 4

Try this example, it calculates the millionth Fibonacci number in a reasonable time frame without any loss of precision.

import java.math.BigInteger;

/*
250000th fib # is: 36356117010939561826426 .... 10243516470957309231046875
Time to compute: 3.5 seconds.
1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875
Time to compute: 58.1 seconds.
*/
public class Fib {
    public static void main(String... args) {
        int place = args.length > 0 ? Integer.parseInt(args[0]) : 1000 * 1000;
        long start = System.nanoTime();
        BigInteger fibNumber = fib(place);
        long time = System.nanoTime() - start;

        System.out.println(place + "th fib # is: " + fibNumber);
        System.out.printf("Time to compute: %5.1f seconds.%n", time / 1.0e9);
    }

    private static BigInteger fib(int place) {
        BigInteger a = new BigInteger("0");
        BigInteger b = new BigInteger("1");
        while (place-- > 1) {
            BigInteger t = b;
            b = a.add(b);
            a = t;
        }
        return b;
    }
}

Solution 5

Create an array with 100 values, then when you calculate a value for Fib(n), store it in the array and use that array to get the values of Fib(n-1) and Fib(n-2).

If you're calling Fib(100) without storing any of the previously calculated values, you're going to make your java runtime explode.

Pseudocode:

array[0] = 0;
array[1] = 1;
for 2:100
array[n] = array[n-1] + array[n-2];

View more solutions