Cofactor canonicalisation of mpn_gcdext

Torbjorn Granlund tg at
Sun May 8 17:22:40 CEST 2011

nisse at (Niels Möller) writes:

  Torbjorn Granlund <tg at> 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 mailing list