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

## Problem

The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the `expt` procedure:

(define (* a b) (if (= b 0) 0 (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in *b*. Now suppose we include, together with addition, operations `double`, which doubles an integer, and `halve`, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to `fast-expt` that uses a logarithmic number of steps.

## Solution

Here's one possible implementation:

(define (double a) (* a 2)) (define (even? n) (= (remainder n 2) 0)) (define (halve a) (/ a 2)) (define (fast-mul a b) (cond ((= b 0) 0) ((even? b) (double (fast-mul a (halve b)))) (else (+ a (fast-mul a (- b 1))))))

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