(gmp.info.gz) Small Quotient Division

Info Catalog

(gmp.info.gz) Exact Remainder

(gmp.info.gz) Division Algorithms

 
 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.
 

Info Catalog

(gmp.info.gz) Exact Remainder

(gmp.info.gz) Division Algorithms