SICP exercise 1.16

From Drewiki

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})² = (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.)

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