**Exercise 1.16:** Design a procedure that evolves an iterative exponentiation process that uses successive squaring
and uses a logarithmic number of steps, as does `fast-expt`

. (Hint: Using the observation that
\( (b^{\frac{n}{2}})^2 = (b^2)^{\frac{n}{2}} \), keep, along with the exponent `n`

and the base `b`

,
an additional state variable `a`

, and define the state transformation in such a way that the product a*bn
is unchanged from state to state. At the beginning of the process `a`

is taken to be 1, and the answer is
given by the value of a at the end of the process. In general, the technique of defining an invariant quantity
that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

```
(define (square x) (* x x))
(define (fast-expt-iter b n a)
(cond ((= n 0) a)
((even? n) (fast-expt-iter (square b) (/ n 2) a))
(else
(fast-expt-iter b (- n 1) (* b a)))))
```

For me the thing to notice about this algorithm is the following property: Notice how when the exponent n is odd
\( b^{7} = b \cdot (b^{6}) = b \cdot (b^2 \cdot (b^{4})^1) \) All the `b`

’s outside the parenthesis get
accumulated in the state variable a of the algorithm.

If b = 2 n = 7

```
(fast-expt-iter 2 7 1)
(fast-expt-iter 2 6 2)
(fast-expt-iter 4 3 2)
(fast-expt-iter 4 2 8)
(fast-expt-iter 16 1 8)
(fast-expt-iter 16 0 128)
128
```