※ 引述《hijkxyzuw (i,j,k) ×(x,y,z)》之铭言：
: 最近在读 sicp ，在 1-2-4 章，
: 有介绍一种将 n 次计算简化为 log(n) 次的作法。
: 他应用在费氏数列上，但他使用的费氏数列算法我看不懂……。
: 原文：
: > *Exercise 1.19:* There is a clever algorithm for computing the
: > Fibonacci numbers in a logarithmic number of steps. Recall the
: > transformation of the state variables a and b in the 'fib-iter'
: > process of section *note 1-2-2::: a <- a + b and b <- a. Call this
: > transformation T, and observe that applying T over and over again n
: > times, starting with 1 and 0, produces the pair _Fib_(n + 1) and
: > _Fib_(n). In other words, the Fibonacci numbers are produced by
: > applying T^n, the nth power of the transformation T, starting with
: > the pair (1,0). Now consider T to be the special case of p = 0 and
: > q = 1 in a family of transformations T_(pq), where T_(pq)
: > transforms the pair (a,b) according to a <- bq + aq + ap and b <-
: > bp + aq. Show that if we apply such a transformation T_(pq) twice,
: > the effect is the same as using a single transformation T_(p'q') of
: > the same form, and compute p' and q' in terms of p and q. This
: > gives us an explicit way to square these transformations, and thus
: > we can compute T^n using successive squaring, as in the 'fast-expt'
: > procedure. Put this all together to complete the following
: > procedure, which runs in a logarithmic number of steps:(5)
因为矩阵乘法(or 线性变换的合成)符合结合律
他的意思是说, 观察 a' = a + b
b' = a
这个算式, 发现用矩阵来表达的话(发现他是个线性变换):
( F_{n+2} ) = ( 1 1 ) ( F_{n+1} )
( F_{n+1} ) ( 1 0 ) ( F_n )
要把 F 前进几项就是把中间的方阵乘在左边几次. 但是因为他有结合律,
可以先把中间的方阵用 A^{2n} = ( A^n )^2 A^{2n+1} = A ( A^n )^2
的方式快速幂, 复杂度变 log n