Multiplication of n-Bit Numbers 573W Multiplication of n-Bit Numbers
Because the design of a computer includes a decision about the size of the unit of storage
for holding integer values, the exact multiplication of integers with an arbitrarily large
number of digits usually cannot be done using a computer's multiplication operation. Since
exact multiplication of large numbers cannot be accomplished using the hardware structure
of a computer, a software approach is needed. In a software approach, a number is assumed
to be represented by its binary expansion consisting of n bits for n as large as needed.
The exact multiplication of n-bit numbers when n is large can be accomplished using a
divide-and-conquer strategy.
The example that follows shows how two 8-bit numbers are decomposed so that the
multiplication of these two numbers involves multiplication of only 4-bit numbers:X = 01101100, Y = 10011001,
A = 0110, B = 1100, C = 1001, D = 1001,
X=A24 + B, Y = C24 + D,
XY = (A2^4 + B)(C2^4 + D)
= AC 28+ BC2^4 + AD2
(^4) + BD
The multiplications involve 4-bit digits even though X and Y are 8-bit digits. The multipli-
cations by 24 and 28 can be carried out simply as a shift operation and not as a multiplica-
tion. Assume, now, that X and Y are n-bit numbers with n = 2 k for some k. The restriction
to the case n = 2 k will make the calculation easier to present without losing any essential
information about this method.
Let X and Y be n-bit numbers with A(C) the first n/2 bits of X(Y) and B(D) the
remaining bits. The decompositions of X and Y are as follows:
Calculation I
X = A2n/^2 + B
Y = C2n1^2 + D
XY = A • C2n + (A • D + B • C)2n/^2 + B • D
This method for calculating XY involves four multiplications using pairs of numbers of
size n/2. Repeat the divide-and-conquer strategy to calculate each of these n/2-bit products
using n/4-bit numbers. Now, let T (n) be the measure of complexity for multiplying two n-
bit numbers where the key operation measured is the multiplication of two n-digit numbers.
The complexity of this method is described by the following recurrence relation:T(n) = 4T(n/2) + mln
where m I is a constant and n = 2k.