Page 273 - Discrete Mathematics and Its Applications

252 4 / Number Theory and Cryptography

ALGORITHM 3 Multiplication of Integers.

procedure multiply(a, b: positive integers)
{the binary expansions of a and b are (a n−1 a n−2 ...a 1 a 0 ) 2
and (b n−1 b n−2 ...b 1 b 0 ) 2 , respectively}
for j := 0 to n − 1
if b j = 1 then c j := a shifted j places
else c j := 0
{c 0 ,c 1 ,...,c n−1 are the partial products}
p := 0
for j := 0 to n − 1
p := p + c j
return p {p is the value of ab}

Example 10 illustrates the use of this algorithm.

EXAMPLE 10 Find the product of a = (110) 2 and b = (101) 2 .

Solution: First note that
0
0
ab 0 · 2 = (110) 2 · 1 · 2 = (110) 2 ,
1
1
ab 1 · 2 = (110) 2 · 0 · 2 = (0000) 2 ,
110
× 101 and
110
2 2
000 ab 2 · 2 = (110) 2 · 1 · 2 = (11000) 2 .
110
To find the product, add (110) 2 , (0000) 2 , and (11000) 2 . Carrying out these additions (us-
11110
ing Algorithm 2, including initial zero bits when necessary) shows that ab = (1 1110) 2 . This
FIGURE 2 multiplication is displayed in Figure 2. ▲
Multiplying
(110) 2 and (101) 2 . Next, we determine the number of additions of bits and shifts of bits used by Algorithm 3
to multiply two integers.
EXAMPLE 11 How many additions of bits and shifts of bits are used to multiply a and b using Algorithm 3?

Solution: Algorithm 3 computes the products of a and b by adding the partial products
c 0 ,c 1 ,c 2 ,..., and c n−1 . When b j = 1, we compute the partial product c j by shifting the binary
expansion of a by j bits. When b j = 0, no shifts are required because c j = 0. Hence, to find
j
all n of the integers ab j 2 ,j = 0, 1,...,n − 1, requires at most
0 + 1 + 2 + ··· + n − 1

2
shifts. Hence, by Example 5 in Section 3.2 the number of shifts required is O(n ).
To add the integers ab j from j = 0to j = n − 1 requires the addition of an n-bit integer,
an (n + 1)-bit integer,..., and a (2n)-bit integer. We know from Example 9 that each of these
2
additions requires O(n) additions of bits. Consequently, a total of O(n ) additions of bits are
required for all n additions. ▲

Surprisingly, there are more efficient algorithms than the conventional algorithm for mul-
tiplying integers. One such algorithm, which uses O(n 1.585 ) bit operations to multiply n-bit
numbers, will be described in Section 8.3.