GNU Info

(gmp.info)Exact Division

---

Next: Exact Remainder Prev: Divide and Conquer Division Up: Division Algorithms

---

Enter node , (file) or (file)node

Exact Division
--------------

   A so-called exact division is when the dividend is known to be an
exact multiple of the divisor.  Jebelean's exact division algorithm
uses this knowledge to make some significant optimizations (Note:
References).

   The idea can be illustrated in decimal for example with 368154
divided by 543.  Because the low digit of the dividend is 4, the low
digit of the quotient must be 8.  This is arrived at from 4*7 mod 10,
using the fact 7 is the modular inverse of 3 (the low digit of the
divisor), since 3*7 == 1 mod 10.  So 8*543=4344 can be subtracted from
the dividend leaving 363810.  Notice the low digit has become zero.

   The procedure is repeated at the second digit, with the next
quotient digit 7 (7 == 1*7 mod 10), subtracting 7*543=3801, leaving
325800.  And finally at the third digit with quotient digit 6 (8*7 mod
10), subtracting 6*543=3258 leaving 0.  So the quotient is 678.

   Notice however that the multiplies and subtractions don't need to
extend past the low three digits of the dividend, since that's enough
to determine the three quotient digits.  For the last quotient digit no
subtraction is needed at all.  On a 2NxN division like this one, only
about half the work of a normal basecase division is necessary.

   For an NxM exact division producing Q=N-M quotient limbs, the saving
over a normal basecase division is in two parts.  Firstly, each of the
Q quotient limbs needs only one multiply, not a 2x1 divide and
multiply.  Secondly, the crossproducts are reduced when Q>M to
Q*M-M*(M+1)/2, or when Q<=M to Q*(Q-1)/2.  Notice the savings are
complementary.  If Q is big then many divisions are saved, or if Q is
small then the crossproducts reduce to a small number.

   The modular inverse used is calculated efficiently by
`modlimb_invert' in `gmp-impl.h'.  This does four multiplies for a
32-bit limb, or six for a 64-bit limb.  `tune/modlinv.c' has some
alternate implementations that might suit processors better at bit
twiddling than multiplying.

   The sub-quadratic exact division described by Jebelean in "Exact
Division with Karatsuba Complexity" is not currently implemented.  It
uses a rearrangement similar to the divide and conquer for normal
division (Note: Divide and Conquer Division), but operating from low
to high.  A further possibility not currently implemented is
"Bidirectional Exact Integer Division" by Krandick and Jebelean which
forms quotient limbs from both the high and low ends of the dividend,
and can halve once more the number of crossproducts needed in a 2NxN
division.

   A special case exact division by 3 exists in `mpn_divexact_by3',
supporting Toom-3 multiplication and `mpq' canonicalizations.  It forms
quotient digits with a multiply by the modular inverse of 3 (which is
`0xAA..AAB') and uses two comparisons to determine a borrow for the next
limb.  The multiplications don't need to be on the dependent chain, as
long as the effect of the borrows is applied.  Only a few optimized
assembler implementations currently exist.