 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.