# 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.
return (Ymem(F, cache))(n);
};
}

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…

## Revisions

You can edit these tests or add even more tests to this page by appending `/edit` to the URL.