GNU Info

(gmp.info)Small Quotient Division

---

Prev: Exact Remainder Up: Division Algorithms

---

Enter node , (file) or (file)node

Small Quotient Division
-----------------------

   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.