Division call in mpn_gcd

Niels Möller 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
>   reduction.
> 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 mailing list