Fast Fibonacci Implementations

FastFib.js

/* Looping version */

function fib(n){
	var fk = 0, fkp = 1,
		f2k, f2kp, b;
	for(b = Math.floor(Math.log(n)/Math.LN2); b > 0; b--){
		f2k = fk*(2*fkp-fk);
		f2kp = fkp*fkp+fk*fk;
		if(n&(1<<b)){
			fk = f2kp;
			fkp = f2k+f2kp;
		}else{
			fk = f2k;
			fkp = f2kp;
		}
	}
	//avoid calculating thrown-away neighboring number
	return (n&1)?(fkp*fkp+fk*fk):(fk*(2*fkp-fk));
}

/* Naive Recursive version
   Easily memoized, but requires multiple return.
   Implicitly counts bits with stack frames.
 */

function rfib(n){
	var fk, f2k, f2kp;
	if(n === 0){ return [0, 1]; }
	fk = rfib(n>>>1);
	f2k = fk[0]*(2*fk[1]-fk[0]);
	f2kp = fk[0]*fk[0]+fk[1]*fk[1];
	return (n&1)?[f2kp, f2k+f2kp]:[f2k, f2kp];
}
function fib(n){
	var fk = rfib(n>>>1);
	return (n&1)?(fk[0]*fk[0]+fk[1]*fk[1]):(fk[0]*(2*fk[1]-fk[0]));
}

/* Tail Recursive version */

function rfib(n, b, fk, fkp){
	var f2k, f2kp;
	if(b === 1){
		return (n&1)?(fk*fk+fkp*fkp):(fk*(2*fkp-fk));
	}
	f2k = fk*(2*fkp-fk);
	f2kp = fk*fk+fkp*fkp;
	return (n&b)?
		rfib(n, b>>>1, f2kp, f2k+f2kp):
		rfib(n, b>>>1, f2k, f2kp);
}

function fib(n){
	return rfib(n, 1<<Math.floor(Math.log(n)/Math.LN2), 0, 1);
}

/* Tail Recursive with closure */

function fib(n){
	function rfib(b, fk, fkp){
		var f2k, f2kp;
		if(b === 1){
			return (n&1)?(fk*fk+fkp*fkp):(fk*(2*fkp-fk));
		}
		f2k = fk*(2*fkp-fk);
		f2kp = fk*fk+fkp*fkp;
		return (n&b)?
			rfib(b>>>1, f2kp, f2k+f2kp):
			rfib(b>>>1, f2k, f2kp);
	}
	return rfib(1<<Math.floor(Math.log(n)/Math.LN2), 0, 1);
}