# Iterative exponentiation process

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?

• even? is a Scheme builtin, so you should not define your own version. :-) Also, your bottom version isn't iterative. Jun 19 '12 at 2:59

Your implementation will not produce correct results in general because your recursive definitions are erroneous.

One should note that in case n = 0, result is 1. In case of even n (or n = 2 i), one may write b ^ n = (b * b) ^ i. In case of odd n (or n = 2 i + 1), one may write b ^ n = b * (b * b) ^ i. Here's an implementation (using if's instead of cond and folding the two recursive steps into one):

(define (fast-expt b n)
(if (= n 0) 1
(* (if (= (remainder n 2) 0) 1 b) (fast-expt (* b b) (quotient n 2)))))


To make this definition iterative, use the accumulator, a, that is initially 1. When n is even (n = 2 i), square b but keep a unchanged. This maintains the property b ^ n = a * (b ^ 2) ^ i. When n is odd (n = 2 i + 1), square b and multiply a by b. This maintains the property b ^ n = (a * b) * (b ^ 2) ^ i. Thus, we have:

(define (fast-expt b n)
(fast-expt-iter 1 b n))

(define (fast-expt-iter a b n)
(if (= n 0) a
(fast-expt-iter (* a (if (= (remainder n 2) 0) 1 b)) (* b b) (quotient n 2))))

• This doesn't work for (fast-expt 2 2) - it returns 2, which should be 4, shouldn't it? Mar 28 '11 at 3:59
• @jaresty: You're absolutely right. I screwed up my recursive definition. =) I'm editing my answer. Mar 28 '11 at 5:35
• Hmm... I'm a bit confused. The problem asked for an "iterative solution," but I feel like the solution we arrived at is somehow more recursive than iterative. What do you think? Mar 28 '11 at 7:03
• @jaresty: Agreed. I forgot to include the iterative version. Edited it into the answer. Mar 28 '11 at 7:34