Division

Division is the most complicated and costly of the basic multiple-precision operations. Algorithm 14.20 computes the quotient q and remainder r in radix b representation when x is divided by y.

14.20 Algorithm Multiple-precision division

INPUT: positive integers x = (xn ■ ■ ■ xix0)b, y = (yf■ УУо)ь with n > t > 1, yt ф 0. OUTPUT: the quotient q = {qn-t • ■ • qqo)b and remainder r = (rt ■ ■ ■ rir0)b such that x = qy + r,0 < r < y.

  • 1. For j from 0 to (n - t) do: qj*-0.
  • 2. While (x > ybn~*) do the following: qn-t<-qn-t + 1, x<—x - ybn~*.
  • 3. For i from n down to (t + 1) do the following:
  • 3.1 If Xi = yt then set 1; otherwise set xi-i)/yt) ■
  • 3.2 While (qi-t-i(ytb + yt-i) > ж<Ь2 + *f_ib +ж^_2) do: g»—t-i■<—Q'i—t—l - 1-
  • 3.3 xl—x — qi-t-iyb1-1-1.
  • 3.4 If x < 0 then set хь-x + ybl_t~l and qi-t-i<—qi-t-i ~ 1-
  • 4. ПX.
  • 5. Retum(q,r).
  • 14.21 Example (multiple-precision division) Let x = 721948327, у = 84461, so that n = Sand t = 4. Table 14.5 illustrates the steps in Algorithm 14.20. The last row gives the quotient q = 8547 and the remainder r = 60160. □

i

<74

<7з

Я2

Qi

9o

Ха

X7

Xe

X5

Xa

x3

X2

Xi

Xo

-

0

0

0

0

0

7

2

1

9

4

8

3

2

7

8

0

9

0

0

0

7

2

1

9

4

8

3

2

7

8

0

0

0

4

6

2

6

0

3

2

7

7

8

5

0

0

4

0

2

9

8

2

7

G

8

5

5

0

4

0

2

9

8

2

7

8

5

4

0

6

5

1

3

8

7

5

8

5

4

8

6

5

1

3

8

7

8

5

4

7

6

0

1

C

0

Table 14.5: Multiple-precision division (see Example 14.21).

  • 14.22 Note (comments on Algorithm 14.20)
  • (i) Step 2 of Algorithm 14.20 is performed at most once if yt > |Jj and b is even.
  • (ii) The condition n > t > 1 can be replaced by n > t > 0, provided one takes Xj = у j — 0 whenever a subscript j < 0 in encountered in the algorithm.
  • 14.23 Note (normalization) The estimate for the quotient digit qi-t-i in step 3.1 of Algorithm
  • 14.20 is never less than the true value of the quotient digit. Furthermore, if y, > then step 3.2 is repeated no more than twice. If step 3.1 is modified so that qi-t-i<-[{xib2 + Xi-ib + x'i_2)/{ytb + yt-i)J, then the estimate is almost always correct and step 3.2 is never repeated more than once. One can always guarantee that yt > [fj by replacing the integers x, у by Xx, Xу for some suitable choice of Л. The quotient of Xx divided by Xy is the same as that of x by у; the remainder is Л tunes the remainder of x divided by y. If the base h is a power of 2 (as in many applications), then the choice of A should be a power of 2; multiplication by A is achieved by simply left-shifting the binary representations of x and y. Multiplying by a suitable choice of A to ensure that yt > |_^J is called normalization. Example 14.24 illustrates the procedure.
  • 14.24 Example (.normalized division) Take x = 73418 and у = 267. Normalize x and у by multiplying each by A = 3: x' = 3a; = 220254 and у = 3у = 801. Table 14.6 shows the steps of Algorithm 14.20 as applied to x' and y'. When x' is divided by у', the quotient is 274, and the remainder is 780. When x is divided by y, the quotient is also 274 and the remainder is 780/3 = 260. □

i

Яз

92

9i

9o

X5

Xa

Хз

X2

Xi

Xo

0

0

0

0

2

2

0

2

5

4

5

0

2

0

0

6

0

0

5

4

4

2

7

0

3

9

8

4

3

2

7

4

7

8

0

Table 14.6: Multiple-precision division after normalization (see Example 14.24).

  • 14.25 Note (computational efficiency of Algorithm 14.20 with normalization)
  • (i) (multiplication count) Assuming that normalization extends the number of digits in ж by 1, each iteration of step 3 requires 1 + (f + 2) = f + 3 single-precision multiplications. Hence, Algorithm 14.20 with normalization requires about (n — t)(t + 3) single-precision multiplications.
  • (ii) (division count) Since step 3.1 of Algorithm 14.20 is executed n - t times, at most n-t single-precision divisions are required when normalization is used.
 
Source
< Prev   CONTENTS   Source   Next >