DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 

(gmp.info.gz) Exact Remainder

Info Catalog (gmp.info.gz) Exact Division (gmp.info.gz) Division Algorithms (gmp.info.gz) Small Quotient Division
 
 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, 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 (
 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 ( 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'.  For a 32 or 64 bit limb other such
 factors include 5, 17 and 257, but no particular use has been found for
 this.
 
Info Catalog (gmp.info.gz) Exact Division (gmp.info.gz) Division Algorithms (gmp.info.gz) Small Quotient Division
automatically generated byinfo2html