[archives] [homepage]

Problem 1.16
Friday, August 23, 2019; ago; Download .md

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}) $$