From SICP's 1.24: (Exponentiation)
(you may need to click through and read ~1 page to understand)
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.)
I wrote the following solution:
(define (even n) (= (remainder n 2) 0)) (define (fast-expt b n) (fast-expt-iter b b n)) (define (fast-expt-iter a b n) (cond ((= n 1) a) ((even n) (fast-expt-iter (* a b) b (/ n 2))) (else (fast-expt-iter (* a b) b (- n 1)))))
Do you think my solution is correct? Moreover, what do you think about my code?