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 $ を適用する。

となっている。

ochalog

RubyとMediaWikiとIRCが好き。

SICP: Exercise 1.19

問題 1.19