CODEWITHSUNDEEP
javascript
Tesseract
Tesseract

Reputation: 8139

Why is this js code so slow?

This code takes 3 seconds on Chrome and 6s on Firefox. If I write the code in Java and run it under Java 7.0 it takes only 10ms. Chrome's JS engine is usually very fast. Why is it so slow here? btw. this code is just for testing. I know it's not very practical way to write a fibonacci function

fib = function(n) {
  if (n < 2) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
};

console.log(fib(32));

Upvotes: 5

Views: 430

Answers (5)

avadhutp
avadhutp

Reputation: 187

In addition to the memoization approach recommended by @galymzhan, you could also use another algorithm all together. Traditionally, the formula for nth Fibonacci number is F(n) = F(n-1) + F(n-2). This has time complexity that is directly proportional to n.

Dijkstra came up with an algorithm to derive Fibonacci numbers in less than half the steps as specified by the conventional formula. This was outlined in his writing EDW #654. It goes:

  1. For even numbers, F(2n) = (F(n))2 + (F(n+1))2
  2. For odd numbers, F(2n+1) = (2F(n) + F(n+1)) * F(n+1) OR F(2n-1) = (2F(n+1) - F(n)) * F(n)

Upvotes: 0

galymzhan
galymzhan

Reputation: 5558

This isn't fault of javascript, but your algorithm. You're recomputing same subproblems over and over again, and it gets worse when N is bigger. This is call graph for a single call:

                  F(32)
               /         \
            F(31)            F(30)
          /     \           /      \
      F(30)     F(29)     F(29)    F(28)
    /  \      /     \     /   \     |    \
F(29) F(28) F(28) F(27) F(28) F(27) F(27) F(26)

... deeper and deeper

As you can see from this tree, you're computing some fibonacci numbers several times, for example F(28) is computed 4 times. From the "Algorithm Design Manual" book:

How much time does this algorithm take to compute F(n)? Since F(n+1) /F(n) ≈ φ = (1 + sqrt(5))/2 ≈ 1.61803, this means that F(n) > 1.6^n . Since our recursion tree has only 0 and 1 as leaves, summing up to such a large number means we must have at least 1.6^n leaves or procedure calls! This humble little program takes exponential time to run!

You have to use memoization or build solution bottom up (i.e. small subproblems first).

This solution uses memoization (thus, we're computing each Fibonacci number only once):

var cache = {};
function fib(n) {
  if (!cache[n]) {
    cache[n] = (n < 2) ? n : fib(n - 1) + fib(n - 2);
  }
  return cache[n];
}

This one solves it bottom up:

function fib(n) {
  if (n < 2) return n;
  var a = 0, b = 1;
  while (--n) {
    var t = a + b;
    a = b;
    b = t;
  }
  return b;
}

Upvotes: 6

Steven Lu
Steven Lu

Reputation: 43417

Based on the evidence already provided the conclusion I draw is:

When the code is not run from the console (like in the jsFiddle where my machine, a Sandy Bridge Macbook Air, computes it in 55ms) the JS engine is able to JIT and possibly automatically memoize the algorithm.

When run from the js console none of this occurs. On my machine it was only under 10x slower: 460ms.

I then edited the code to look for F(38) which bumped the times up to 967ms and 9414ms so it has maintained a similar speedup factor. This indicates that no memoization is being performed and the speedup is probably due to JITting.

Upvotes: 2

RobG
RobG

Reputation: 147343

Just a comment...

Function calls are relatively expensive, recursion is very expensive and always slower than an equivalent using an efficient loop. e.g the following is thousands of times faster than the recursive alternative in IE:

function fib2(n) {
  var arr = [0, 1];
  var len = 2;

  while (len <= n) {
    arr[len] = arr[len-1] + arr[len-2];
    ++len;
  }
  return arr[n];
}

And as noted in other answers, it seems the OP algorithm is also inherently slow, but I guess that isn't really the issue.

Upvotes: 1

Ray Toal
Ray Toal

Reputation: 88378

As is fairly well known, the implementation of the fibonacci function you gave in your question requires a lot of steps if implemented naively. In particular, it takes 7,049,155 calls.

However, these kinds of algorithms can be greatly sped up with a technique known as memoization. If you see the function call fib(32) taking several seconds, the function is being implemented naively. If it returns instantly, there is a high probability that the implementation is using memoization.

Upvotes: 3

Related Questions