SICP exercise 1.16, where is my bug, because it looks right to me

Question

I've just started working through this book for fun; I wish it were homework, but I could never afford to attend MIT, and there are tons of people smarter than me anyway. :p

fast-exp is supposed to find b^n, i.e. 4^2 = 16, 3^3 = 27

(define (fast-exp b n)
  (define (fast-exp-iter n-prime a)
    (cond ((= n-prime 1) a)
          ((= (remainder n-prime 2) 1) (fast-exp-iter (- n-prime 1) (* a b)))
          (else (fast-exp-iter (/ n-prime 2) (* a b b)))))
  (fast-exp-iter n 1))

fast-exp 4 2; Expected 16, Actual 2

Answer 1

You forgot to call fast-exp. Instead, you evaluated three separate atoms. To actually evaluate the fast-exp of 4 to the 2, you'd have to write

(fast-exp 4 2)

Answer 2

The solution you have written here is also incorrect. e.g. Check out (fast-exp 2 6). Expected: 64, actual: 32.

Answer 3

Your solution is calculating wrong answers. (See http://ideone.com/quT6A) In fact, how you in principle can write a tail-recursive fast exponentiation passing only two numbers as arguments? I don't think it's even possible, because in the middle of computation you don't know what multiplier to use if you encounter odd exponent. But I can give an example of working solution that is exactly what is expected by SICP authors (iterative process using "invariant quantity" (a * b^n), where a is initially 1)

(define (pow x y)
  (define (powi acc x y)
    (cond
      ((= y 0) acc)
      ((odd? y) (powi (* acc x) x (- y 1)))
      (else (powi acc (* x x) (/ y 2)))))
  (powi 1 x y))