斐波那契数列 O(lgn) 算法

[xxleyi]

题：

fib 数列作为树形递归和动态规划问题的始祖型题目，想必几乎任何一个程序员都会写，且能正确写出。

但是，如果告诉你存在一个 O(lgn) 的算法，你能想出来吗？

n:      0 1 2 3 4 5 6
fib(n): 0 1 1 2 3 5 8

解：

递归方程 f(n) = f(n - 1) + f(n - 2) 还可以写成矩阵形式：

|q + p, q|     |a|     |new_a|
|        |  *  | |  =  |     |
|q    , p|     |b|     |new_b|

初始取值，a = 1, b = 0, p = 0, q = 1，迭代 2*n 次时，可以使用连续平方的技巧。

对左边的矩阵进行 double 转换，可以求得 2*n 时的新转换矩阵：

|q + p, q|     |q + p, q|   |q * q + p * p + q * q + 2 * p * q , q * q + 2 * p * q|
|        |  *  |        | = |                                                     |
|q    , p|     |q    , p|   |q * q + 2 * p * q                 , q * q + p * p    |

其中

new_p = q * q + p * p,
new_q = q * q + 2 * p * q

算法实现：

function fib(n) {
  function fib_iter(a, b, p, q, n) {
    return n === 0
           ? b
           : n % 2 === 0
             ? fib_iter(
               a, b,
               q * q + p * p,
               q * q + 2 * p * q,
               n / 2
               )
             : fib_iter(
               (p + q) * a + q * b,
               q * a + p * b,
               p, q,
               n - 1
               )
  }
  return fib_iter(1, 0, 0, 1, n)
}

针对这个问题，「循环不变式」可以被完全且简洁的表示出来：

T**N*V == (T**2)**(N/2)*V when N is even
T**N*V == T**(N-1)*(T*V) when N is odd

其中 T 代表 p, q 构成的转换矩阵，N 代表第几个 fib 数，V 代表 fib 对。