Solution to SICP Exercise 1.19

Solution to Exercise 1.19:

T_qp is defined as:

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

If we apply T_pq to itself, we get T²_pq:

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

With some manipulation, this can be rewritten as:

a ← b(2pq + q²) + a(2pq + q²) + a(p² + q²)
b ← b(p² + q²) + a(2pq + q²)

As we are looking for a transformation of the form

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

It should be fairly obvious that

p′ = p² + q²
q′ = 2pq + q²

Now we can modify our program:
(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
(sum-of-squares p q) ; compute p'
(+ (* 2 p q) (square q)) ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))

(define (square x)
(* x x))

(define (sum-of-squares x y)
(+ (square x) (square y)))