GNU Info

(gmp.info)Exact Remainder

---

Next: Small Quotient Division Prev: Exact Division Up: Division Algorithms

---

Enter node , (file) or (file)node

Exact Remainder
---------------

   If the exact division algorithm is done with a full subtraction at
each stage and the dividend isn't a multiple of the divisor, then low
zero limbs are produced but with a remainder in the high limbs.  For
dividend a, divisor d, quotient q, and b = 2^mp_bits_per_limb, then
this remainder r is of the form

     a = q*d + r*b^n

   n represents the number of zero limbs produced by the subtractions,
that being the number of limbs produced for q.  r will be in the range
0<=r<d and can be viewed as a remainder, but one shifted up by a factor
of b^n.

   Carrying out full subtractions at each stage means the same number
of cross products must be done as a normal division, but there's still
some single limb divisions saved.  When d is a single limb some
simplifications arise, providing good speedups on a number of
processors.

   `mpn_bdivmod', `mpn_divexact_by3', `mpn_modexact_1_odd' and the
`redc' function in `mpz_powm' differ subtly in how they return r,
leading to some negations in the above formula, but all are essentially
the same.

   Clearly r is zero when a is a multiple of d, and this leads to
divisibility or congruence tests which are potentially more efficient
than a normal division.

   The factor of b^n on r can be ignored in a GCD when d is odd, hence
the use of `mpn_bdivmod' in `mpn_gcd', and the use of
`mpn_modexact_1_odd' by `mpn_gcd_1' and `mpz_kronecker_ui' etc (Note:
Greatest Common Divisor Algorithms).

   Montgomery's REDC method for modular multiplications uses operands
of the form of x*b^-n and y*b^-n and on calculating (x*b^-n)*(y*b^-n)
uses the factor of b^n in the exact remainder to reach a product in the
same form (x*y)*b^-n (Note: Modular Powering Algorithm).

   Notice that r generally gives no useful information about the
ordinary remainder a mod d since b^n mod d could be anything.  If
however b^n == 1 mod d, then r is the negative of the ordinary
remainder.  This occurs whenever d is a factor of b^n-1, as for example
with 3 in `mpn_divexact_by3'.  Other such factors include 5, 17 and
257, but no particular use has been found for this.