Division
Division is the most complicated and costly of the basic multipleprecision operations. Algorithm 14.20 computes the quotient q and remainder r in radix b representation when x is divided by y.
14.20 Algorithm Multipleprecision division
INPUT: positive integers x = (x_{n} ■ ■ ■ xix_{0})b, y = (yf■ УУо)ь with n > t > 1, y_{t} ф 0. OUTPUT: the quotient q = {q_{n}t • ■ • qqo)b and remainder r = (r_{t} ■ ■ ■ rir_{0})b such that x = qy + r,0 < r < y.
 1. For j from 0 to (n  t) do: qj*0.
 2. While (x > yb^{n}~*) do the following: q_{n}_{t}<qnt + 1, x<—x  yb^{n}~*.
 3. For i from n down to (t + 1) do the following:
 3.1 If Xi = y_{t} then set 1; otherwise set ^{x}ii)/yt) ■
 3.2 While (qi_{t}i(ytb + yti) > ж<Ь^{2} + *_{f}_ib +ж^__{2}) do: g»—ti■<—Q'i—t—l  1
 3.3 xl—x — qitiyb^{111}.
 3.4 If x < 0 then set хьx + yb^{l_t}~^{l} and qiti<—qiti ~ 1
 4. П—X.
 5. Retum(q,r).
 14.21 Example (multipleprecision 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 
X_{5} 
Xa 
x_{3} 
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: Multipleprecision 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 y_{t} > 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 qiti 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 qiti<[{xib^{2} + Xiib + x'i_2)/{ytb + yti)J, then the estimate is almost always correct and step 3.2 is never repeated more than once. One can always guarantee that y_{t} > [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 leftshifting the binary representations of x and y. Multiplying by a suitable choice of A to ensure that y_{t} > _^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: Multipleprecision 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 singleprecision multiplications. Hence, Algorithm 14.20 with normalization requires about (n — t)(t + 3) singleprecision multiplications.
 (ii) (division count) Since step 3.1 of Algorithm 14.20 is executed n  t times, at most nt singleprecision divisions are required when normalization is used.