Info

Examining various algorithms for calculating an N fibonacci number.

NOTE: some of the methods, using recursion, have upper bounds on how large a fibonacci number you can ask for, before the engine/browser will fail by running out of stack space for the recursion. Use recursion with caution.

Preparation code

<script>
  var m;
  
  function fibonacci_1(n) {
   if (n < 2) return n;
   if (n == 2) return 1;
   var n_1 = 1,
       n_2 = 1,
       i, tmp;
   if (n > 3) {
    for (var i = 4; i <= n; i++) {
     tmp = n_1;
     n_1 += n_2;
     n_2 = tmp;
    }
   }
   return n_1 + n_2;
  }
  
  function fibonacci_2(n) {
   if (n < 2) return n;
   return fibonacci_2(n - 1) + fibonacci_2(n - 2);
  }
  
  var fibonacci_3 = (function(n) {
   var store = {};
   return function _fib(n) {
    if (store[n]) return store[n];
    if (n < 2) return n;
    if (n == 2) return 1;
    return (store[(n - 1)] = _fib(n - 1)) + (store[(n - 2)] = _fib(n - 2));
   };
  })();
  
  function Ymem(F, cache) {
   if (!cache) cache = {}; // Create a new cache.
   return function(arg) {
    if (cache[arg]) return cache[arg]; // Answer in cache.
    var answer = (F(function(n) {
     return (Ymem(F, cache))(n);
    }))(arg); // Compute the answer.
    cache[arg] = answer; // Cache the answer.
    return answer;
   };
  }
  
  var fibonacci_4 = Ymem(function(g) {
   return (function(n) {
    if (n < 2) return n;
    return g(n - 1) + g(n - 2);
   });
  });
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

m = 1 + fibonacci_1(25);

m = 2 + fibonacci_2(25);

m = 3 + fibonacci_3(25);

m = 4 + fibonacci_4(25);

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

• Revision 1: published by Kyle Simpson on 26th May 2011
• Revision 2: published by fearphage on 27th May 2011
• Revision 3: published by Kyle Simpson on 27th May 2011

0 comments