Exercise 1.16

Imports: [[Chapter 1.1]] square

Iterative, successive squaring: \(\Theta (\log n)\) time, \(\Theta(\log n)\) space.

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

(fast-expt 2 5) => 32
(fast-expt 2 100) => 1267650600228229401496703205376