Saturday, July 3, 2010

フィボナッチ数列の行列的アルゴリズム

SICPの問題1.19から
フィボナッチ数列をO(log 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 p) (* q q))     ; compute p'
                   (+ (* 2 (* p q)) (* q q))      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

参考になるかどうか・・・

No comments: