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