Monday, January 11, 2010

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 (bn/2)2 = (b2)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 (bn/2)2 = (b2)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)
> (fast-expt 2 3)
> (fast-expt 2 10)
> (fast-expt 3 3)
> (fast-expt 5 5)

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


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


pbewig said...

The ipow function in my Standard Prelude does this using exactly the same algorithm:

(define (ipow b e)
  (cond ((zero? e) 1)
        ((even? e) (ipow (* b b) (/ e 2)))
        (else (* b (ipow (* b b) (/ (- e 1) 2))))))

Bill the Lizard said...

There's a lot of really useful stuff in your Standard Prelude. That will probably be the first place I look for hints if I get stuck on any SICP exercises. I can already tell it will come in handy when I get to the next chapter, which deals with data abstraction.

geeknanny said...

pbewig's ipow function isn't tail-recursive, is it? The else condition calls ipow and then multiplies the result by b. Rewriting the function to be tail-recursive is the whole point of the exercise, yes?

Bill the Lizard said...

You're absolutely right. The tail-call version will be more efficient in both time and (stack) space for most exponents. (They'll run virtually the same for exponents that are powers of 2.)

I hadn't noticed this before, thanks for pointing it out.

Anonymous said...

If you subtract 1 from n, the product b*n is not invariant. Is this correct?

Anonymous said...

I apologize, there is a problem with my browser, the text shows up as:

"the product a bn is unchanged"

In your example: a * (b ^ n) is invariant, which is correct.