18

Exercise 1.18: Using the results of Exercise 1.16 and Exercise 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.

Assume b is even first:

(define (double a) (* a 2))
(double 2)

(define (halve b) (/ b 2))
(halve 4)

(define (fast-multi a b)
    (if (= b 1) 
        a 
        (fast-multi (double a) (halve b))
)
)

(fast-multi 3 4)

The process is iterative because:

(fast-multi 3 4) ------------\
(fast-multi 6 2)             |
(fast-multi 12 1)            |
12               <-----------/

For b is not even, we subtract 1 from it:

(define (fast-multi-all a b) (if (= 0 (mod b 2)) (fast-multi a b) (+ a (fast-multi a (- b 1)))))
(fast-multi-all 3 5)