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