# Page 201 : 专栏 更快地计算递归式

## 从问题本身推演到矩阵乘积（`O(m ^ 3 * log n)`）

``````Fn = Fn-1 + Fn-2
``````

``````fn = a1 * fn-1 + a2 * fn-2 ...
``````

``````Ai = a1 * Ai-1 + b1 * Bi-1 ...
Bi = a2 * Ai-1 + b2 * Bi-1 ...
...
``````

f1跟原递推式不同的地方在于它是一个变换，有统一的输入和输出。

``````f3(x) = f1(f1(f1(x)))
``````

``````f3 = f1 · f1 · f1 = f1 ^ 3
``````

``````fn = f1 ^ n
``````

``````fi+j = fi · fj
``````

``````c = a + b
d = a
``````

``````c = 1 * a + 1 * b
d = 1 * a + 0 * b
``````

``````c = p * a + q * b
d = s * a + t * b
``````

``````c = pi * (pj * a + qj * b) + qi * (sj * a + tj * b)
d = si * (pj * a + qj * b) + ti * (sj * a + tj * b)
``````

``````c = a * (pi * pj + qi * sj) + b * (pi * qj + qi * tj)
d = a * (si * pj + ti * sj) + b * (si * qj + ti * tj)
``````

``````pi+j = pi * pj + qi * sj
qi+j = pi * qj + qi * tj
si+j = si * pj + ti * sj
ti+j = si * qj + ti * tj
``````

``````[pi+j, qi+j]        [pi, qi]        [pj, qj]
=                *
[si+j, ti+j]        [si, ti]        [sj, tj]
``````

## `O(m ^ 2)`

``````Fn = a * Fn-1 + b * Fn-2 ...
``````

`m=2`时，p，q维护了一条轨道，s，t维护一条。

m条轨道的意义在于我们必须维护m个值以支持变换操作。

``````Fn = a * Fn-1 + b * Fn-2 ...
``````

``````Fm+1 = f1(F1 ... Fm)
``````

``````F2m-1 = f1(Fm-1 ... F2m-2)
``````

``````Fx+j = fi(Fj ... Fj+m)
``````

``````Fy = fj(Fx ... Fx+m)
``````

### 以斐波那契为例

``````//任意的初值组
a
b

//初值拓展所使用的常数，就是f1的结构
p1 = 1
q1 = 1
``````

``````c = p1 * a + q1 * b
``````

`fi{pi, qi}`变换

``````x = pi * a + qi * b
y = pi * b + qi * c
``````

`fj{pj, qj}`变换

``````z = pj * x + qj * y
``````

``````pj * x  = pj * (pi * a + qi * b)
= pi * pj * a + qi * pj * b

qi * c  = qi * (p1 * a + q1 * b)
= p1 * qi * a + q1 * qi * b

qj * y  = qj * (pi * b + qi * c)
= qj * (pi * b + p1 * qi * a + q1 * qi * b)
= p1 * qi * qj * a + pi * qj * b + q1 * qi * qj * b

z       = pi * pj * a + qi * pj * b
+ p1 * qi * qj * a + pi * qj * b + q1 * qi * qj * b
= (pi * pj + p1 * qi * qj) * a
+ (2 * qi * pj + q1 * qi * qj) * b
``````

``````pi+j = pi * pj + p1 * qi * qj
qi+j = 2 * qi * pj + q1 * qi * qj
``````

``````Fn = a * Fn-1 + b * Fn-2 ...
``````