janmr blog

Basic Multiple-Precision Multiplication

After addressing multiple-precision addition and subtraction, we now turn to multiplication of two multiple-precision numbers. Once again, we use the number representation and notation introduced earlier.

Several algorithms exist for doing multiple-precision multiplication. This post will present the basic, pencil-and-paper-like method. Basically, it consists of two parts: Multiplying a number by a single digit and adding together the sub-results, aligned appropriately.

Multiple digits times a single digit

Let us first consider multiplying an -digit multiple-precision integer by a single digit. More precisely, we wish to compute where

Using this information it is straightforward to show that , which implies that the result will fit into or digits, so we set , where may be zero.

We now have the algorithm:

for and finally setting .

To realize that the algorithm computes what it is supposed to, observe first that

Then we have

which is what we wanted.

From the expression for we see that they naturally fit into a digit, that is, for . But what about the 's and thus also ? Assume that . We then have which implies that . Since we have also assumed we have, by induction, that for .

Multiple digits times multiple digits

We now turn to multiplying two multiple-precision numbers. More specifically, we wish to multiply

which implies . So we set and aim to compute

We observe two things:

  1. Multiplication by corresponds to shifting left the number of digits given by .
  2. The product is of type single-digit times multiple-digit and can be computed using the algorithm from the previous section.

Putting these pieces together we get:

The algorithm can actually be generalized slightly if we compute

instead. All we need to do is replace the first step in the algorithm by