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 (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 a bn 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.)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (define (square n) (* n n)) | |
| (define (odd? n) | |
| (= (remainder n 2) 1)) | |
| (define (even? n) | |
| (= (remainder n 2) 0)) | |
| (define (fast-expt-it b n) | |
| (fast-expt-iter 1 b n)) | |
| (define (fast-expt-iter a b n) | |
| (cond | |
| ((= n 0) a) | |
| ((even? n) | |
| (fast-expt-iter | |
| a | |
| (square b) | |
| (/ n 2))) | |
| ((odd? n) | |
| (fast-expt-iter | |
| (* a b) | |
| b | |
| (- n 1))))) | |