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 .

Tests:

Output:

0

Output:

0

Output:

2

Output:

4

Output:

6

Output:

8

Output:

10

Output:

12

Output:

14

Output:

16

Output:

18

Output:

20

Output:

9

Output:

12

Output:

15

Output:

18

Output:

21

Output:

24

Output:

27

Output:

30

Output:

325