GCD in Fractions

blindanagram noone at nowhere.net
Tue Sep 23 16:37:39 CEST 2014


On 23/09/2014 13:50, Steven D'Aprano wrote:
> 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.

That's an argument for a private gcd within the fractions module and a a
'normal' version in math.




More information about the Python-list mailing list