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.
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.