Exercise 1.16 of SICP

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