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


Groups > comp.lang.python > #78199 > unrolled thread

GCD in Fractions

Started byblindanagram <noone@nowhere.net>
First post2014-09-23 09:16 +0100
Last post2014-09-23 15:31 -0400
Articles 20 on this page of 35 — 13 participants

Back to article view | Back to comp.lang.python


Contents

  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

Page 1 of 2  [1] 2  Next page →


#78199 — GCD in Fractions

Fromblindanagram <noone@nowhere.net>
Date2014-09-23 09:16 +0100
SubjectGCD in Fractions
Message-ID<pfGdnaNKbb7-sbzJnZ2dnUVZ8vudnZ2d@brightview.co.uk>
What is the rationale for gcd(x, y) in Fractions returning a negative
value when y is negtive?

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.

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.

[toc] | [next] | [standalone]


#78206

FromWolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de>
Date2014-09-23 13:53 +0200
Message-ID<mailman.14256.1411473203.18130.python-list@python.org>
In reply to#78199
On 09/23/2014 10:16 AM, blindanagram wrote:
> What is the rationale for gcd(x, y) in Fractions returning a negative
> value when y is negtive?
>

I guess it is implemented this way because its main use is in the 
Fraction constructor.

> 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.
>

On the other hand, it allows:
 >>> Fraction(3, -7)
Fraction(-3, 7)

and:
 >>> Fraction(3, -7) == Fraction(-3, 7)
True

Given that the implementation is particularly useful for Fraction() it 
is debatable whether the function shouldn't be called _gcd instead of 
gcd, but otherwise it makes sense.

> 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.
>

however, you can always use abs on y before passing it to gcd.

Wolfgang

[toc] | [prev] | [next] | [standalone]


#78208

Fromblindanagram <noone@nowhere.net>
Date2014-09-23 13:48 +0100
Message-ID<Xp-dnZAMccaJ8bzJnZ2dnUVZ8iednZ2d@brightview.co.uk>
In reply to#78206
On 23/09/2014 12:53, Wolfgang Maier wrote:
> On 09/23/2014 10:16 AM, blindanagram wrote:
>> What is the rationale for gcd(x, y) in Fractions returning a negative
>> value when y is negtive?
>>
> 
> I guess it is implemented this way because its main use is in the
> Fraction constructor.

This is not guaranteed once it is exposed as a function that is
available to all Python users.

>> 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.

[snip]
> Given that the implementation is particularly useful for Fraction() it
> is debatable whether the function shouldn't be called _gcd instead of
> gcd, but otherwise it makes sense.

As you imply, it would make sense if it hadn't been exposed for more
general use.

However, I am less sure that it is sensible to have a gcd function
exposed for end user use when it conflicts with the function's usual
definition.

[toc] | [prev] | [next] | [standalone]


#78209

FromSteven D'Aprano <steve+comp.lang.python@pearwood.info>
Date2014-09-23 22:50 +1000
Message-ID<54216c8e$0$29966$c3e8da3$5496439d@news.astraweb.com>
In reply to#78199
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.




-- 
Steven

[toc] | [prev] | [next] | [standalone]


#78214

Fromblindanagram <noone@nowhere.net>
Date2014-09-23 15:37 +0100
Message-ID<6qidnUSKb8osGLzJnZ2dnUVZ8jOdnZ2d@brightview.co.uk>
In reply to#78209
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.

[toc] | [prev] | [next] | [standalone]


#78215

FromChris Angelico <rosuav@gmail.com>
Date2014-09-24 00:42 +1000
Message-ID<mailman.14263.1411483330.18130.python-list@python.org>
In reply to#78214
On Wed, Sep 24, 2014 at 12:37 AM, blindanagram <noone@nowhere.net> wrote:
> That's an argument for a private gcd within the fractions module and a a
> 'normal' version in math.

Steven's examples show that there's not really much definition of
"normal" as regards GCD of negative numbers.

ChrisA

[toc] | [prev] | [next] | [standalone]


#78224

FromWolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de>
Date2014-09-23 18:38 +0200
Message-ID<mailman.14271.1411490314.18130.python-list@python.org>
In reply to#78209
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

[toc] | [prev] | [next] | [standalone]


#78229

FromIan Kelly <ian.g.kelly@gmail.com>
Date2014-09-23 11:20 -0600
Message-ID<mailman.14276.1411492886.18130.python-list@python.org>
In reply to#78209
On Tue, Sep 23, 2014 at 10:38 AM, Wolfgang Maier
<wolfgang.maier@biologie.uni-freiburg.de> wrote:
> Maybe fractions.gcd could be renamed, but be wrapped or reimplemented
> correctly somewhere else in the stdlib or even in fractions ?

+1

I don't think the math module as suggested upthread is the right
place, as that module houses wrappers of C functions that operate on
floats. I'm also not sure where is better, though. Maybe the
reimplemented version should just keep the name fractions.gcd.

[toc] | [prev] | [next] | [standalone]


#78231

Fromblindanagram <noone@nowhere.net>
Date2014-09-23 18:31 +0100
Message-ID<r7mdnRvah4DuM7zJnZ2dnUVZ8o-dnZ2d@brightview.co.uk>
In reply to#78229
On 23/09/2014 18:20, Ian Kelly wrote:
> On Tue, Sep 23, 2014 at 10:38 AM, Wolfgang Maier
> <wolfgang.maier@biologie.uni-freiburg.de> wrote:
>> Maybe fractions.gcd could be renamed, but be wrapped or reimplemented
>> correctly somewhere else in the stdlib or even in fractions ?
> 
> +1
> 
> I don't think the math module as suggested upthread is the right
> place, as that module houses wrappers of C functions that operate on
> floats. I'm also not sure where is better, though. Maybe the
> reimplemented version should just keep the name fractions.gcd.

Since the gcd is only used once in fractions anyway, it would be easy to
change gcd here with very little impact on the performance of the
fractions module (if necessary a local version could be added to work
within fractions as it does now).

[toc] | [prev] | [next] | [standalone]


#78230

FromStefan Behnel <stefan_ml@behnel.de>
Date2014-09-23 19:26 +0200
Message-ID<mailman.14277.1411493200.18130.python-list@python.org>
In reply to#78209
Wolfgang Maier schrieb am 23.09.2014 um 18:38:
> 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.

Making a public API private is rarely a good idea. It should be enough in
this case to document the behaviour.

And, believe it or not, it actually is documented:

https://docs.python.org/3.5/library/fractions.html#fractions.gcd


> 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.

It is. Certainly for positive numbers, which clearly present the majority
of use cases. It's definitely the "normal" use case, wouldn't you say?

For negative numbers, the "expected" behaviour seems to be unclear, so the
current behaviour is just as good as any, so backwards compatibility
concerns clearly win this fight.

Stefan

[toc] | [prev] | [next] | [standalone]


#78234

Fromblindanagram <noone@nowhere.net>
Date2014-09-23 18:43 +0100
Message-ID<CYmdneCJKbm7LLzJnZ2dnUVZ7vadnZ2d@brightview.co.uk>
In reply to#78230
On 23/09/2014 18:26, Stefan Behnel wrote:
> Wolfgang Maier schrieb am 23.09.2014 um 18:38:
>> 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.
> For negative numbers, the "expected" behaviour seems to be unclear, so the
> current behaviour is just as good as any, so backwards compatibility
> concerns clearly win this fight.

The expected behaviour is not unclear for anyone who takes the
mathematical properties of the GCD seriously.  It's a shame that Python
doesn't.


[toc] | [prev] | [next] | [standalone]


#78237

FromStefan Behnel <stefan_ml@behnel.de>
Date2014-09-23 19:55 +0200
Message-ID<mailman.14280.1411494972.18130.python-list@python.org>
In reply to#78234
blindanagram schrieb am 23.09.2014 um 19:43:
> On 23/09/2014 18:26, Stefan Behnel wrote:
>> Wolfgang Maier schrieb am 23.09.2014 um 18:38:
>>> 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.
>> For negative numbers, the "expected" behaviour seems to be unclear, so the
>> current behaviour is just as good as any, so backwards compatibility
>> concerns clearly win this fight.
> 
> The expected behaviour is not unclear for anyone who takes the
> mathematical properties of the GCD seriously.  It's a shame that Python
> doesn't.

May I ask how you get from one little function in the well-defined scope of
a data type module (which is not named "math" or "integers" or "natural" or
anything like it) to the extrapolation that Python doesn't take
mathematical properties serious?

If the scope of that function's applicability does not match what you want
in your specific use case, then by all means, don't use it for your
specific use case.

Stefan

[toc] | [prev] | [next] | [standalone]


#78249

Fromblindanagram <noone@nowhere.net>
Date2014-09-23 22:38 +0100
Message-ID<tfidne0ioO6jdbzJnZ2dnUVZ7rednZ2d@brightview.co.uk>
In reply to#78237
On 23/09/2014 18:55, Stefan Behnel wrote:
> blindanagram schrieb am 23.09.2014 um 19:43:
>> On 23/09/2014 18:26, Stefan Behnel wrote:
>>> Wolfgang Maier schrieb am 23.09.2014 um 18:38:
>>>> 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.
>>> For negative numbers, the "expected" behaviour seems to be unclear, so the
>>> current behaviour is just as good as any, so backwards compatibility
>>> concerns clearly win this fight.
>>
>> The expected behaviour is not unclear for anyone who takes the
>> mathematical properties of the GCD seriously.  It's a shame that Python
>> doesn't.
> 
> May I ask how you get from one little function in the well-defined scope of
> a data type module (which is not named "math" or "integers" or "natural" or
> anything like it) to the extrapolation that Python doesn't take
> mathematical properties serious?

Firstly I have to choose between two possibilities:

(a) that the name of the function has been deliberately chosen to imply
that it calculates the mathematical function known as the 'greatest
commmon divisor'; or

(b) that the initials 'gcd' have been chosen by pure chance and the
association between this function and the 'greatest commmon divisor' has
arisen from pure coincidence.

Of these, I find (a) overwhelmingly more likely.

Seccondly (as others here have pointed out), the mathematical properties
of the greatest common divisor are well defined for both positive and
negative integers.  But the Python function called gcd doesn't have some
of these properties.

I hence conclude that Python doesn't take the mathematical properties of
the greatest common divisor seriously since it doesn't ensure that its
version of this function has these properties.

[toc] | [prev] | [next] | [standalone]


#78275

FromSteven D'Aprano <steve+comp.lang.python@pearwood.info>
Date2014-09-24 21:44 +1000
Message-ID<5422ae8b$0$29980$c3e8da3$5496439d@news.astraweb.com>
In reply to#78249
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.

GCD is well-defined for **positive integers only**.

Mathworld emphasises "positive integers" in their definition, repeating the
phrase THREE times in the first paragraph:

    The greatest common divisor, sometimes also called the highest 
    common divisor (Hardy and Wright 1979, p. 20), of two positive 
    integers a and b is the largest divisor common to a and b. For 
    example, GCD(3,5)=1, GCD(12,60)=12, and GCD(12,90)=6. The 
    greatest common divisor GCD(a,b,c,...) can also be defined for 
    three or more positive integers as the largest divisor shared 
    by all of them. Two or more positive integers that have greatest
    common divisor 1 are said to be relatively prime to one another,
    often simply just referred to as being "relatively prime." 

http://mathworld.wolfram.com/GreatestCommonDivisor.html

The rest of the page avoids mentioning anything about negative values. There
are five graphs on the page, all five are limited to only positive values.

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.

http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/


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.

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

https://answers.yahoo.com/question/index?qid=20111021023909AA8bCjB

Wikipedia, on the other hand, defines GCD:

    In mathematics, the greatest common divisor (gcd), also 
    known as the greatest common factor (gcf), highest common 
    factor (hcf), or greatest common measure (gcm), of two or 
    more integers (when at least one of them is not zero), is 
    the largest positive integer that divides the numbers 
    without a remainder.

https://en.wikipedia.org/wiki/Greatest_common_divisor


So:

- Mathworld says that GCD of two negative numbers is a negative number;

- but Mathematica says that GCD of two negative numbers is a positive;

- Wikipedia agrees with Mathematica and disagrees with Mathworld;

- Euclid's algorithm returns negative values for the GCD of two negatives;

- Collins Dictionary gives a definition which is met by either positive
  or negative results.




-- 
Steven

[toc] | [prev] | [next] | [standalone]


#78281

Fromblindanagram <noone@nowhere.net>
Date2014-09-24 14:25 +0100
Message-ID<WdGdnY7uu9nKW7_JnZ2dnUVZ7omdnZ2d@brightview.co.uk>
In reply to#78275
On 24/09/2014 12:44, Steven D'Aprano wrote:

> blindanagram wrote:
[snip]
> - Mathworld says that GCD of two negative numbers is a negative number;
> 
> - but Mathematica says that GCD of two negative numbers is a positive;
> 
> - Wikipedia agrees with Mathematica and disagrees with Mathworld;

After looking at these (and several other) on-line mathematical sites, I
realised that I would have to go back to long standing mathemmatical
references to find how the gcd is defined by those that explicitly cover
the greatest common divisor for negative integers (I did this before
raising the issue here).

All four that I have so far looked at have definitions that lead to
gcd(a, b) for integers being equal to gcd(|a|, |b|). I hope to visit a
University library shortly to review more.  Does anyone know of such a
reference that uses a definition that conflicts with gcd(a, b) for
integers being equal to gcd(|a|, |b|)?

[toc] | [prev] | [next] | [standalone]


#78295

FromStefan Behnel <stefan_ml@behnel.de>
Date2014-09-24 18:13 +0200
Message-ID<mailman.14320.1411575221.18130.python-list@python.org>
In reply to#78281
blindanagram schrieb am 24.09.2014 um 15:25:
> On 24/09/2014 12:44, Steven D'Aprano wrote:
> 
>> blindanagram wrote:
> [snip]
>> - Mathworld says that GCD of two negative numbers is a negative number;
>>
>> - but Mathematica says that GCD of two negative numbers is a positive;
>>
>> - Wikipedia agrees with Mathematica and disagrees with Mathworld;
> 
> After looking at these (and several other) on-line mathematical sites, I
> realised that I would have to go back to long standing mathemmatical
> references to find how the gcd is defined by those that explicitly cover
> the greatest common divisor for negative integers (I did this before
> raising the issue here).
> 
> All four that I have so far looked at have definitions that lead to
> gcd(a, b) for integers being equal to gcd(|a|, |b|). I hope to visit a
> University library shortly to review more.  Does anyone know of such a
> reference that uses a definition that conflicts with gcd(a, b) for
> integers being equal to gcd(|a|, |b|)?

Steven has already given sources that suggest that the result of gcd()
should be positive. Just like he gave sources that suggest the opposite.
So, the question is not how or where to find even more sources, or to
decide which of those sources is "more right" than the others, the question
is whether such a shaky ground is a reasonable foundation for breaking
other people's code.

We have an open tracker ticket now on changing *something* about the
current situation. Let's just add some new functionality somewhere if
people really want it (as in "need it for their code", not just "want it
for purity reasons" or "sleep better when they know it's out there"), but
please, everyone, stop complaining about "fractions.gcd" not catering for
your needs. It does what it's there for, even if the name is more public or
more generic than you might want. There are other ways to fix the actual
problem and move on.

Stefan

[toc] | [prev] | [next] | [standalone]


#78301

Fromblindanagram <noone@nowhere.net>
Date2014-09-24 18:05 +0100
Message-ID<vLudnUwG4PtSZL_JnZ2dnUVZ8uednZ2d@brightview.co.uk>
In reply to#78295
On 24/09/2014 17:13, Stefan Behnel wrote:

> blindanagram schrieb am 24.09.2014 um 15:25:
>> On 24/09/2014 12:44, Steven D'Aprano wrote:

[snip]
> We have an open tracker ticket now on changing *something* about the
> current situation. Let's just add some new functionality somewhere if
> people really want it (as in "need it for their code", not just "want it
> for purity reasons" or "sleep better when they know it's out there"), but
> please, everyone, stop complaining about "fractions.gcd" not catering for
> your needs. It does what it's there for, even if the name is more public or
> more generic than you might want. There are other ways to fix the actual
> problem and move on.

This has never been about my need to use fractions.gcd since I don't
even use it (I have my own implementation).

[toc] | [prev] | [next] | [standalone]


#78314

From"Robert E. Beaudoin" <rbeaudoin@comcast.net>
Date2014-09-24 19:19 -0400
Message-ID<lvvji8$cfc$1@speranza.aioe.org>
In reply to#78281
On 09/24/14 09:25, blindanagram wrote:
> On 24/09/2014 12:44, Steven D'Aprano wrote:
>
>> blindanagram wrote:
> [snip]
>> - Mathworld says that GCD of two negative numbers is a negative number;
>>
>> - but Mathematica says that GCD of two negative numbers is a positive;
>>
>> - Wikipedia agrees with Mathematica and disagrees with Mathworld;
>
> After looking at these (and several other) on-line mathematical sites, I
> realised that I would have to go back to long standing mathemmatical
> references to find how the gcd is defined by those that explicitly cover
> the greatest common divisor for negative integers (I did this before
> raising the issue here).
>
> All four that I have so far looked at have definitions that lead to
> gcd(a, b) for integers being equal to gcd(|a|, |b|). I hope to visit a
> University library shortly to review more.  Does anyone know of such a
> reference that uses a definition that conflicts with gcd(a, b) for
> integers being equal to gcd(|a|, |b|)?
>

I doubt you'll find an advanced mathematical text that has such a 
definition.  I think most abstract algebra texts would give a definition 
equivalent to saying that for any integers n and m the ideal generated 
by n and m is equal to the principal ideal generated by gcd(n,m); that 
is the heart of the matter mathematically, and this definition 
generalizes to other so-called "principal ideal domains" than the integers.

(Don't want to Google for "ideal" and "principal ideal"?  OK:  an ideal 
is a subset of the integers closed under addition of any two of its 
elements, and under multiplication of any of its elements by any 
integer; a set of integers generates an ideal if that ideal is the 
intersection of all ideals containing that set, and a principal ideal is 
an ideal generated by a singleton set.  For more elaboration, though, 
I'm going to point you at the internet, or better, some of those 
advanced texts in the library.)

After working through what the definitions of ideals and principal 
ideals imply for the the definition above of gcd, you get the statement 
that k is the (or, better, a) gcd of n and m if and only if k divides n 
and m, and any other integer that divides both n and m divides k.  The 
upshot is that, mathematically, gcd is only defined up to a change of 
sign, which helps explain why references may disagree with each other. 
Some authors may impose the restriction than gcd(n,m) >= 0 for all n and 
m (which does have the advantage that then "greatest" really means 
greatest and not just "greatest absolute value"), but that isn't really 
a necessary part of the definition as far as the mathematically 
important properties of gcd are concerned.  All that the abstract 
algebra requires is that

|gcd(n,m)| = |gcd(|n|,|m|)|.

So implementations of gcd that sometimes return a negative value are 
not, it seems to me, mathematically broken, though they might violate 
the principle of least surprise.

for-whatever-it's-worth'ly-yrs,

R. Beaudoin

[toc] | [prev] | [next] | [standalone]


#78289

FromIan Kelly <ian.g.kelly@gmail.com>
Date2014-09-24 08:26 -0600
Message-ID<mailman.14315.1411568849.18130.python-list@python.org>
In reply to#78275
On Wed, Sep 24, 2014 at 5:44 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> 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.

Well, this definition would imply that gcd(a, b) should always return
*two* results, one positive and one negative. I don't think anybody
wants that. It would make more sense to standardize on one of them,
and if we take sqrt as an example, then the result should be positive.

> Here's an example using Euclid's algorithm to calculate the GCD of negative
> numbers, and sure enough, you get a negative result:
>
> https://answers.yahoo.com/question/index?qid=20111021023909AA8bCjB

This depends entirely on your implementation of the modulo operation,
which is an issue of computing since the operator is not used in
mathematics.  The algorithm itself only specifies at each step to
solve the equation R_{n-2} = Q * R_{n-1} + R_{n}, such that |R_{n}| <
|R_{n-1}|. For any given input there can be many possible solutions,
both positive and negative, regardless of the signs of the inputs, and
it doesn't matter which solution you choose. So one could implement
Euclid's algorithm to return either a positive or negative result for
any arbitrary pair of integers.

[toc] | [prev] | [next] | [standalone]


#78299

Fromrandom832@fastmail.us
Date2014-09-24 12:49 -0400
Message-ID<mailman.14324.1411577379.18130.python-list@python.org>
In reply to#78275
On Wed, Sep 24, 2014, at 10:26, Ian Kelly wrote:
> This depends entirely on your implementation of the modulo operation,
> which is an issue of computing since the operator is not used in
> mathematics.

Wikipedia suggests that "remainders from Euclidean division" should be
used. In Euclidean division, the remainder is always positive. (whereas
either C or Python allows the modulo to be negative, in different
situations: in python [round quotient down] the modulo has the same sign
as b, whereas in C [round quotient to zero] the modulo has the same sign
as a).

def mod(a, b):
   r = a % b
   return r + abs(b) if r < 0 else r

def gcd(a, b):
    if b == 0: return a
    else: return gcd(b, mod(a, b))

This appears to give a negative result when:
  a < 0 and b == 0, obviously. A is returned as the gcd.
  a == 0 and b < 0. B is returned as the gcd
  |a| is exactly divisible by |b| and b < 0. B is returned as the gcd.

However, it still lacks the symmetry of gcd(a, b) == gcd(b, a) in some
cases. For example, gcd(-2, 6) is 2, whereas gcd(6, -2) is -2.

[toc] | [prev] | [next] | [standalone]


Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python


csiph-web