SICPの宿題

SICP

問題1.19

Tをn回作用させた時のa, bを a_{n}, b_{n}とすると a_{n+1}, b_{n+1}は
a_{n+1} = b_{n}q + a_{n}q + a_{n}p
b_{n+1} = b_{n}p + a_{n}q
となる。
さらに、もう一回Tを作用させたとき a_{n+2}, b_{n+2}は
a_{n+2}
= b_{n+1}q + a_{n+1}q + a_{n+1}p
= (b_{n}p + a_{n}q)q + (b_{n}q + a_{n}q + a_{n}p)q + (b_{n}q + a_{n}q + a_{n}p)p
= b_{n}(2pq + q^{2}) + a_{n}(2pq + q^{2}) + a_{n}(p^{2} + q^{2})
b_{n+2}
= b_{n+1}p + a_{n+1}q
= (b_{n}p + a_{n}q)p + (b_{n}q + a_{n}q + a_{n}p)q
= b_{n}(p^{2} + q^{2}) + a_{n}(2pq + q^{2})
これから
p' = p^{2} + q^{2}, q' = 2pq + q^{2}
とすると、 T_{pq}を２回作用させるのは、 T_{p'q'}を１回作用させるのと同じになる。

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

実行結果

gosh> (fib 3)
2
gosh> (fib 4)
3
gosh> (fib 5)
5
gosh> (fib 6)
8
gosh> (fib 7)
13
gosh> (fib 8)
21