SICP excercises 1.17 and 1.18 - Multiplication using addition, doubling and halving

These two exercises ask us to implement a multiplication routine assuming we can only add, double, and halve even numbers. The first implementation is a straightforward translation of the facts that the product of two numbers \(a\) and \(b\) is given by $ab = 2 ( a { 2} ) \(</span> for even values of <span>\)b\(</span> and <span>\)ab = a(b-1) + a\(</span> for odd values of <span>\)b$. Here is the code:

(define (fast* a b)
  (cond ((= b 1) a)
        ((even? b) (double (fast* a (halve b))))
        (else (+ a (fast* a (- b 1))))))

This assumes that the routines double and halve are available.

Note that in this algorithm, doubling \(b\) will only increase the total number of steps (and the height of the call stack) by one. This means we have a process that consumes \(\Theta \left( \lg b \right)\) space and time.

Now to implement an iterative version of logarithmic time multiplication which takes constant space. When designing an iterative process, it helps to think about an expression involving the state variables of the process which will evaluate to the same value, across iterative transformations, for a particular invocation of the process. In this case, we shall use the expression \(ab + c\), with the assertion that this expression always evaluates to the intended product. For example, if we invoke our procedure with values \(a=a_0\) and \(b=b_0\) and another state variable \(c\), at any point in the iteration, say, the \(t^{th}\) step, \(a_t b_t + c_t\) must equal \(a_0 b_0\). This means the only choice for \(c_0\), the initial value of the state variable \(c\) is \(c_0 = 0\).

Next, the transformations will be as follows.

For even \(b\),

\[ a \gets 2a \\\\ b \gets \frac {b} {2} \]

For odd \(b\), \[ b \gets b-1 \\\\ c \gets a + c \]

Finally, when \(b = 0\), we return \(c\) as the result. Here’s the code:

(define (iter* a b)
  (define (aux a b c)
    ;; The invariant is that a*b + c always equals the intended product.
    (cond ((= b 0) c)
          ((even? b) (aux (double a) (halve b) c))
          (else (aux a (- b 1) (+ a c)))))
  (aux a b 0))

We can see that just like the previous recursive fast*, iter* also takes \(\Theta \left( \lg b \right)\) steps. But unlike fast*, iter* takes constant or \(\Theta \left( 1 \right)\) space, to store the state variables a, b and c.