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

题目

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

(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$

翻译翻译"T"到底代表什么

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

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

引入p和q

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

  然后题目说，假设这里的$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''''',$...等等等，写太长会很难看，所以省略）

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

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

如何计算p'和q'

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

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

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

  对比$Expression1$和$Expression2$的右边可知：

算法的原理

To be determined