高速Fibonacci数の計算

Scheme

{ \displaystyle T_{pq}は(a,b)をa\leftarrow bq+aq+apとb\leftarrow bp+aqの写像とする.\\ T_{pq}を２回作用させると同じ形式のT_{p'q'}を１回作用させたときと同じ効果を及ぼすことの証明\\ T_{pq}を(a,b)に１回作用させると\\ (a,b)\rightarrow(bq+aq+ap,bp+aq)\\ T_{pq}を(bq+aq+ap,bp+aq)に作用させると\\ (bq+aq+ap,bp+aq)\rightarrow(b(q^{2}+2pq)+a(q^2+2pq)+a(q^2+p^2),\ b(p^{2}+q^{2})+a(q^{2}+2pq))\\ よってp'=p^{2}+q^{2}, q' = q^{2}+2pqとすればT_{pq}を２回作用させた変換と同等の変換が得られる. }

これを使ってFibonacci数の計算を高速に行うことができる.

(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));p'
                   (+ (* q q) (* 2 p q));q'
                   (/ count 2)))
        (else;奇数だったら素直に１回分の変換
         (fib-iter (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (- count 1)))))