Cofactor canonicalisation of mpn_gcdext
tg at gmplib.org
Sun May 8 17:22:40 CEST 2011
nisse at lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund <tg at gmplib.org> writes:
> One usually defines gcd(a,0) = |a|. (But it seems that for a=0, one may
> define gcd as any positive integer, while 0 is a poor divisor.)
I mathematics, I think gcd(0,0) is usually undefined. As far as I can
find, not even Knuth defines a value the gcd function in this case. If
we don't want to raise a divide-by-zero error, I guess 0 is a reasonable
value to return (for lack of a representation of infinity).
> This code from mpz/gcdext.c looks suspicious:
> /* g = |a|, s = sign(a), t = 0. */
> ssize = SIZ (a) >= 0 ? 1 : -1;
> Since a = 0 is possible here, this is a poor computation of sgn(a).
> I pushed a fix. I also made some other minor tweaks.
I see. I totally forgot normalization for the a == b == 0 case.
Maybe the sentence "S = 0 if and only if V divides U (i.e., G = V)." in
the docs need a tweak? Actually, behaviour for both inputs zero seem to
be completely undocumented.
Perhaps we should not bother making gcd(0,0) well-defined? Instead of
my fix, perhaps we should fix the test case not to exercise this strange
More information about the gmp-devel