已知对于对偶 (a, b) ，有变换 T_{pq} 为 \begin{cases}a&\leftarrow\ bq+a(p+q), \\ b&\leftarrow\ bp+aq. \end{cases}
那么对于 T_{pq} 的平方 (T_{pq})^2 来说，有变换 \begin{cases}a&\leftarrow\ (bp+aq)q + (bq + a(p + q))(p + q) = b(2pq + q^2) + a(p^2 + q^2 +2pq + q^2), \\ b&\leftarrow\ (bp+aq)p + (bq + a(p+q))q = b(p^2 + q^2) + a(2pq + q^2). \end{cases}
通过对比 T_{pq} 和 (T_{pq})^2 ，可以得出变换 T_{p'q'} ，其中 p' = p^2 + q^2 并且 q' = 2pq + q^2 。
因此，每次当 N 为偶数时，我们可以通过应用变换 T_{p'q'} 来减少一半计算 T^N 所需的计算量，从而得出对数复杂度的斐波那契计算函数：
.. literalinclude:: code/19-fib-in-log-time.scm
测试：
1 ]=> (load "19-fib-in-log-time.scm") ;Loading "19-fib-in-log-time.scm"... done ;Value: fib-iter 1 ]=> (fib 0) ;Value: 0 1 ]=> (fib 5) ;Value: 5 1 ]=> (fib 8) ;Value: 21
.. seealso:: 本题的答案来自 Math Help Forum 的一篇帖子： `http://mathhelpforum.com/number-theory/179966-o-log-n-algorithm-computing-fibonacci-numbers-sicp-ex-1-19-a.html <http://mathhelpforum.com/number-theory/179966-o-log-n-algorithm-computing-fibonacci-numbers-sicp-ex-1-19-a.html>`_
.. seealso:: Design and Analysis of Algorithms 课程的一篇笔记分别给出了指数、线性和对数三种复杂度的斐波那契算法实现（C 语言）和相应的算法分析： `http://www.ics.uci.edu/~eppstein/161/960109.html <http://www.ics.uci.edu/~eppstein/161/960109.html>`_\ 。
.. seealso:: 这道练习引用自《Programming：the derivation of algorithms》一书的 5.2 节： `http://book.douban.com/annotation/17994049/ <http://book.douban.com/annotation/17994049/>`_ 。