SICP Exercise 1.16: Fast Exponentiation

From SICP section 1.2.4 Exponentiation

Exercise 1.16 asks us to design an exponentiation procedure that evolves an iterative process using successive squaring and uses a logarithmic number of steps. A hint tells us to use the observation that (b^n/2)² = (b²)^n/2 and to keep, along with the exponent n and base b, an additional state variable a, and to define the state transformation in such a way that the product a * bn is unchanged from state to state. The value of a should start at 1, and should contain the final answer by the end of the process.

Earlier in section 1.2.4, we were given the procedure:

(define (even? n)
   (= (remainder n 2) 0))

which tests whether an integer is even. This will come in handy again for this exercise, since we'll need to adjust a by a different amount when n is even than when n is odd.

We'll also use the following simple procedure for squaring a number:

(define (square x)
   (* x x))

With those building blocks in place, we can define our iterative procedure.

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

We call the procedure expt-iter with the arguments base b, exponent n, and the state variable a. The first thing we do is check to see if the exponent is 0. If so, we've reached the end of the procedure and just return the value of a. Next we check to see if n is even. If it is, we use the observation that (b^n/2)² = (b²)^n/2 to transform state information by squaring b and dividing n by 2. Finally, if n is odd we transform state information by reducing n by 1 and multiplying a by the base b.

The only thing that's left to do is define a procedure that calls expt-iter with the correct initial values.

(define (fast-expt b n)
   (expt-iter b n 1))

Here are a few sample runs of the procedure:

> (fast-expt 2 2)
4
> (fast-expt 2 3)
8
> (fast-expt 2 10)
1024
> (fast-expt 3 3)
27
> (fast-expt 5 5)
3125

You can try running the procedure with large values of n to verify that it really is fast.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.