Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.lang.python > #78224

Re: GCD in Fractions

From Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de>
Subject Re: GCD in Fractions
Date 2014-09-23 18:38 +0200
References <pfGdnaNKbb7-sbzJnZ2dnUVZ8vudnZ2d@brightview.co.uk> <54216c8e$0$29966$c3e8da3$5496439d@news.astraweb.com>
Newsgroups comp.lang.python
Message-ID <mailman.14271.1411490314.18130.python-list@python.org> (permalink)

Show all headers | View raw


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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 09:16 +0100
  Re: GCD in Fractions Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2014-09-23 13:53 +0200
    Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 13:48 +0100
  Re: GCD in Fractions Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-23 22:50 +1000
    Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 15:37 +0100
      Re: GCD in Fractions Chris Angelico <rosuav@gmail.com> - 2014-09-24 00:42 +1000
    Re: GCD in Fractions Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2014-09-23 18:38 +0200
    Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-23 11:20 -0600
      Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 18:31 +0100
    Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-23 19:26 +0200
      Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 18:43 +0100
        Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-23 19:55 +0200
          Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 22:38 +0100
            Re: GCD in Fractions Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-24 21:44 +1000
              Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-24 14:25 +0100
                Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-24 18:13 +0200
                Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-24 18:05 +0100
                Re: GCD in Fractions "Robert E. Beaudoin" <rbeaudoin@comcast.net> - 2014-09-24 19:19 -0400
              Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-24 08:26 -0600
              Re: GCD in Fractions random832@fastmail.us - 2014-09-24 12:49 -0400
              Re: GCD in Fractions Terry Reedy <tjreedy@udel.edu> - 2014-09-24 13:42 -0400
              Re: GCD in Fractions Johann Hibschman <jhibschman@gmail.com> - 2014-09-24 14:09 -0400
        Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-23 20:30 +0100
          Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 22:48 +0100
            Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-23 23:52 +0100
            Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-24 11:42 +0100
            Re: GCD in Fractions Mark Dickinson <mdickinson@enthought.com> - 2014-09-24 11:14 +0000
            Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-24 17:34 +0100
              Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-24 18:31 +0100
            Re: GCD in Fractions Akira Li <4kir4.1i@gmail.com> - 2014-09-25 14:56 +0400
            Re: GCD in Fractions Chris Angelico <rosuav@gmail.com> - 2014-09-25 21:03 +1000
    Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-23 11:39 -0600
    Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-23 11:40 -0600
    Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-23 20:09 +0200
  Re: GCD in Fractions Terry Reedy <tjreedy@udel.edu> - 2014-09-23 15:31 -0400

csiph-web