Multiplication
Let x and у be integers expressed in radix b representation: x = (x_{n}x_{n}i ■ ■ ■ x 1X0)1, and У = (iJtVt 1 • • • УУо)ь The product x ■ у will have at most (n + f + 2) base b digits. Algorithm 14.12 is a reorganization of the standard pencilandpaper method taught in grade school. A singleprecision multiplication means the multiplication of two base b digits. If Xj and y, are two base b digits, then Xj ■ y, can be written as Xj ■ у, = {uv)b, where и and v are base b digits, and и may be 0.
14.12 Algorithm Multipleprecision multiplication
INPUT: positive integers x and у havmg n + 1 and t + 1 base b digits, respectively. OUTPUT: the product x ■ у = (w_{n+t+}i ■ ■ ■ ww_{0})b in radix b representation.
 1. For i from 0 to (n + t + 1) do: Wi<— 0.
 2. For i from 0 to t do the following:
 2.1 ct—0.
 2.2 For j from 0 to n do the following:
Compute (uv)b = щ+j + Xj ■ yi + c, and set v, ct—u.
 2.3 mj_{+n+}i^— u.
 3. Retum((u>_{n+t+}i • • wiw_{0})).
14.13 Example (multipleprecision multiplication) Take x = x^x^xixq = 9274 and у = У2У1У0 = 847 (base 10 representations), so that 11 = 3 and t = 2. Table 14.3 shows the steps performed by Algorithm 14.12 to compute x ■ у = 7855078. □
г 
3 
C 
w_{i+}j + XjiИ + c 
u 
V 
w_{6} 
w_{5} 
W4 
W_{3} 
W2 
W1 
Wo 
0 
0 
0 
0 + 28 + 0 
2 
8 
0 
0 
0 
0 
0 
0 
8 
1 
2 
0 + 49 + 2 
5 
1 
0 
0 
0 
0 
0 
1 
8 

2 
5 
0 + 14 + 5 
1 
9 
0 
0 
0 
0 
9 
1 
8 

3 
1 
0 + 63+1 
6 
4 
0 
0 
6 
4 
9 
1 
8 

1 
0 
0 
1 + 16 + 0 
1 
7 
0 
0 
6 
4 
9 
7 
8 
1 
1 
9 + 28+1 
3 
8 
0 
0 
6 
4 
8 
7 
8 

2 
3 
4 + 8 + 3 
1 
5 
0 
0 
6 
5 
8 
7 
8 

3 
1 
6 + 36 + 1 
4 
3 
0 
4 
3 
5 
8 
7 
8 

2 
0 
0 
8 + 32 + 0 
4 
0 
0 
4 
3 
5 
0 
7 
8 
1 
4 
5 + 56 + 4 
6 
5 
0 
4 
3 
5 
0 
7 
8 

2 
6 
3 + 16 + 6 
2 
5 
0 
4 
5 
5 
0 
7 
8 

3 
2 
4 + 72 + 2 
7 
8 
7 
8 
5 
5 
0 
7 
8 
Table 14.3: Multipleprecision multiplication (see Example 14.13).
14.14 Remark (pencilandpaper method) The pencilandpaper method for multiplying x = 9274 and у = 847 would appear as
The shaded entries in Table 14.3 correspond to row 1, row 1 + row 2, and row 1 + row 2 + row 3, respectively.
 14.15 Note (computational efficiency of Algorithm 14.12)
 (i) The computationally intensive portion of Algorithm 14.12 is step 2.2. Computing w_{i+}j + Xj ■ yi + c is called the innerproduct operation. Since w_{i+}j, Xj, y, and c are all base b digits, the result of an innerproduct operation is at most (b  1) + (b  l)^{2} + (b  1) = b^{2}  1 and, hence, can be represented by two base b digits.
 (ii) Algorithm 14.12 requires (n + l)(t + 1) singleprecision multiplications.
 (iii) It is assumed in Algorithm 14.12 that singleprecision multiplications are part of the instruction set on a processor. The quality of the implementation of this instruction is crucial to an efficient implementation of Algorithm 14.12.