Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.18

Jump to: navigation, search

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 $ab = \frac{2ab}{2}$.

(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