[SICP] 問題 1.19 : Fibonacci数を対数的ステップ数で計算する

Fibonacci数を対数的ステップ数で計算するうまいアルゴリズムがある. 1.2.2 節のfib-iterプロセスで使った状態変数aとbの変換: a ← a + bとb ← aに注意しよう. この変換をTと呼ぶ. 1と0から始め, Tを繰り返してn回作用させると, Fib(n + 1)とFib(n)の対が出来る. いいかえれば, Fibonacci数は対(1, 0)にTⁿ, つまり変換Tのn乗を作用させると得られる. さて, T_pqは対(a, b)をa ← bq + aq + apとb ← bp + aqに従って変換するものとし, Tを変換族T_pqのp = 0とq = 1の特例としよう. 変換T_pqを二回使うとその効果は同じ形式の変換T_p'q'を一回使ったのと同じになることを示し, p'とq'をp, qを使って表せ. これで変換を二乗する方法が得られ, fast-exptのように逐次平方を使い, Tⁿを計算することが出来る. これらをすべてまとめ, 対数的ステップ数の以下の手続きを完成せよ.

(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
                   ＜??＞      ; p'を計算
                   ＜??＞      ; q'を計算
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

変換T_pqは次のような行列として表現できます.

Tpq=	[	p+q	q	]
		q	p

変換T_p'q'はT_pq²となります. T_pq²を計算し整理すると次のようになります.

Tp'q'=	[	(p2+q2) + (2pq+q2)	2pq+q2	]
		2pq+q2	p2+q2

変換T_p'q'とT_pqを見比べると, p'とq'はpとqを用いて次のように表せます.

p'=	p2+q2
q'=	2pq+q2

上で求めたp'とq'を使って手続きを定義すると次のようになります. 計算結果を検証するために, p.22の手続きもfib0として定義します.

(require (lib "racket/trace.ss"))

(define (fib0 n)
  (define (iter a b count)
    (if (= count 0)
        b
        (iter (+ a b) a (- count 1))))
  (iter 1 0 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (+ (* 2 p q) (* q q))
                   (/ count 2)))
        (else
         (fib-iter (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (- count 1)))))

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

;;(trace fib-iter)

計算結果が正しいことを確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map fib0 '(0 1 2 3 4 5 6 7))
(0 1 1 2 3 5 8 13)
> (map fib '(0 1 2 3 4 5 6 7))
(0 1 1 2 3 5 8 13)
> 

トレースしてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fib 30)
>(fib-iter 1 0 0 1 30)
>(fib-iter 1 0 1 1 15)
>(fib-iter 2 1 1 1 14)
>(fib-iter 2 1 2 3 7)
>(fib-iter 13 8 2 3 6)
>(fib-iter 13 8 13 21 3)
>(fib-iter 610 377 13 21 2)
>(fib-iter 610 377 610 987 1)
>(fib-iter 1346269 832040 610 987 0)
<832040
832040
> 

トレースの結果を見ると, 対数的ステップ数で計算していることが分かります.