**Exercise 1.19:** There is a clever algorithm for computing the Fibonacci numbers in a logarithmic
number of steps. Recall the transformation of the state variables a and b in the `fib-iter`

process of section 1.2.2: `a <- a + b`

and `b <- a`

. Call this transformation `T`

, and observe
that applying `T`

over and over again `n`

times, starting with 1 and 0, produces the pair
Fib(n+1) and Fib(n). In other words, the Fibonacci numbers are produced by applying T^{n},
the n^{th} power of the transformation `T`

, starting with the pair (1,0).
Now consider T_{pq} to be the special case of `p = 0`

and `q = 1`

in a family of
transformations T_{pq}, where T_{pq} transforms the pair (a,b) according to
`a <- bq + aq + ap`

and `b <- bp + aq`

.

Show that if we apply such a transformation T_{pq} twice, the effect is the same as
using a single transformation T_{p’q’} of the same form, and compute `p'`

and `q'`

in terms
of `p`

and `q`

. This gives us an explicit way to square these transformations, and thus we can
compute Tn using successive squaring, as in the `fast-expt`

procedure. Put this all together
to complete the following procedure, which runs in a logarithmic number of steps:

```
(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
?? ;; compute p'
?? ;; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
```

Definition of a_{1} and b_{1}:

$$ a_1 \leftarrow bq + aq + ap $$

$$ b_1 \leftarrow bp + aq $$ $$ T^2_{pq} = T_{p’q’} $$ $$ a_1 = bq + aq + ap $$ $$ b_1 = bp + aq $$ $$ a_2 = b_1q + a_1q + a_1p $$ $$ b_2 = b_1p + a_1q $$

The key here is to substitute from the definition of a_{1} and b_{1} into a_{2}
and b_{2} in order to get `p'`

and `q'`

I start with b_{2} because the expression is simpler to work with. The values I get
for `p'`

and `q'`

must also work with a_{2}

$$ b_2 = b_1p + a_1q = (bp+aq)p + (bq+aq+ap)q $$

$$ b_2 = bp^2+aqp + bq^2+aq^2+aqp $$

$$ b_2 = b(p^2+ q^2)+a(2qp+q^2) $$

$$ p’=(p^2+ q^2) $$

$$ q’= (2qp+q^2) $$

$$ b_2 = bp’+aq’ $$

a_{2} is trickier to check because of the number of terms, I’ll take a few short cuts here in showing the math

$$ a_2 = bpq + aq^2 + bq^2 + aq^2 + aqp + bqp + aqp + ap^2 $$

$$ a_2 = b(2qp+q^2) + a(2qp+q^2) + a(p^2+ q^2) $$

$$ a_2 = bq’+aq’+ap’ $$

Finally: \( T^2_{pq} = T_{p’q’} \) where \( p’= p^2 + q^2 \) and \( q’= 2qp + q^2 \)

```
(define (square x) (* x x))
(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)) ; 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)))))
```

```
> (fib 10)
55
> (fib 100)
354224848179261915075
```