計算機プログラムの構造と解釈 第二版 P26 問題1.19

計算機プログラムの構造と解釈 第二版
P26 問題1.19
すごく難しかったが、
割とよくできたと思うので、結果を乗せておきます。

(Tpq)^2 = Tp'q'
なので、Tpq を二回実行して、比較してみれば、p' q'は、もとまる。 

Tpqを一回実行した結果の対をA B とすると、
A = bq + aq + ap
B = bp + aq

Tpqの二回目の実行を行った結果の対を A' B'とすると、
A' = Bq + Aq + Ap
B' = Bp + Aq

B'を用いて比較を行う。B'を展開すると
B' = Bp + Aq
B' = (bp + aq)p + (bq + aq + ap)q
B' = bpp + apq + bqq + aqq + apq
B' = b(pp + qq) + a(qq + 2pq)

ここで、
B'= bp' + aq'
であるから。
B' = b(pp + qq) + a(qq + 2pq)
と比較すると、

p' = pp + qq
q' = qq + 2pq


(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)))))