フィボナッチ数列の実装とメモ化

fibonacci.js

var fib = (function () {
	var num = [];
	return function fib(n) {
		if (num[n] === undefined) num[n] = n > 0 ? fib(n-2) + fib(n-1) : -n;
		return num[n];
	};
})();

// test
var time = new Date();
for (var i = 0; i < 1000; i++) {
	console.log(fib(i));
}
console.log(new Date() - time + "ms");

Function.prototype.js

Function.prototype.memo = function () {
	var	f = this,
		result = {};
	return function () {
		var key = JSON.stringify(arguments);
		if (result[key] === undefined) result[key] = f.apply(null, arguments);
		return result[key];
	};
};

var fib = (function (n) { return n > 0 ? fib(n-2) + fib(n-1) : -n }).memo();

// test
var time = new Date();
for (var i = 0; i < 1000; i++) {
	console.log(fib(i));
}
console.log(new Date() - time + "ms");

general.js

var fib = (function () {
	// square root of 5, golden ratio
	var r5 = Math.sqrt(5),
		gr = (1 + r5) / 2,
		gr_ = (1 - r5) / 2;
	
	return function (n) {
		return Math.round(Math.pow(gr, n) - Math.pow(gr_, n)) / r5;
	};
})();

// test
var time = new Date();
for (var i = 0; i < 1000; i++) {
	console.log(fib(i));
}
console.log(new Date() - time + "ms");

それぞれの速度は、大体以下の通りでした(マシンの性能と実行環境によります)
fibonacci.js 160ms
Function.prototype.js 200ms
general.js 140ms

Function.prototype.jsの仕様を変更し、Function.prototype.memoを実行すると、fibonacci.jsと同様なFunctionを生成します。
その為、毎度.memoを付加して実行する必要がなくなり、高速になりました。

また、general.jsはグローバルを汚さないようクロージャにしました。

計算速度は、general.js > fibonacci.js ≒ Function.prototype.jsとなっています。