Large Integer Multiplication

Let's look again at the example multiplication:

					5	4	3	2	1
				x			4	5	6
				3	2	5	9	2	6
			2	7	1	6	0	5
	+	2	1	7	2	8	4
		2	4	7	7	0	3	7	6

You can see that the first number (54321) has 5 digits and the second (456) has 3. Looking at the individual multiplications (eg.: 6x1, 6x2, ... 5x1, 5x2, ... 4x1, 4x2, ... 4x5) we can see there are 15 of them, which is the product of the number of digits (5 x 3).

Next there are two big additions corresponding to the number of digits in the second number minus one (three rows of numbers means two additions). If we expand each addition number with zeroes, we get:

					5	4	3	2	1
				x			4	5	6
		0	0	3	2	5	9	2	6
		0	2	7	1	6	0	5	0
	+	2	1	7	2	8	4	0	0
		2	4	7	7	0	3	7	6

Here we have two additions of 8 digits where 8 = 5 + 3. So the additions reduce to 2 x 8 or 16 simple additions.

In general, if a and b are two numbers of m and n digits respectively, then a x b results in m x n small multiplications. We will then have n - 1 big additions of at most m + n digits resulting in at most (n - 1) x (m + n) small additions.

Of course this can be optimized, noting that adding a zero to a number doesn't change the number.

However in the simplest form, multiplying a by b results in m x n small multiplications and at most (n - 1) x (m + n) small additions.

Now, although we have explained this using digits as the smallest item that can be added or multiplied using the intrinsic computer instructions, the same explanation holds if we substituted computer words of 32 bits. In this case instead of considering the digits 0 - 9 as a single unit, we consider the number 0 - (2³² - 1) which the computer can add or multiply in a single instruction.

A look at another algorithm for multiplication, the Karatsuba method, can be found here.