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

What does mysql_real_escape_string() do that addslashes() doesn't?

php security sql-injection

Why do we need a DB-specific functions like mysql_real_escape_string()? What can it do that addslashes() doesn't?

Generating a Unique String by UDFunction

sql sql-server sql-server-2008 tsql

I generating a string for my Primarykey column similar identity function. but its behavior is unexpected.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.