高速フィボナッチ

Scheme Programming

http://oss.timedia.co.jp/index.fcgi/kahua-web/show/ossz/oneline/2004-11-29
古い記事やけど、なんか最近知った。フィボナッチ数をO(log n)で計算するアルゴリズム。考えてみればフィボナッチ数の一般項とかでもn乗が入ってるから、あれをm^nの要領でO(log n)にまでオーダを落とせるような気がしないでもない感じか？
まぁ、このアルゴリズムは同じ要領でも全然理解できんのやが。状態変数pとqは一体何の意味だ…？

一応Schemeで書くとこんなんかなぁ。

(define (fib n)
  (let loop ((a 1) (b 0) (p 0) (q 1) (c n))
    (cond ((= c 0) b)
          ((even? c) (loop a
                           b
                           (+ (* p p) (* q q))
                           (+ (* 2 p q) (* q q))
                           (/ c 2)))
          (else (loop (+ (* b q) (* a q) (* a p))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- c 1)))
          )))

のあたりでteranishiさんが解説している。なるほどねー…。数式ぐにゃぐにゃやってますな。