Fibonacci Y Combinator

JavaScript performance comparison

Revision 5 of this test case created by Rhys

Preparation code

<script>
  var r5 = Math.sqrt(5);
</script>
    

Test runner

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

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
fast loop
function fib_fastloop(n) {
var half = Math.floor((n-1)/2);
for(var i = 0, a = 0, b = 1; i < half; i++,b+=(a+=b)) {}
return n%2==0 ? b : a;
}
fib_fastloop(200)
pending…
recursive with memoization
function fib2(n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib2(n - 1) + fib2(n - 2);
}

function memo(f) {
  var cache = {}
  return function(x) {
    if (typeof cache[x] === 'undefined') {
      cache[x] = f(x);
    }
    return cache[x];
  }
}
fib2 = memo(fib2);

fib2(200)
pending…
Y combinator
var Y = function(F) {
    return (function(x) {
      return F(function(y) {
        return (x(x))(y);
      });
    })(function(x) {
      return F(function(y) {
        return (x(x))(y);
      });
    });
    };

var FactGen = function(fact) {
    return (function(n) {
      return ((n == 0) ? 1 : (n * fact(n - 1)));
    });
    };
fib3 = (Y(FactGen))

fib3(200)
pending…
Y combinator with memoization
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 fib4 = Ymem(function(g) {
  return (function(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return g(n - 1) + g(n - 2);
  });
});

fib4(200)
pending…
direct
function fibonacci_direct(n) {
  if (n < 2) return n;
  return (Math.pow((1 + r5) / 2, n) - Math.pow((1 - r5) / 2, n)) / r5;
}
fibonacci_direct(200)
pending…
loop
function fibonacci_loop(n) {
  if (n < 2) return n;
  var previous = 0;
  var current = 1;
  var next;
  for (var i = 1; i < n; i++) {
    next = previous + current;
    previous = current;
    current = next;
  }
  return current;
}
fibonacci_loop(200)
pending…
Fib with matrices
//to find the nth number
//fibonacci identity
Fib = [1,1,1,0]
//multiply a 2x2 Matrix
function mult2x2(a,b){
 return([a[0]*b[0]+a[1]*b[2],a[0]*b[1]+a[1]*b[3],a[2]*b[0]+a[3]*b[2],a[2]*b[1]+a[3]*b[3]]);
}
function fibRecurse(M,n){
  //if n is one return the identity
  if(n==1)
    return M;
  //get the value of fib^n/2 (divide)
  var fibSoFar = fibRecurse(M,Math.floor(n/2));
  //multiply the two halves (and multiply by 1 more if not an even number) (conquer)
  fibSoFar = mult2x2(fibSoFar,fibSoFar);
  if(n%2==1)
    fibSoFar = mult2x2(fibSoFar,Fib);
  return fibSoFar;
}
fibRecurse(Fib,200)[0];
pending…

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.

0 Comments