Exercise 1.17

Recursive, naive: \(\Theta(n)\) time, \(\Theta(n)\) space.

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

(* 5 4) => 20

These are taken as primitives:

(define (double x) (+ x x))
(define (halve x) (/ x 2))

Recursive, sucessive doubling: \(\Theta(\log n)\) time, \(\Theta(\log n)\) space.

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

(fast-* 5 4) => 20