Dan's Thoughts Thinking somewhat carefully

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 , 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*bⁿ 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
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