理系学生日記

おまえはいつまで学生気分なのか

問題1.19

Fibonacci数をO(log n)で求めるアルゴリズムがあるとかないとかで,なんかがんばれとか書かれている。
T_{pq}: a\leftarrow bq+aq+ap, b\leftarrow bp+aqという変換があるとすると,その変換を2回すると、a\leftarrow b(2pq+q^2)+a(2pq+q^2)+a(p^2+q^2), b\leftarrow b(p^2+q^2)+a(2pq+q^2)とかなるので,T_{pq}を2度繰り返す変換T_{p'q'}は、p'=p^2+q^2,q'=2pq+q^2とかでかけるみたいです。これをschemeでかく。

(define (square x) (* x x))

(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
		   (+ (square p) (square q))
		   (+ (* 2 p q) (square q))
		   (/ count 2)))
	(else (fib-iter (+ (* b q) (* a q) (* a p))
			(+ (* b p) (* a q))
			p
			q
			(- count 1)))))