SICP

Exercise 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: a a + b and b 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 Tn, the nth 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 Tpq, where Tpq transforms the pair (a,b) according to a bq + aq + ap and b bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp’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 Tn using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:

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

本题实现了对数时间复杂度求 Fibonacci 数。

对于 Fibonacci 数 $0, 1, 1, 2, 3, 5, 8, 13, \dots$ 我们知道已经有如下的一个转换

$$ T \left\{\begin{aligned} a_2 & \leftarrow a_1 + b_1 \\ b_2 & \leftarrow a_1 \\ \end{aligned} \right. $$ 对于新的公式 $T_{pq}$

$$ T_{pq} \left\{\begin{aligned} a_2 & \leftarrow b_1q + a_1q + a_1p \\ b_2 & \leftarrow b_1p + a_1q \\ \end{aligned} \right. $$ 我们能求出 $a_3, b_3$ 来：

$$ T{pq} \left\{\begin{aligned} a_3 & \leftarrow b_2q + a_2q + a_2p \\ b_3 & \leftarrow b_2p + a_2q \\ \end{aligned} \right. $$ 即

$$ T{pq} \left\{\begin{aligned} a_3 &\leftarrow b_2q + a_2q + a_2p \\ &\leftarrow (b_1p+a_1q)q+(b_1q+a_1q+a_1p)q+(b_1q+a_1q+a_1p)p \\ &\leftarrow b_1(q^2+2pq)+a_1(q^2+2pq) + a_1(p^2+q^2)\\ b_3 & \leftarrow b_2p + a_2q \\ & \leftarrow (b_1p+a_1q)p+(b_1q+a_1q+a_1p)q \\ & \leftarrow b_1(p^2+q^2) + a_1(q^2+2pq) \end{aligned} \right. $$ 我们要去寻找的 a3 b3 与 a1 b1 之间的关系就得到了，然后用 q’ 与 p’ 来表示：

$$ T{pq} \left\{\begin{aligned} a_3 &\leftarrow b_1(q^2+2pq)+a_1(q^2+2pq) + a_1(p^2+q^2)\\ &\leftarrow b_1q’ + a_1q’ + a_1p’; \\ b_3 &\leftarrow b_1(p^2+q^2) + a_1(q^2+2pq) \\ &\leftarrow b_1p’ + a_1q’ \\ \end{aligned} \right. $$ 于是得到了 p’ 是 $p^2+q^2$, q’ 是 $q^2+2pq$ 。

补充我们的程序就很简单了：

(define (fib-new n)
  (define (fib-iter a b p q count)
    (cond ((= count 0) b)
          ((even? count)
           (fib-iter a
                     b
                     (+ (* p p) (* q q))
                     (+ (* q 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))

; for testing
(define (fib n)
  (define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))  
  (fib-iter 1 0 n))


;;; tests begin
(load "../testframe.scm")

(for-each (lambda (x)
            (assert= (fib x) (fib-new x)))
          '(1 2 3 4 5 6 7 8 9 10))

SICP 全笔记