フィボナッチ数列を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:
Post a Comment