views:

1076

answers:

8

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

+5  A: 

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.

Stefan Kendall
Binet's formula will only give you an approximation in constant time. If you need an exact answer using this method you need arbritrary precision floating point arithmetic which is not possible in constant time.
Mark Byers
I thought Binet's gave you e, or is that only when n=1?
Norla
You're talking about hardware problems, friend, not software problems :). The error is small enough that you can get the correct integer values just by rounding. I don't know at what point this breaks down, but a simple program test (using double precision) can confirm this.
Stefan Kendall
It definitely works up to F[100]. You probably won't notice error until much higher numbers.
Stefan Kendall
Also, this is the classic example of speed vs accuracy. Binet's formula will be super-fast for pure approximations at any level of F[n], but the slower method guarantees accuracy.At any rate, any program using fibonacci numbers should probably just pre-compute all the values using a guaranteed-accuracy algorithm. You wind up needing 400 bytes to precompute enough value to solve the OP's conditions.
Stefan Kendall
anyway I think you only have to *memorize* the 2 previous values when looping... but you'llsoon get an overflow when using long.
Carlos Heuberger
I'm pretty sure you don't need any floating point arithmetic at all to do this computation. You need a symbolic understanding of square roots, and arbitrary-precision integer arithmetic, but I believe that's sufficient.
Joren
It's arguable whether memoization is more "straightforward" than just writing the iterative version :)
hobbs
I meant straightforward if recursion was a requirement. I agree that the iterative version is more straightforward in the absolute sense, and if I was doing precomputation, I'd probably use the iterative approach. Occasionally, exponentation is expensive to do on the fly.
Stefan Kendall
+7  A: 

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.

Mark Byers
+1  A: 

The problem is not JAVA, but the way you are implementing your Fibonacci algorithm. You are computing the same values many times, which is slowing your program.

Try something like this : Fibonacci with memoization

Soufiane Hassou
A: 

If you use the naive approach, you'll end up with an exploding number of same calculations, i.e. to calc fib(n) you have to calc fib(n-1) and fib(n-2). Then to calc fib(n-1) you have to calc fib(n-2) and fib(n-3), etc. A better approach is to do the inverse. You calc starting with fib(0), fib(1), fib(2) and store the values in a table. Then to calc the subsequent values you use the values stored in a table (array). This is also caled memoization. Try this and you should be able to calc large fib numbers.

lewap
+2  A: 

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];
Simon Righarts
+5  A: 

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.6n), 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

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.6n) to O(n).

Yacoby
+3  A: 

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;
    }
}
Peter Lawrey
A: 

This is the code in Python, which can easily be converted to C/Java. First one is recursive and second is the iterative solution.

def fibo(n, i=1, s=1, s_1=0):
    if n <= i: return s
    else: return fibo(n, i+1, s+s_1, s)


def fibo_iter_code(n):
    s, s_1 = 1, 0
    for i in range(n-1):
       temp = s
       s, s_1 = s+s_1, temp
       print(s)
Swapneel Patil