## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.16

## Problem

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

(*b*^{n / 2})^{2} = (*b*^{2})^{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 *a**b*^{n} 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.)

## Solution

The recursive version of fast-expt is:

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

For the iterative implementation, we use a helper procedure which implements the hint given in the text.

(define (fast-expt b n) (fast-expt-iter b n 1)) (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) (* a b)))))

Tests:

(fast-expt 2 0)

*Output:*

`
`

1

(fast-expt 2 1)

*Output:*

`
`

2

(fast-expt 2 2)

*Output:*

`
`

4

(fast-expt 2 3)

*Output:*

`
`

8

(fast-expt 2 4)

*Output:*

`
`

16

(fast-expt 2 5)

*Output:*

`
`

32

(fast-expt 2 6)

*Output:*

`
`

64

(fast-expt 2 7)

*Output:*

`
`

128

(fast-expt 2 8)

*Output:*

`
`

256

(fast-expt 2 9)

*Output:*

`
`

512

(fast-expt 2 10)

*Output:*

`
`

1024

(fast-expt 3 0)

*Output:*

`
`

1

(fast-expt 3 1)

*Output:*

`
`

3

(fast-expt 3 2)

*Output:*

`
`

9

(fast-expt 3 3)

*Output:*

`
`

27

(fast-expt 3 4)

*Output:*

`
`

81

(fast-expt 3 5)

*Output:*

`
`

243

(fast-expt 3 6)

*Output:*

`
`

729

(fast-expt 3 7)

*Output:*

`
`

2187

(fast-expt 3 8)

*Output:*

`
`

6561

(fast-expt 3 9)

*Output:*

`
`

19683

(fast-expt 3 10)

*Output:*

`
`

59049