Exercise 1.18

Iterative, succesive doubling: \(\Theta(\log n)\) time, \(\Theta(1)\) space.

(define (fast-* a b)
  (define (iter c a b)
    (cond ((= b 0) c)
          ((even? b) (iter c (double a) (halve b)))
          (else (iter (+ c a) a (- b 1)))))
  (iter 0 a b))

(fast-* 5 4) => 20