Fibonacci numbers algorithm

The most common recursive algorithm for Fibonacci sequences looks something like this:

unsigned int fib(unsigned int n){
   return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}

What is the most efficient fibonacci algorithm in terms of time and space complexity?

Answers


The formula Jan suggested is not very magical (and I can prove it here if you have a basic understanding linear algebra, and are interested).

It's also the fastest way. So resorting to JavaScript (I can do this in other languages you'd like it's simply:

var sqrt5= Math.sqrt(5);
var phi = (1 + sqrt5) / 2;

function fibonacci(n){
     return (Math.pow(phi,n) - Math.pow(-phi,-n)) / sqrt5;
}

If for some reason you deeply want to avoid it - you can do O(n) (rather than exponential time which you currently have) using a very basic form of dynamic programming. Instead of calculating the last two numbers every time - you remember them.

function fib(n){
    var x=1,y=1,t;
    for(var i=1;i<n;i++){ 
        t=x;
        x+=y;
        y=t;
    }
    return x;
}

Which returns fib(50) almost instantly (the recursive approach takes a huge time here)


Using floating point for computing integers is generally a bad idea. So is in the answers I see above, with the closed formula.

There is a surprisilngly less known formula, which I will try to illustrate below. A better way is to use the following matrix: [[1 1] [1 0]]. It can be shown that raising this to the n-th power will give you [[f(n+1) f(n)] [f(n) f(n-1)]]. You can just use 4 params if you don't want to play with matrices, and, of course, use fast exponentiation to get the result for f(N) in O(log N).

See a more detailed explanation here: Nth Fibonacci number O(log n)

Let me know if yoou need any extra details.


Need Your Help