ochalog

Ruby と MediaWiki が好きな電子・情報系の学生のブログ。

SICP: Exercise 1.19

問題 1.19

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

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

計算機プログラムの構造と解釈 第二版 1.2.4 べき乗」より

まず \( p' \) と \( q' \) を計算する。

$$ \begin{align*} a' &\leftarrow bq + aq + ap \\ b' &\leftarrow bp + aq \\ \\ a'' &\leftarrow b'q + a'q + a'p \\ &= (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p \\ &= bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2 \\ &= b(pq + q^2 + pq) + a(q^2 + q^2 + pq + pq + p^2) \\ &= b(2pq + q^2) + a(2pq + q^2) + a(p^2 + q^2) \\ \\ b'' &\leftarrow b'p + a'q \\ &= (bp + aq)p + (bq + aq + ap)q \\ &= bp^2 + apq + bq^2 + aq^2 + apq \\ &= b(p^2 + q^2) + a(pq + q^2 + pq) \\ &= b(p^2 + q^2) + a(2pq + q^2) \end{align*} $$

以上より、係数を比較して

$$ \begin{cases} p' = p^2 + q^2 \\ q' = 2pq + q^2 \end{cases} $$

したがって、再帰呼び出しは以下のようにすればよい。

(fib-iter a
          b
          (+ (square p) (square q)) ; p' を計算
          (+ (* 2 p q) (square q))  ; q' を計算
          (/ count 2))

繰り返しプロセスの概要は

  • count が偶数のとき:\( a \) と \( b \) は固定しておく。\( p \) と \( q \) を変化させる。
  • count が奇数のとき:\( a \) と \( b \) に \( T \) を適用する。

となっている。