SICP Exercise 1.16: Iterative Exponentiation

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 (bn/2)² = (b²)^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 abⁿ 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.)

In order to help us produce an iterative version Abelson and Sussman provide us with a pretty big hint. Given that (b^n/2)² = (b²)^n/2, in what ways can we maintain the invariant quantity abⁿ while changing at least one of a, b and n? Well we can square b if we half n. We can also multiply a by b if we subtract 1 from n. I.e.

• abⁿ = a(b²)^n/2
• abⁿ = abb^n-1

These two relationships bear a pretty close resemblance to the ones given in section 1.2.4 where they are describing the successive squaring approach to calculating exponents. This is not surprising - we're simply multiplying both sides of the equation by a and then, in the first of the two, applying the transformation (b^n/2)² = (b²)^n/2.

So the first of these relationships gives us a way to maintain the invariant quantity when n is even while the second gives us a way to maintain it when n is odd. This gives us pretty much all we need to construct our iterative exponentiation process. The iterator itself will maintain a state variable, a, and will apply the above relationships appropriately to update the values of a, b and n until it has reduced n to 0. At this point a will hold the desired value as we have maintained the invariant quantity throughout and we have gone from an initial state of 1.bⁿ to ab⁰ = a.1 = a.

Here's my implementation:

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

And some examples of it in use:

> (fast-expt 2 5)
32
> (fast-expt 3 2)
9
> (fast-expt 4 10)
1048576
> (fast-expt 10 4)
10000