高中读完我就把数学都忘光了，看SICP的习题1.19硬是看不明白，网上找了好久，有幸看到一篇文章说得很详细，下面是我看完此文章后的个人理解。

斐波那契的定义

F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-1) + F(n-2), & \text{if } n > 1 \end{cases}

题目

题目给出以下代码要我们补全：

(define (fib n)
   (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
   (cond ((= count 0) b)
         ((even? count)
          (fib-iter a
                    b
                    <??>      ; compute p'
                    <??>      ; compute q'
                    (/ count 2)))
         (else (fib-iter (+ (* b q) (* a q) (* a p))
                         (+ (* b p) (* a q))
                         p
                         q
                         (- count 1)))))

先理解普通算法

最原始的解法，从F(0)和F(1)开始，运算n次才能算出F(n)和F(n+1)：

  • F(2) = F(1) + F(0)
  • F(3) = F(2) + F(1)
  • F(4) = F(3) + F(2)
  • ...
  • F(n) = F(n-1) + F(n-2)
  • F(n+1) = F(n) + F(n-1) \leftarrow stop

翻译翻译&quot;T&quot;到底代表什么

题目给出了一个很巧妙的算法，可以降低时间复杂度到O(logn)。由于我的数学水平差，所以这里先不考虑算法的原理是什么，只考虑：这个算法是怎么运作的。 对于任意一个斐波那契对，我们假设左边较大的是a，右边较小的是b。例如假设F(6) = a,F(5) = b。那么对于下一对新的序列F(7)=a'和F(6)=b'：

\begin{cases} a' \leftarrow a + b \\ b' \leftarrow a \end{cases}

我们把这种将a,b转化为a',b'的转化方式记为T(ab)。那么对于原始的计算斐波那契的方式，等价于执行n次T(ab)——即T(ab)^{n}。

引入p和q

题目这里开始不说人话了，无缘无故引入了两个变量p和q，并且给出了一个新的转化方式，我们称为T(abpq)：

\begin{cases} a' \leftarrow bq + aq + ap \\ b' \leftarrow bp + aq \end{cases}

然后题目说，假设这里的p = 0,q = 1，那么这个表达式和上面的表达式是等价的，这不是屁话吗？！ 最难理解的地方来了。题目又说：有一种方式可以由p和q计算出p'和q'，新的p'和q'的作用是一次性执行两次T，即T(abp'q')=T(T(abpq))，至于为什么，我也不知道。 例如我们要计算F(11)，原始解法是T(ab)^{11}，过程如下：（第四步应该为a''',b'''，第五步应该为a'''',b''''，第六步应该为a''''',...等等等，写太长会很难看，所以省略）

\begin{array}{c} F(1) + F(0)，剩余T(ab)^{11} \\ \downarrow \\ F(2) + F(1)，剩余T(a'b')^{10} \\ \downarrow \\ F(3) + F(2)，剩余T(a''b'')^{9} \\ \downarrow \\ F(4) + F(3)，剩余T(ab)^{8} \\ \downarrow \\ F(5) + F(4)，剩余T(ab)^{7} \\ \downarrow \\ F(6) + F(5)，剩余T(ab)^{6} \\ \downarrow \\ F(7) + F(6)，剩余T(ab)^{5} \\ \downarrow \\ F(8) + F(7)，剩余T(ab)^{4} \\ \downarrow \\ F(9) + F(8)，剩余T(ab)^{3} \\ \downarrow \\ F(10) + F(9)，剩余T(ab)^{2} \\ \downarrow \\ F(11) + F(10)，剩余T(ab)^{1} \\ \downarrow \\ F(12) + F(11)，剩余T(ab)^{0} \\ \end{array}

而它这个解法，过程如下：

\begin{array}{c} F(1) + F(0)，剩余T(abpq)^{11} \leftarrow 指数是奇数，p和q不变 \\ \downarrow \\ F(2) + F(1)，剩余T(a'b'pq)^{10} \leftarrow 偶数，第一次计算p'和q'，并且n/2 \\ \downarrow \\ F(7) + F(6)，剩余T(a''b''p'q')^{5} \leftarrow 奇数，p'和q'不变 \\ \downarrow \\ F(8) + F(7)，剩余T(a'''b'''p'q')^{4} \leftarrow 第二次计算p''和q''，并且n/2 \\ \downarrow \\ F(10) + F(9)，剩余T(a''''b''''p''q'')^{2} \leftarrow 第三次计算p'''和q'''，并且n/2 \\ \downarrow \\ F(11) + F(10)，剩余T(a'''''b'''''p'''q''')^{1} \leftarrow 奇数，p'''和q'''不变 \\ \downarrow \\ F(12) + F(11)，剩余T(a''''''b''''''p'''q''')^{0} \leftarrow 结束 \\ \end{array}

注意这里的过程，p,q的值和a,b一样是迭代计算的，如果指数是奇数——则p,q不变，如果指数是偶数——则算出新的p',q'作为下一步迭代。

如何计算p&#39;和q&#39;

注意：只有指数是偶数的情况下，才需要计算p',q' 已知T(T(abpq)) \xrightarrow{~~} T(abp'q')，我们把表达式左边计算出来，就可以得到p',q'了。先通过T把T(T(abpq))计算出来：

\begin{array}{c} T(T(abpq)) \\ \downarrow \\ \begin{cases} a' \leftarrow bq + aq + ap \\ b' \leftarrow bp + aq \end{cases} \\ \downarrow \\ \begin{cases} a'' \leftarrow b'q + a'q + a'p \\ b'' \leftarrow b'p + a'q \end{cases} \\ \downarrow \\ Expression1 = \begin{cases} a'' \leftarrow (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p \\ b'' \leftarrow (bp + aq)p + (bq + aq + ap)q \end{cases} \\ \end{array}

T(abp'q')同样可以通过T计算为：

\begin{array}{c} T(abp'q') \\ \downarrow \\ Expression2 = \begin{cases} a'' \leftarrow bq' + aq' + ap' \\ b'' \leftarrow bp' + aq' \end{cases} \\ \end{array}

用观察法，可以把上面复杂的Express1改写为：

\begin{array}{c} Expression1 = \begin{cases} a'' \leftarrow (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p \\ b'' \leftarrow (bp + aq)p + (bq + aq + ap)q \end{cases} \\ \downarrow \\ Expression1 = \begin{cases} a'' \leftarrow b(2pq + qq) + a(2pq + qq) + a(pp+qq) \\ b'' \leftarrow b(pp+qq) + a(2pq + qq) \end{cases} \\ \end{array}

对比Expression1和Expression2的右边可知：

\begin{array}{c} \begin{cases} bq' + aq' + ap' = b(2pq + qq) + a(2pq + qq) + a(pp+qq) \\ bp' + aq' = b(pp+qq) + a(2pq + qq) \end{cases} \\ \downarrow \\ \begin{cases} p' = (pp+qq) \\ q' = (2pq + qq) \end{cases} \end{array}

算法的原理

To be determined