対数的ステップ数のフィボナッチ数列アルゴリズム

Scheme

以下は、ふつうのフィボナッチ数列のアルゴリズムです。

(define (fib n)
    (cond
        [(= n 0) 0]
        [(= n 1) 1]
        [else (+ (fib (- n 1)) (fib (- n 2)))]))

これを反復的になるように書き換えると以下のようになります。ステップ数は\mathcal{O}(n)です。

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

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

これをステップ数\mathcal{O}(\log n)にするには、どうしたらよいでしょうか。この問題がSICPの問題1.19です。解説してみます。

上の反復的アルゴリズムでは、(fib n)は、(a, b)=(1, 0)に対して変換Tをn回掛けたものです。



T\::\:a' \leftarrow a + b,\:b' \leftarrow a
さて、ここで、一般的な変換T_{pq}というものを考えてみましょう。


T_{pq}\::\:a' \leftarrow bq + aq + qp,\:b' \leftarrow bp + aq
つまり


T\:=\:T_{01}
です。
行列で表現すると


\begin{pmatrix}a'\\b'\end{pmatrix}\:=\:T_{pq}\begin{pmatrix}a\\b\end{pmatrix}, \: T_{pq} \:=\: \begin{pmatrix}p+q & q \\ q & p\end{pmatrix}
となります。
よって、


T_{p'q'}\:=\:(T_{pq})^{2}\:=\: \begin{pmatrix}p^{2}+2pq+2q^{2} & 2pq+q^{2}\\ 2pq+q^{2} & p^{2}+q^{2}\end{pmatrix}
となります。
したがって、


p'\:=\:p^{2}+q^{2},\:q'\:=\:2pq+q^{2}
となります。
このことを利用すれば、対数的ステップ数のフィボナッチ数列アルゴリズムが以下のように書けます。

(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
                             (+ (* p p) (* q q)) ; p'を計算
                             (+ (* 2 p q) (* q q)) ; q'を計算
                             (/ n 2))]
        [else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- n 1))]))