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

^{2}= (b

^{2})

^{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 * b`^{n}

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

^{2}= (b

^{2})

^{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.

## 6 comments:

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

pbewig,

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.

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?

geeknanny,

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.

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

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.

Post a Comment