GCD in Fractions
Steven D'Aprano
steve+comp.lang.python at pearwood.info
Tue Sep 23 14:50:21 CEST 2014
blindanagram wrote:
> What is the rationale for gcd(x, y) in Fractions returning a negative
> value when y is negtive?
Good question.
Normally, gcd is only defined for non-negative integers. Wolfram Mathworld,
for example, doesn't mention negative values at all (as far as I can see):
http://mathworld.wolfram.com/GreatestCommonDivisor.html
although buried deep in the documentation for Mathematica's GCD function is
hidden the fact that it treats GCD(-a, -b) the same as GCD(a, b):
http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/
and sure enough Wolfram Alpha tells me that the GCD of *all* of:
(100, 20)
(-100, 20)
(100, -20)
(-100, -20)
are equal to +20. On the other hand, Excel and LibreOffice both give an
error for the GCD of a negative value, and I've seen versions of gcd()
which do the same as fractions.gcd. So I think there is not one single
standard way to extend GCD to negative numbers.
> For example gcd(3, -7) returns -1, which means that a co-prime test that
> would work in many other languages 'if gcd(x, y) == 1' will fail in
> Python for negative y.
True, but either of:
abs(gcd(x, y)) == 1
gcd(x, y) in (1, -1)
will work.
> And, of course, since -|x| is less than |x|, returning -|x| rather than
> |x| is not returning the greatest common divisor of x and y when y is
> negative.
That's a good argument for gcd if it were in a general maths module, but
since it is specifically used for generating fractions, I guess that the
developers won't be very convinced by that.
--
Steven
More information about the Python-list
mailing list