The Grass on the Other Side...

...of the fence is not necessarily the same colour of green as the grass you can see here.

Or, alternatively:

The views expressed this blog are mine alone, and do not necessarily reflect those of my employer.

Just in case you were silly enough to think they were.

SICP Exercise 1.18: Iterative Multiplication

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.

To remind us, exercise 1.16 took a recursive implementation of fast-expt which utilized successive squaring:

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

...and produced a corresponding iterative implementation:

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

To do this we introduced a state variable, a, and established the invariant quantity was abⁿ, where b was the base and n the exponent. For any operation we applied to n to bring us nearer to the terminating condition we had to apply an appropriate operation to either b or a in order to maintain the invariant.

Okay, so here's the result from exercise 1.17:

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

To produce a corresponding iterative implementation, we're going to have to follow a similar set of steps. We introduce a state variable, s, that we will use for accumulating the result into, and then establish the invariant quantity s + ab, where a and b correspond to the numbers to be multiplied. So in what ways can we maintain the invariant quantity s + ab while changing at least one of s, a and b? Well, we can double a if we half b. We can also add a to s if we subtract 1 from b. I.e.

• s + ab = s + 2a(b/2)
• s + ab = (s + a) + a(b - 1)

The first of these relationships give us a way to maintain the invariant quantity when b is even while the second gives us a way to maintain it when b is odd. So, in the same way we used the invariant quantity relationships determined in exercise 1.16 to produce the iterative implementation from the recursive one, we can produce:

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

...and try it out:

> (mult 2 4)
8
> (mult 4 2)
8
> (mult 3 21)
63
> (mult 12 34)
408

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