SICP Exercise 1.16 - Is my solution correct?

Question

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

So I've tried really hard and came up with this solution:

(define (exp b n)
  (exp-iter b n 1))

(define (square p) (* p p))

(define (even? k)
  (= (remainder k 2) 0))

(define (exp-iter b counter product)
  (define (smash counter)
    (if (even? counter) (square (exp-iter b (/ 2 counter) product)) (* b (exp-iter b (- counter 1) product))))
  (if (= counter 0) product (smash counter)))

(exp 4 3) ;test

This runs perfectly but I'm not sure if this is what the author asked me to do. Are there any problems with this? Is my solution really iterative?

Óscar López Óscar López · Accepted Answer · 2019-09-29T21:31:43

Your solution is not iterative. An iterative process is one that doesn't call anything after the recursive call, and that's not the case in these two lines:

(square (exp-iter b (/ 2 counter) product))
(* b (exp-iter b (- counter 1) product))

After invoking exp-iter, in the first line you're passing the result to square, and in the second line you're multiplying the result by b. Compare it with this, a tail recursive solution:

(define (exp-iter b counter product)
  (cond ((= counter 0)
         product)
        ((even? counter)
         (exp-iter (square b) (/ counter 2) product))
        (else
         (exp-iter b (- counter 1) (* b product)))))

Notice that after invoking exp-iter there's nothing left to do and the procedure simply returns its value. A smart compiler will detect this, and transform the recursive call into a loop that will use a constant amount of stack memory (instead of increasing with every recursive call.)

SICP Exercise 1.16 - Is my solution correct?

1 Answers