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


Groups > comp.lang.python > #78304

Re: GCD in Fractions

From Johann Hibschman <jhibschman@gmail.com>
Newsgroups comp.lang.python
Subject Re: GCD in Fractions
Date 2014-09-24 14:09 -0400
Organization A noiseless patient Spider
Message-ID <osxr3z0j3g7.fsf@gmail.com> (permalink)
References (3 earlier) <mailman.14277.1411493200.18130.python-list@python.org> <CYmdneCJKbm7LLzJnZ2dnUVZ7vadnZ2d@brightview.co.uk> <mailman.14280.1411494972.18130.python-list@python.org> <tfidne0ioO6jdbzJnZ2dnUVZ7rednZ2d@brightview.co.uk> <5422ae8b$0$29980$c3e8da3$5496439d@news.astraweb.com>

Show all headers | View raw


Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:

> blindanagram wrote:
>
>> Seccondly (as others here have pointed out), the mathematical properties
>> of the greatest common divisor are well defined for both positive and
>> negative integers.
>
> You keep saying that, but it simply is not true. Different people use
> different definitions. Some refuse to allow negative arguments at all. Some
> insist that the GCD must be positive. Others allow it to be negative.

I can't find a good source for allowing it to be negative, though.
Clearly, the primary use of the function is on the positive integers,
with the negatives being an extension.

> Mathworld does show one thing that suggests an interpretation for the GCD of
> negative values:
>
>  The GCD is distributive
>     GCD(ma,mb)=mGCD(a,b) 
>
> which tells us that:
>
>     GCD(-x, -y) = -GCD(x, y)
>
> And yet, Mathematica has:
>
>     GCD(-x, -y) = GCD(x, y)
>
> the very opposite of what Mathworld says, despite coming from the same
> people.

This is most likely simply them dropping the constraint that m must be
non-negative.  Wikipedia, for example, specifies it under "Properties."

> The Collins Dictionary of Mathematics (second edition, 2002) says:
>
>     highest common factor, greatest common factor, or greatest 
>     common divisor (abbrev hcf, gcf, gcd)
>
>     n, an integer d that exactly divides (sense 2) two given 
>     integers a and b, and is such that if c divides a and b, 
>     then c divides d; this definition extends to finite sets 
>     of integers and to integral domains. For example, the 
>     highest common factor of 12, 60 and 84 is 12.
>
> Yet again, we have no clear definition for negative values.

As pointed out, this definition always yields two values (positive and
negative), even for positive a and b, so there's nothing special for
negative a or b.  Typically, I've seen this augmented with "choose the
positive one" to get a single value.

> Here's an example using Euclid's algorithm to calculate the GCD of negative
> numbers, and sure enough, you get a negative result:

The algorithm is pretty irrelevant here.  gcd's not defined by a
particular algorithm to calculate it.

From everything that I've seen, mathematicians consider the gcd to be
always positive.

Now, that's not saying that fraction should implement the mathematical
gcd, if it doesn't need it.  That should be its own argument, though;
it doesn't help to add false doubt about what the gcd of negative
numbers should be.

Cheers,
Johann

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