Calculating Fibonacci numbers

Question

The following problem is currently taking more than 8 seconds to execute. Please help me to modify the program, so that execution time will be reduced.

var yourself = {
fibonacci : function(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    else {
        return this.fibonacci(n - 1) +
            this.fibonacci(n - 2);
    }
}
};

Answer 1

If you are just looking for a simple function that gets the nth Fibonacci number, you can use phi:

$$\frac{\sqrt5 + 1}2$$

To calculate the nth fibonacci number:

$$fib(n)=round(\phi^n/\sqrt5)$$

I don't know javascript very well, but if you can store the value of phi and square root of 5, you can do:

var SQRT_5 = Math.sqrt(5);
var PHI = (SQRT_5 + 1) / 2;

var yourself = {
    fibonacci : function(n) {
        if (n <= 1) {
            return n;
        }            
        return Math.round(Math.pow(PHI, n) / SQRT_5);
    }

};

Answer 2

This is one of the standard examples for algorithmic complexity. This algorithm is very easy to understand since it matches the mathematical definition well, but performs miserably since it's trying to calculate a number that grows exponentially by adding 0s and 1s together.

The key observation is that to calculate, say, fibonacci(5), it has to recursively calculate fibonacci(4) and fibonacci(3). Then to calculate fibonacci(4), it has to calculate fibonacci(3) again, which is completely wasteful. There are several things we can do to go faster:

• Build from the bottom up. Start two variables a=0 and b=1, then run a loop where you set a=b and b=a+b (careful to not blast values as you're using them). This is how you would do it by hand.
• Use your recursive solution, but cache the results so that it doesn't repeat work. This is called memoization.
• Use the closed-form formula.

Answer 3

I'm not too familiar with javascript but here goes.

First a bit of background. The way you have discovered to calculate the fibonacci numbers is known as dynamic programming.

Now the good thing about dynamic programming is that it enforces the idea of building a solution. That is, you start by solving a problem similar to the one you are trying to solve but you start by focusing on the smallest aspect of it, which then allows you to build on that solution to solve an even more complex problem

What's the point of my ramble? I noticed you were employing dynamic programming in solving this problem, but you missed one thing which was reusing the other solutions you already got. Not reusing your solutions leads to an exponential time algorithm which doesn't scale well with larger input.

Solution

Store the results of previous solutions and use them to solve the larger ones

fibonacci = function (n) {
    var fib = [0, 1]
    return function memoizedFib(n) {
        if (!fib[n]) {
            fib[n] = memoizedFib(n - 1) + memoizedFib(n - 2);
        }
        return fib[n];
    }(n);
};

See this post for another method of computing fibonacci

Answer 4

Complexity

Sequence definition

$$ F_{n+2} = F_{n+1} + F_n $$

which means that your complexity is \$ O(n) \$.

Matrix definition

$$ { \left ( \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right ) } ^ n = \left ( \begin{matrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{matrix} \right ) $$

As you can see with matrix definition we can improve complexity using exponentiation by squaring which tells us that

$$ A^{2n} = A^n \times A^n, A^{n+1} = A^n \times A $$

Which means that complexity using matrix definition is \$ O(\log n) \$

Big integers

Fibonacci numbers are fast growing sequence, so in order to store values you have to use arbitrary-precision arithmetic.

Answer 5

Another method is to do something closer to this. Note that I have no idea if this code is ok, but it worked in Google Docs when I made it a standalone function.

var yourself = {
fibonacci : function(n) {
    var n0 = 0;
    var n1 = 1;
    var n2;
    for (var l = 2; l <= n; l++) {
        n2 = n0 + n1;
        n0 = n1;
        n1 = n2;
    }
    return n2;
}
}

This method has you work upwards from 0 to n (instead of downwards from n to 0) and store the results in three variables as you go. It makes things faster since you don't have to find fibbonacci(n-1) twice, fibbonacci(n-2) three times, etc.

Answer 6

Explanation:

Your code calls the Fibonacci method twice on each recursive call which produces redundant calculations.

Here is an efficient and compact way to calculate Fibonacci using some of the ecmascript-6 features. It keeps a private array in cache holding previous and current values of the sequence to be able to calculate the next values without duplication.

Solution:

const fibonacci = (n, [p,c] = [0,1]) => n == 0 ? 0 : n == 1 ? c : fibonacci(n-1, [c,p+c])

console.log(fibonacci(3)); // 2
console.log(fibonacci(10)); // 55
console.log(fibonacci(100)); // 354224848179262000000
console.log(fibonacci(1000)); // 4.346655768693743e+208

Verbose solution explanation:

const fibonacci = (n, [previous, current] = [0,1]) => {
  //0 appears when initial fib method has value 0, so return 0
  return n == 0 ? 0 : 
         //1 occurs if n is initially 1 or when calculation is done
         //if so return current fibo number
         n == 1 ? current :
         //otherwise call fibonacci, reduce n and update previous and current values
         fibonacci(n-1, [current,previous+current])
}

console.log(fibonacci(50));