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