16

Exercise 1.16: 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^{n2/})^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 $ab^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.)

① Suppose n is even:

(define (square x) (* x x))
(define (fast-expt b n) (fast-expt-iter 1 b n))

(define (fast-expt-iter a b n) (if (= n 1) a (fast-expt-iter (* a (square b)) b (/ n 2))))
(fast-expt 2 4)

② For n is not even, we compute $| b^{n-1} |$ first.

(define (fast-expt-all b n) (if (= 0 (mod n 2)) (fast-expt-iter 1 b n) (* b (fast-expt-iter 1 b (- n 1)))))

(fast-expt-all 2 3)