SICP exercise 1.18

From Drewiki

Problem

Using the results of exercises 1.16 and 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.

Solution

Here's one possible implementation. Like we did in exercise 1.16, let's use an invariant: given product ab and state variable p, ab + p is unchanged from state to state. At the beginning of the process, the state variable p is 0, and the answer is given by p at the end.

Let's also take advantage of the fact that .

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

Tests:

(fast-mul 2 0)

Output:

0

(fast-mul 0 2)

Output:

0

(fast-mul 2 1)

Output:

2

(fast-mul 2 2)

Output:

4

(fast-mul 2 3)

Output:

6

(fast-mul 2 4)

Output:

8

(fast-mul 2 5)

Output:

10

(fast-mul 2 6)

Output:

12

(fast-mul 2 7)

Output:

14

(fast-mul 2 8)

Output:

16

(fast-mul 2 9)

Output:

18

(fast-mul 2 10)

Output:

20

(fast-mul 3 3)

Output:

9

(fast-mul 3 4)

Output:

12

(fast-mul 3 5)

Output:

15

(fast-mul 3 6)

Output:

18

(fast-mul 3 7)

Output:

21

(fast-mul 3 8)

Output:

24

(fast-mul 3 9)

Output:

27

(fast-mul 3 10)

Output:

30

(fast-mul 25 13)

Output:

325