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