乐正

Actions speak louder than words.

Sicp-ex1-19

问题

存在着一种以对数步数求出斐波那契数的巧妙算法。请回忆在1.2.2节中fib-iter的 计算过程中状态变量a和b的变换规则,$a\leftarrow a+b$和$b\leftarrow a$,现在将这种 变换称为$T$变换。通过观察可以发现,从1和0开始将$T$反复应用$n$次方,将产生一对数 $Fib(n+1)$和$Fib(n)$。换句话说,斐波那契数可以通过将Tn(变换$T$的$n$次方)应用 于对偶$(1, 0)$而产生出来。现在将$T$看做是变换族$T_{pq}$中$p=0$和$q=1$的特殊情况。 其中$T_{pq}$是对于对偶$(a, b)$按照$a\leftarrow bq+aq+ap$和$b\leftarrow bp+aq$规 则的变换。请证明,如果我们应用变换$T_{pq}$两次,其效果等同于应用同样形式的一次 变换$T_{p’ q’}$,其中$p’$和$q’$可以由$p$和$q$计算出来。 这就指明了一条求出这种变换的平方的路径,使我们可以通过连续求平方的方式去计算Tn, 就像fast-expt过程里所做的那样。

解答

已知对于对偶$(a, b)$有变换$T_{pq}$为 $$ \begin{cases}a&\leftarrow bq+aq+ap \\ b&\leftarrow bp+aq \end{cases} $$

那么,对于$T_{pq}$的平方$(T_{pq})^2$来说,有变换 $$ \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} $$

得 $$ \begin{cases}a &\leftarrow b(q^2+2pq)+a(q^2+2pq)+a(p^2+q^2) \\ b&\leftarrow b(p^2+q^2)+a(q^2+2pq) \end{cases} $$

对比$T_{pq}$和$(T_{pq})^2$可以知道有变换$T_{p’q’}$,并且其中 $$ \begin{cases}p’ = p^2 + q^2 \\ q’ = q^2 + 2pq \end{cases} $$

因此,每当$N$为偶数的时候,可以通过应用变换$T_{p’q’}$来减少一半计算$T^N$的量。 所以可以得到如下的计算斐波那契数的函数

练习1.19 (ex1-19.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (fib 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))
                     (/ count 2)))
          (else (fib-iter (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q))
                          p
                          q
                          (- count 1)))))
  (fib-iter 1 0 0 1 n))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(fib 0)
;Value: 0

(fib 1)
;Value: 1

(fib 3)
;Value: 2

(fib 4)
;Value: 3

(fib 5)
;Value: 5

draft

« 计算机程序的构造和解释-习题解答 sicp-ex1-1 »

Comments