A fast iterative process for multiplication in Scheme

I have been studying the book Structure and Interpretation of Computer Programs in my free time. The book uses the Scheme programming language to explain and explore concepts in programming and computer science. It is a great book with a lot of depth and I highly recommend it to anyone interested in either of these areas of study.

One of the exercises in the book is to design a procedure that can multiply two numbers (without using multiplication or division) in O(log n) time and using O(1) space. The solution is really cool! The way in which the procedure manipulates numbers is both clever and elegant. Let’s take a look at how it works.

The Problem Statement

It is assumed that our language can only add and subtract, not multiply and divide. In such a language, integer multiplication can be performed by means of repeated addition. The following procedure demonstrates this and has a time complexity that is linear in b (O(n) time complexity).

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

Given this example, the exercise in the book is then presented to the reader as follows:

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.

By analogous to fast-expt , a previous exercise in the book, the authors simply mean that the procedure must evolve an iterative process that takes O(1) space and must also take a logarithmic number of steps.

Here is the solution that I wrote:

(define (* a b)
  (if (or (= a 0) (= b 0)) 
    0
    (fast-mult-iter a b 0)))
(define (fast-mult-iter a b sum)
  (cond 
    ((= b 0) sum)
    ((even? b) 
      (fast-mult-iter (double a) (halve b) sum))
  (else 
    (fast-mult-iter a (- b 1) (+ a sum)))))
#|
It is assumed that double and halve are implemented 
by the language. The following procedures are
meant to simulate such implementations. 
|#
(define (double n)
  (+ n n))
(define (halve n)
  (/ n 2))

TL;DR

The procedure alternates between two patterns: halving b and doubling a until b is odd; then subtracting 1 from b and incrementing sum by a.

How It Works

Basically, the procedure works by halving b and doubling a until b is an odd number. This is possible because of the associative and commutative properties of multiplication. Then, it pulls out one a and adds it to a state variable sum by subtracting 1 from b . Now b will be even again and the procedure can continue this pattern: halving b and doubling a until b is odd, then subtracting 1 from b and incrementing sum by a. This pattern continues until b is zero, at which point the procedure returns the sum.

Let’s look at this more closely with an example. Suppose we apply the * procedure to 10 and 12. That is to say a is 10 and b is 12. The following diagram illustrates this example. Starting from the top row and reading the diagram row by row demonstrates how the variables a, b, and sum change throughout the lifecycle of the procedure call.

We will halve b and double a until b is no longer even. So a becomes 20 and b becomes 6. Then a becomes 40 and b becomes 3. The multiplication has been transformed to 40 x 3 which can be represented as 40 + 40 + 40. If we pull out one 40 and move it to sum , we are left with 40 + 40 or 40 * 2, and b is once again even. Now we continue the pattern of halving and doubling such that a becomes 80 and b becomes 1. Since b is now odd we can pull out one 80 and move it to sum so that we are left with a of 80, b of 0, and sum of 80 + 40 = 120. Now in the last iteration of the procedure since b is zero, the sum of 120 is returned.

This is a relatively simple procedure, but I really like the way that it manipulates the numbers with two interwoven patterns. The challenge of designing the algorithm was the restriction of having a time complexity of O(log n) and a space complexity of O(1). I thought it was a cool example and I wanted to share it with you all. I hope that you find it interesting as well. Thanks for reading!