#29: Multiplying Long-Hand

Tagged as challenge

Written on 2018-01-30

Modern CPUs only support multiplying integers of a fixed size, which is usually 32- or 64-bits.

In grade school, most of us learned how to multiply numbers long-hand; we write the two numbers down, one above the other, and proceed to do the multiplication. It often looks like so:

   123
  x 45
  ----
   615
+ 492
------
  5535

If you've forgotten this method for multiplying, you might consult a children's arithmetic book.

The goal of this exercise is to implement the long multiplication algorithm. While not required, it is certainly convenient if your language supports arbitrary precision integers out of the box.

Part 1

As testing utilities, write two functions:

• (digits n) which takes a non-negative integer and produces a list of base-10 digits from least to most significant. For example, (digits 123) shall return (3 2 1). Decide on what (digits 0) should be.

• (undigits dlist) which does the opposite: takes a list of digits and produces a non-negative integer.

Furthermore, answer the following questions:

• Is any list of digits a valid representation of a non-negative integer?

• What is the precise relationship between digits and undigits?

Part 2

Implement the long multiplication algorithm as a function long-multiply which takes two lists of base-10 numbers and produces a list representing the product.

Part 3

Modify long-multiply to print out what the process might look like with pencil and paper. For example:

(display-long-multiply '(3 2 1) '(5 4))

; Outputs:
;
;    123
;   x 45
;   ----
;    615
; + 492
; ------
;   5535

Part 4

If you implemented the previous parts successfully, you may not have done so with absolute mathematical correctness. Without loss of generality, suppose we are multiplying two $N$-digit numbers. Then, in the second step of the algorithm, we will produce the $N$ terms that we need to add up. When we perform the addition in each column, each of which consist of at most $N$ base-10 digits, our sum will likely exceed our digit size.

Answer these questions:

1. What is the maximum size of a number we could sum to in a column?

2. What is an example of two numbers whose multiplication process leads to that sum?

3. If we are truly constrained on a computer where every storable register, be it in the processor or RAM, is limited to holding a digit between 0 and 9, how can we modify the algorithm to accommodate?

Finally, perform the modifications to the algorithm.

• ← Previous
• Next →