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:
- when n is even, $$ ab^n = a(b^{2})^{n/2} $$
- when n is odd, $$ ab^n = ab(b^{n-1}) $$