SICP問題1.19
T^1 の時の a bq + aq + ap T^2 の時の a (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p = bpq + a(q^2) + b(q^2) + a(q^2) + apq + bpq + apqq + a(p^2) = 2a(q^2) + 2apq + 2bpq + b(q^2) + a(p^2) = b((q^2) + 2pq)) + a((q^2) + 2pq) + a((p^2) + (q^2)) T^1 の時の b bp + aq T^2 の時の b (bp + aq)p + (bq + aq + ap)q = b(p^2) + apq + b(q^2) + a(q^2) + apq = a(q^2) + 2apq + b(p^2) + b(q^2) = b((p^2) + (q^2)) + a((q^2) + 2pq) よって p' = (p^2) + (q^2) q' = (q^2) + 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 (+ (square p) (square q)) (+ (square q) (double (* p q))) (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))) )
となる。