excercise-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 1.2.2: $aleftarrow a +b$ and $bleftarrow 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 $n^{th}$ 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 $aleftarrow bq + aq + ap$ and $bleftarrow bp + aq$. Show that if we apply such atransformation $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-exptprocedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

Ans

证:

$T_{p,q}$ 对 $(a, b)$ 执行的转换为 $aleftarrow bq + aq + ap$ 和 $bleftarrow bp + aq$.
也即对 $(a,b)$ 以行列式 $begin{pmatrix}
p+q & p \
p & q
end{pmatrix}$ 做了一次乘法.

执行两次 $T{p,q}$ 也即对 $(a,b)$ 做两次行列式乘法,而 $(a,b)cdot T{p,q}cdot T{p,q}=(a,b)cdot (T{p,q}cdot T{p,q})=(a,b)cdot T{p,q}^2$

$begin{aligned}
T{p,q}^2
&=
begin{pmatrix}
p+q & q \
q & p
end{pmatrix}^2 \
&=
begin{pmatrix}
p+q & q \
q & p
end{pmatrix}
begin{pmatrix}
p+q & q \
q & p
end{pmatrix} \
&=
begin{pmatrix}
(p^2+q^2) + (q^2+2pq) & q^2+2pq \
q^2+2pq & p^2+q^2
end{pmatrix} \
&= T{p^2+q^2,q^2+2pq}
end{aligned}$

可知:
$begin{aligned}
p′&=p^2+q^2 \
q′&=q^2+2pq
end{aligned}$

完整的程序为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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