斐波那契通项公式

fibonacci.js

function mulMatrix(a, b) {
	return [
		a[0]*b[0] + a[1]*b[2],
		a[0]*b[1] + a[1]*b[3],
		a[1]*b[0] + a[3]*b[2],
		a[1]*b[1] + a[3]*b[3]
	];
}

function powMatrix(a, n) {
	var b = a;
	for(var i = 1; i < n; ++i) {
		b = mulMatrix(b, a);
	}

	return b;
}

function fibonacci(n) {
	if(n < 3) return 1;

	var matrix = powMatrix([0, 1, 1, 1], n - 2);

	return matrix[1] + matrix[3];
}