Solution to SICP Exercise 1.19

Structure and Interpretation of Computer Programs

Solution to Exercise 1.19:

Tqp is defined as:

abq + aq + ap
bbp + aq

If we apply Tpq to itself, we get T2pq:

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:

ab(2pq + q2) + a(2pq + q2) + a(p2 + q2)
bb(p2 + q2) + a(2pq + q2)

As we are looking for a transformation of the form

abq′ + aq′ + ap
bbp′ + aq

It should be fairly obvious that

p′ = p2 + q2
q′ = 2pq + q2

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