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.
 
Source
< Prev   CONTENTS   Source   Next >