5
\$\begingroup\$

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);
    }
}
};
\$\endgroup\$
4
\$\begingroup\$

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);
    }

};
\$\endgroup\$
  • 1
    \$\begingroup\$ I believe round and pow should be Math.round and Math.pow \$\endgroup\$ – SirPython Nov 4 '15 at 1:51
  • \$\begingroup\$ @SirPython I believe not. Math.pow and Math.round is java... \$\endgroup\$ – TheCoffeeCup Nov 4 '15 at 1:52
  • 1
    \$\begingroup\$ Yes, and this is JavaScript; there are no round or pow functions. However, there is Math.round and Math.pow. \$\endgroup\$ – SirPython Nov 4 '15 at 1:53
  • \$\begingroup\$ @SirPython I see... \$\endgroup\$ – TheCoffeeCup Nov 4 '15 at 3:07
  • 1
    \$\begingroup\$ @holroy This starts to fail (due to precision) at fibonacci(76) as off-by-one, and gets worse. \$\endgroup\$ – TheCoffeeCup Nov 6 '15 at 0:01
8
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Or you could use an iterative approach using a table \$\endgroup\$ – holroy Nov 3 '15 at 20:19
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Calculating \$F_n\$ using the sequence should be \$O(n)\$, but the code in the question is much worse than \$O(n)\$. \$\endgroup\$ – 200_success Nov 4 '15 at 4:10
1
\$\begingroup\$

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 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));

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This does not use recursion at all. It uses a lookup table when doing the math, not recursion. This is very close to the standard iterative version of calculating the Fibonacci numbers, and is a plain O(n) algorithm. Downside of this version, is that it does need to calculate all values, and it stores all of them as it is calculating. \$\endgroup\$ – holroy Nov 5 '15 at 19:15
  • \$\begingroup\$ Changed the code almost completely. Now it stores the values in the variables and computes them more directly. Does this count as recursion? \$\endgroup\$ – Nevermore Nov 5 '15 at 22:57
  • \$\begingroup\$ Still not a recursive solution, but it is a viable iterative solution. \$\endgroup\$ – holroy Nov 5 '15 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.