SICP問題1.19

最近、さぼっていたが、少しずつ再開。

今回の問題は
フィボナッチ数列に関する問題

(define (fib-iter a b count)
 (if (= count 0)
     b
     (fib-iter (+ a b) a (- count 1))))

が

a←a+b　b←a

となる変換Tに関する問題
長くなるので少し端折るが*1
要するに

a←bq+aq+ap　b←bp+aq
(p=0 q=0)

変換Tpqを使って

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

の

<p'> <q'>

を求める問題。
なお
Tp'q'の変換はTpqの変換を2回行ったのと同じ…

a',b'はTpq
a",b"はTp'q'の値として、

Tpq

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

Tp'q'

a"←b'q+a'q+a'p
b"←b'p+a'q

となる。

さらにa',b'を展開すると

Tp'q'

a"←(bp+aq)q+(bq+aq+ap)q+(bq+aq+ap)p
b"←(bp+aq)p+(bq+aq+ap)q

a"←b(2pq+q^2)+a(2pq+q^2)+a(q^2+p^2)
b"←b(p^2+q^2)+a(2pq+q^2)

ここでaとbを不変な値として
Tpqの変換で求められるp',q'を使用して表すと

a"←bq'+aq'+ap'
b"←bp'+aq'

となるので、ここまでの計算結果を用いると、

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

となる。

*1:P26参照のこと