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

From Drewiki
Jump to: navigation, search

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

(bn / 2)2 = (b2)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 abn 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
Personal tools