問題1.19

定義により、(Tpq)^2は

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

であり、これがTp'q'と等しいのであれば、

bq' + aq' + ap' = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
bp' + aq' = (bp + aq)p + (bq + aq + ap)q

が成り立つ。この連立方程式を解くと、

aq' = (bp + aq)p + (bq + aq + ap)q - bp'
 q' = (bp^2 + bq^2 - bp') / a + q^2 + 2pq

b{(bp^2 + bq^2 - bp') / a + q^2 + 2pq} + a{(bp^2 + bq^2 - bp') / a + q^2 + 2pq} + ap'
  = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
(a^2 - b^2 - ab)p' = (a^2 - b^2 - ab)p^2 + (a^2 - b^2 - ab)q^2
                p' = p^2 + q^2

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

となり、p' = p^2 + q^2、q' = q^2 + 2pqのとき、(Tpq)^2 = Tp'q'は成立する。

手続きfibの定義は以下の通り。

(5am:test exercise-1.19
  (5am:is (= 0 (fib 0)))
  (5am:is (= 1 (fib 1)))
  (5am:is (= 5 (fib 5)))
  (5am:is (= (fib 10)
             (+ (fib 8) (fib 9)))))

(defun square (x)
  (* x x))

(defun fib-iter (a b p q count)
  (cond ((zerop count) b)
        ((evenp count)
         (fib-iter a
                   b
                   (+ (square p) (square q))
                   (+ (square q) (* 2 p q))
                   (/ count 2)))
        (t (fib-iter (+ (* b q) (* a q) (* a p))
                     (+ (* b p) (* a q))
                     p
                     q
                     (1- count)))))

(defun fib (n)
  (fib-iter 1 0 0 1 n))