 Multiplication

Let x and у be integers expressed in radix b representation: x = (xnxn-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 pencil-and-paper method taught in grade school. A single-precision 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 Multiple-precision multiplication

INPUT: positive integers x and у havmg n + 1 and t + 1 base b digits, respectively. OUTPUT: the product x ■ у = (wn+t+i ■ ■ ■ ww0)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, c-t—u.

• 2.3 mj+n+i^— u.
• 3. Retum((u>n+t+i • • -wiw0)).

14.13 Example (multiple-precision 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 wi+j + XjiИ + c u V w6 w5 W4 W3 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: Multiple-precision multiplication (see Example 14.13).

14.14 Remark (pencil-and-paper method) The pencil-and-paper 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 wi+j + Xj yi + c is called the inner-product operation. Since wi+j, Xj, y, and c are all base b digits, the result of an inner-product operation is at most (b - 1) + (b - l)2 + (b - 1) = b2 - 1 and, hence, can be represented by two base b digits.
• (ii) Algorithm 14.12 requires (n + l)(t + 1) single-precision multiplications.
• (iii) It is assumed in Algorithm 14.12 that single-precision 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.