SICP Exercise 1.17: Additive Multiplication

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.

Let's begin by defining double and halve. These are very straightforward:

(define (double x) (* x 2))
(define (halve x) (/ x 2))

Now let's think about how we can use these to implement multiplication-by-addition. If we look at the original recursive definition of fast-expt from section 1.2.4:

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

We see that it consists of three expressions that will be conditionally evaluated based upon whether n is 0, even or odd respectively:

• When n = 0, the terminating case, it returns 1, as b⁰ = 1.
• When n is even, it squares the result of a recursive call with n' = n/2, as bⁿ = (b^n/2)², and this allows us to make progress towards the terminating case.
• When n is odd, it multiplies the result of a recursive call with n' = n - 1, as bⁿ = bb^n-1, and this too allows us to make progress towards the terminating case.

There are an analogous set of expressions for the multiplication-by-addition procedure which we are going to define (and here we're assuming that we have two numbers a and b that we want to multiply together):

• We'll make our terminating case to be when b = 0. In this case we want our procedure to return 0, as a.0 = 0.
• When b is even we can make progress towards the terminating case by doubling the result of making a recursive call with b' = b/2, as ab = 2ab/2.
• When b is odd we can make progress towards the terminating case by adding a to the result of making a recursive call with b' = b - 1, as ab = a + a(b - 1).

This then allows us to define our procedure:

(define (mult a b)
  (cond ((= b 0) 0)
        ((even? b) (double (mult a (halve b))))
        (else (+ a (mult a (- b 1))))))

Let's give it a spin!

> (mult 3 5)
15
> (mult 5 3)
15
> (mult 2 34)
68
> (mult 13 11)
143