GCD in Fractions

Wolfgang Maier wolfgang.maier at biologie.uni-freiburg.de
Tue Sep 23 18:38:55 CEST 2014


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

Well, Excel and LibreOffice can hardly be considered the gold standard 
when it comes to mathematical definitions.
I'm no mathematician either, but Wikipedia has this to say about the 
properties of gcd:
http://en.wikipedia.org/wiki/Greatest_common_divisor#Properties

fractions.gcd violates several of them, like:

#2:
gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the 
greatest divisor of a is |a|.

 >>>fractions.gcd(-7, 0)
-7

#8:
The gcd is a commutative function: gcd(a, b) = gcd(b, a).

 >>>fractions.gcd(3, -7) == fractions.gcd(-7, 3)
False

While at first I thought this to be a rather irrelevant debate over 
module private vs public naming conventions, I now think the OP is 
probably right and renaming fractions.gcd to fractions._gcd may be a 
good idea.
Googling for recipes to calculate the gcd using python brings up 
fractions.gcd as a general answer (like at stackoverflow: 
http://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python) 
and it is not obvious for non-mathematicians to realize that it is NOT a 
generally acceptable solution.

Maybe fractions.gcd could be renamed, but be wrapped or reimplemented 
correctly somewhere else in the stdlib or even in fractions ?

Wolfgang





More information about the Python-list mailing list