SICP Exercise 1.16

Question

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})^2=(b^2)^{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 $ab^n$ 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.)

Answer

(define (even? n) (= (remainder n 2) 0))
(define (square n) (* n n))

(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
        (else (fast-expt-iter b (- n 1) (* a b)))))

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

If the exponent $n$ is even, the function is recursively called to turn $b^n$ into $(b^2)^\frac{n}{2}$. A multiplication is only actually calculated if an odd exponent is given, in which case a is multiplied by b once. After one evaluation, the exponent will either be even again (causing a new successive squaring) or $0$, in which case a is returned.