1.16|

$ cd ~

SICP Exercise 1.16

(define (square x)
   (* x x))

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

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

The Hint suggests keeping an additional state variable such that the product \(a b^n\) remains unchanged from state to state. Therefore: