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
<strong>(sum-of-squares p q)</strong> ; compute p'
<strong>(+ (* 2 p q) (square q))</strong> ; 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)))
```

Posted by Ken Dyck in *Programming*