练习1.19

$T_{pq}$ :

$\begin{array}{ll} a \leftarrow bq+a(p+q)\\ b \leftarrow bp+aq \end{array}$

$T_{p\prime q\prime} = (T_{pq})^2$ :

$\begin{array}{ll} a \leftarrow (bp+aq)q+(bq+a(p+q))(p+q)=b(2pq+q2)+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{array}$

通过对比可以发现：

$\left\{ \begin{array}{ll} p\prime=p^2+q^2\\ q\prime=2pq+q^2 \end{array} \right.$

由此 根据题目描述 可以完成快速计算斐波那契数列的程序

(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
                   (+ (square p) (square q))     ; compute p'
                   (+ (* 2 p q) (square q))      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

以下是计算第100个斐波那契数的过程

(fib 100)
(fib-iter 1 0 0 1 100)
(fib-iter 1 0 1 1 50)
(fib-iter 1 0 2 3 25)
(fib-iter 5 3 2 3 24)
(fib-iter 5 3 13 21 12)
(fib-iter 5 3 610 987 6)
(fib-iter 5 3 1346269 2178309 3)
(fib-iter 24157817 14930352 1346269 2178309 2)
(fib-iter 24157817 14930352 6557470319842 10610209857723 1)
(fib-iter 573147844013817084101 354224848179261915075 6557470319842 10610209857723 0)
354224848179261915075

由于时间复杂度为对数 所以计算过程迭代非常迅速 效率非常高