Fibonacci数，Θ(log n)

生成Fiboncci F_n数有Θ(1)，Θ(n)甚至指数级的算法，不过有Θ(log n)的吗？告诉你，有。

首先，关于Fibonacci数，有下面的定理（假设F₀ = 0，n≥2）

证明可以用归纳法，n=2时不证自明，假设n=k-1时成立，那么n=k时，

现在，计算F(n)的问题就转化到计算矩阵上来。不过现在问题已经很明晰了——反复平方法。

下面是js源码：

var fib = function() {var f = function(n, a, b, p, q) {if (n == 0) return b;if (n & 1) return f(n - 1, b * q + a * q + a * p, b * p + a * q, p, q)else return f(n >>> 1, a, b, q * q + p * p, q * (2 * p + q));}return function(n) {return f(n, 1, 0, 0, 1)};}();