1.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)
x
 
4


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


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

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)
 
15