## **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

## 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 *a**b* and state variable `p`, *a**b* + *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