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^{2}_{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*(2*pq* + *q*^{2}) + *a*(2*pq* + *q*^{2}) + a(*p*^{2} + *q*^{2})

*b* ← *b*(*p*^{2} + *q*^{2}) + a(2*pq* + *q*^{2})

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*^{2} + *q*^{2}

*q*′ = 2*pq* + *q*^{2}

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