読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

高速Fibonacci数の計算

Scheme

{ \displaystyle
T_{pq}は(a,b)をa\leftarrow bq+aq+apとb\leftarrow bp+aqの写像とする.\\
T_{pq}を2回作用させると同じ形式のT_{p'q'}を1回作用させたときと同じ効果を及ぼすことの証明\\

T_{pq}を(a,b)に1回作用させると\\
(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}を2回作用させた変換と同等の変換が得られる.
}

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