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

