問題1.19

フィボナッチ数計算の対数ステップ版を作れ
答えを見ながら証明してみましたが、正直理解しきれていないなあ...。

a = bq + aq + ap
b = bp + aq

a' = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
   = bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2
   = a(q^2 + q^2 + pq + pq + p^2) + b(pq + q^2 + pq)
   = a(p^2 + 2q^2 + 2pq) + b(q^2 + 2pq)
   = b(q^2 + 2pq) + a(q^2 + 2pq) + a(p^2 + q^2)

b' = (bp + aq)p + (bq + aq + ap)q
   = bp^2 + apq + bq^2 + aq^2 + apq
   = apq + aq^2 + apq + bp^2 + bq^2 
   = a(2pq + q^2) + b(p^2 + q^2)
   = b(p^2 + q^2) + a(q^2 + 2pq)

ここで、

p' = p^2 + q^2
q' = q^2 + 2pq

とすると

a' = bq' + aq' + ap'
b' = bp' + aq'

となる。

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