Multiplication of Large Integers

Multiplication of Large Integers

If the conventional algorithm for multiplying two n-digit integers is used, each of the n digits of the first number is multiplied by each of the n digits of the second number for the total of n² digit multiplications.

The divide-and-conquer strategy can be used to design an algorithm with fewer than n² multiplications.

The basic idea of the algorithm can be demonstrated using:

 Consider a case of two-digit integers, say, 23 and 14. These numbers can be represented as follows:

23 = 2 x 10¹ + 3 x 10⁰ and 14 = 1 x 10¹ + 4 x 10^0.

Now multiplying them,

23 x 14 = (2 x 10¹ + 3 x 10⁰ ) x (1 x 10¹ + 4 x 10^0.)

            = (2 x 1) 10² + (2 x 4 + 3 x 1) 10¹ + (3 x 4) 10⁰.

For any pair of two-digit numbers a = a1a0 and b = b1b0, their product c can be computed by the formula

c = a x b = c₂10² + c₁10¹ + c₀ ,

where

c₂ = a₁ x b₁ is the product of first digits.

c₁ = (a₁ + a₀) x (b₁ + b₀) – (c₂ + c₀) is the product of sum of a’^s digits and sum of b’^s digits minus                the sum of c₂ and c₀.

c₀ = a₀ x b₀ is the product of second digits.

If n/2 is even, the same method can be applied for computing the products c₂, c₀, and c₁. Thus, if n is a power of 2, a recursive algorithm can be written for computing the product of two n-digit integers. The recursion is stopped when n becomes 1. It can also be stopped when n is small enough to multiply the numbers of that size directly.

Since multiplication of n-digit numbers requires three multiplications of n/2-digit numbers, the

recurrence for the number of multiplications M(n) is

M(n) = 3M (n/2) for n > 1, M(1) = 1.

Solving it by backward substitutions for n=2^k gives

M(2^k) = 3M(2^k-1) = 3[3M(2^k-2)] = 3²M(2^k-2) = …… = 3ⁱM(2^k-i) = 3^kM(2^k-k) = 3^k.

Since k = log₂ n,

If A(n) be the number of digit additions and subtractions executed by the above algorithm in multiplying two n-digit decimal integers. Besides 3A(n/2) of these operations needed to compute the three products of n/2-digit numbers, the above formulas require five additions and one subtraction. Hence, the recurrence is

Applying the Master Theorem, A(n) approximately gives n^log₂³ , which means that the total number of additions and subtractions have the same asymptotic order of growth as the number of multiplications.