Discrete Mathematics for Computer Science

Multiplication of n-Bit Numbers 575

where m2 is a constant and n = 2 k. The term m2 • n represents the additions, subtractions,
and shifting operations required in computing XY. Later, we will prove that the order of
complexity of this method is approximately n 1.59. This procedure not only gives a method
to overcome the usual representation limitations of actual computers but also allows the
computation to be done more efficiently. Although the value of n is restricted to 2 k for
some k, T(n) gives an upper bound for the complexity of T(i) for any i. It is always
possible to embed a problem of size i in a problem of size 2j, where 2j-1 < i < 2i by
adding zeros to the left of the most significant digit of n.
One last detail to handle is how to deal with the product (A + B) -(C + D) if the
additions generate an (n/2 + 1)-bit number. In case A + B and/or C + D are (n/2 + 1)-
bit numbers, proceed as follows:

Carry Calculation

A + B = A 1 2n/2 + B 1 A 1 is the leading bit of A and B 1 the remaining bits

C + D = C 1 2n/2 + D 1 C1 is the leading bit of C and D 1 the remaining bits

(A + B) • (C + D) = A 1 • C 1 2n + (A 1 • D 1 + B 1 • C 1 )2n/^2 ± B 1 • D 1

Since B 1 and D 1 are n/2-bit numbers, the term BI -D 1 can be computed using the
recursive method. The other operations can be computed directly, since they involve 1-bit
numbers or they can be accomplished by simple shifting operations.
Figure 9.7 shows how two 4-bit numbers would be multiplied using this procedure.
The reader should try an example in which the carry digit comes into play.

1011*0110

101*11 *11

10*01 (a+b)(c+d)

Sa1 c I " bd

1*0 1*1 0*1 10*1 11*10 1*1 1*1 10*1 1*0

ac (a+b)*(c+d) ac

ac (a+b)(c+d)-ac-bd bd 10 110-10-1 1 1 10-1 0

0 1-0-0 0

0*22 1*21 0 10*22 111*2 1 1*22 1*21^0

10 1111 110

1 1

10*24 1111-10-110

10*2 111*22 110

1000010

Figure 9.7 Multiplication of two 4-bit numbers.