Previous: Exact Remainder, Up: Division Algorithms [Index]

An NxM division where the number of quotient limbs Q=N-M is small can be optimized somewhat.

An ordinary basecase division normalizes the divisor by shifting it to make
the high bit set, shifting the dividend accordingly, and shifting the
remainder back down at the end of the calculation. This is wasteful if only a
few quotient limbs are to be formed. Instead a division of just the top
*2*Q* limbs of the dividend by the top Q limbs of the divisor can be
used to form a trial quotient. This requires only those limbs normalized, not
the whole of the divisor and dividend.

A multiply and subtract then applies the trial quotient to the M-Q unused limbs of the divisor and N-Q dividend limbs (which includes Q limbs remaining from the trial quotient division). The starting trial quotient can be 1 or 2 too big, but all cases of 2 too big and most cases of 1 too big are detected by first comparing the most significant limbs that will arise from the subtraction. An addback is done if the quotient still turns out to be 1 too big.

This whole procedure is essentially the same as one step of the basecase
algorithm done in a Q limb base, though with the trial quotient test done only
with the high limbs, not an entire Q limb “digit” product. The correctness
of this weaker test can be established by following the argument of Knuth
section 4.3.1 exercise 20 but with the *v2*q>b*r+u2* condition appropriately relaxed.