练习 1.19¶

已知对于对偶 \((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\) 所需的计算量，从而得出对数复杂度的斐波那契计算函数：

;;; 19-fib-in-log-time.scm

(define (fib n)
    (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q n)
    (cond ((= n 0)
            b)
          ((even? n)
            (fib-iter a 
                      b
                      (+ (square p) (square q))     ; 计算 p'
                      (+ (* 2 p q) (square q))      ; 计算 q'
                      (/ n 2)))
          (else
            (fib-iter (+ (* b q) (* a q) (* a p))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- n 1)))))

测试：

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

Navigation

练习 1.19¶

讨论 ¶

Navigation