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?

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

StackExchange Code Review Q#1443, answer score: 4