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