Division call in mpn_gcd
nisse at lysator.liu.se
Fri Feb 24 15:10:38 CET 2012
Torbjorn Granlund <tg at gmplib.org> writes:
> nisse at lysator.liu.se (Niels Möller) writes:
> IIRC, bdiv and redc have slightly different notions on what the
> "remainder" is, but I imagine either variant would fine for the gcd
> Perhaps this is the reason for keeping redc separate?
IIRC, bdiv functions return a borrow, meaning that the remainder
corresponding to the computed quotient is negative, while red returns a
carry which means that the computed remainder is a bit too large.
And then the questions was if a remainder-only function should follow
the redc convention, since that's the most important use, or the bdiv_qr
convention, for consistency.
> There are a couple of other divisions in the gcd code where the quotient
> is similarly unwanted: The initial division in mpn_gcdext,
> Really? Doesn't that quotient affect the cofactors?
It affects one of the cofactors: the one which we're not going to
> If tdiv_qr is good enough now, bdiv_qr ought to be good enough to be
> worth as a separate improvement.
I agree, but I can't promise I'll get around to do that soon.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel