Iterative exponentiation process

Question

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 (b^n/2)² = (b²)^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 bⁿ 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?

• C. K. Young: even? is a Scheme builtin, so you should not define your own version. :-) Also, your bottom version isn't iterative.

Answer 1

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

• jaresty: This doesn't work for (fast-expt 2 2) - it returns 2, which should be 4, shouldn't it?
• Adeel Zafar Soomro: @jaresty: You're absolutely right. I screwed up my recursive definition. =) I'm editing my answer.
• jaresty: 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?
• Adeel Zafar Soomro: @jaresty: Agreed. I forgot to include the iterative version. Edited it into the answer.