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 (bn2/)2=(b2)n/2 (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 bn1 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)

results matching ""

    No results matching ""