Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #78199 > unrolled thread
| Started by | blindanagram <noone@nowhere.net> |
|---|---|
| First post | 2014-09-23 09:16 +0100 |
| Last post | 2014-09-23 15:31 -0400 |
| Articles | 20 on this page of 35 — 13 participants |
Back to article view | Back to comp.lang.python
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 →
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-09-23 09:16 +0100 |
| Subject | GCD 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]
| From | Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> |
|---|---|
| Date | 2014-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]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-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]
| From | Steven D'Aprano <steve+comp.lang.python@pearwood.info> |
|---|---|
| Date | 2014-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]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-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]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-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]
| From | Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> |
|---|---|
| Date | 2014-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]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2014-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]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-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]
| From | Stefan Behnel <stefan_ml@behnel.de> |
|---|---|
| Date | 2014-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]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-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]
| From | Stefan Behnel <stefan_ml@behnel.de> |
|---|---|
| Date | 2014-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]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-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]
| From | Steven D'Aprano <steve+comp.lang.python@pearwood.info> |
|---|---|
| Date | 2014-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]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-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]
| From | Stefan Behnel <stefan_ml@behnel.de> |
|---|---|
| Date | 2014-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]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-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]
| From | "Robert E. Beaudoin" <rbeaudoin@comcast.net> |
|---|---|
| Date | 2014-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]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2014-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]
| From | random832@fastmail.us |
|---|---|
| Date | 2014-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