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?

  • 1
    \$\begingroup\$ even? is a Scheme builtin, so you should not define your own version. :-) Also, your bottom version isn't iterative. \$\endgroup\$ Commented Jun 19, 2012 at 2:59

1 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))))
  • \$\begingroup\$ This doesn't work for (fast-expt 2 2) - it returns 2, which should be 4, shouldn't it? \$\endgroup\$
    – jaresty
    Commented Mar 28, 2011 at 3:59
  • \$\begingroup\$ @jaresty: You're absolutely right. I screwed up my recursive definition. =) I'm editing my answer. \$\endgroup\$ Commented Mar 28, 2011 at 5:35
  • \$\begingroup\$ 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? \$\endgroup\$
    – jaresty
    Commented Mar 28, 2011 at 7:03
  • \$\begingroup\$ @jaresty: Agreed. I forgot to include the iterative version. Edited it into the answer. \$\endgroup\$ Commented Mar 28, 2011 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.