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 | 15 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 2 of 2 — ← Prev page 1 [2]
| From | Terry Reedy <tjreedy@udel.edu> |
|---|---|
| Date | 2014-09-24 13:42 -0400 |
| Message-ID | <mailman.14326.1411580570.18130.python-list@python.org> |
| In reply to | #78275 |
On 9/24/2014 7:44 AM, Steven D'Aprano wrote: > 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. [convincing evidence of the above snipped] The negative of the greatest common divisor is the least common divisor (when the range includes negative integers). If a 'gcd' is allowed to be negative, one must re-interpret 'gcd' as abbreviating 'greatest-magnitude common divisor'. It then might be better called 'gmcd'. -- Terry Jan Reedy
[toc] | [prev] | [next] | [standalone]
| From | Johann Hibschman <jhibschman@gmail.com> |
|---|---|
| Date | 2014-09-24 14:09 -0400 |
| Message-ID | <osxr3z0j3g7.fsf@gmail.com> |
| In reply to | #78275 |
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
[toc] | [prev] | [next] | [standalone]
| From | Mark Lawrence <breamoreboy@yahoo.co.uk> |
|---|---|
| Date | 2014-09-23 20:30 +0100 |
| Message-ID | <mailman.14285.1411500669.18130.python-list@python.org> |
| In reply to | #78234 |
On 23/09/2014 18:43, blindanagram wrote: > 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. > All you need do is raise an issue on the bug tracker, provide a patch to code, test and docs and the job is done. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence
[toc] | [prev] | [next] | [standalone]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-09-23 22:48 +0100 |
| Message-ID | <kdOdnedOutE0d7zJnZ2dnUVZ7oudnZ2d@brightview.co.uk> |
| In reply to | #78242 |
On 23/09/2014 20:30, Mark Lawrence wrote: > On 23/09/2014 18:43, blindanagram wrote: >> 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. >> > All you need do is raise an issue on the bug tracker, provide a patch to > code, test and docs and the job is done. Thank you for your helpful comment. I will happily do this if after discussion here there is a reasonable level of support and encouragement for such an action. However, there is at least one person here who takes the view that backward compatibility outranks mathematical correctness and I don't want to find that 'I am banging my head against a brick wall' if this is likely to be the stance that Python developers take.
[toc] | [prev] | [next] | [standalone]
| From | Mark Lawrence <breamoreboy@yahoo.co.uk> |
|---|---|
| Date | 2014-09-23 23:52 +0100 |
| Message-ID | <mailman.14294.1411512796.18130.python-list@python.org> |
| In reply to | #78250 |
On 23/09/2014 22:48, blindanagram wrote: > On 23/09/2014 20:30, Mark Lawrence wrote: >> On 23/09/2014 18:43, blindanagram wrote: >>> 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. >>> >> All you need do is raise an issue on the bug tracker, provide a patch to >> code, test and docs and the job is done. > > Thank you for your helpful comment. I will happily do this if after > discussion here there is a reasonable level of support and encouragement > for such an action. > > However, there is at least one person here who takes the view that > backward compatibility outranks mathematical correctness and I don't > want to find that 'I am banging my head against a brick wall' if this is > likely to be the stance that Python developers take. > From https://docs.python.org/devguide/experts.html Mark Dickinson and Raymond Hettinger are listed as the maintainers of the fractions module. If they're not lurking here I'd guess the simplest way to contact them is via the bug tracker. That also gives the official mechanism as to whether or not an enhancement request such as this is accepted or rejected and the rationale behind the decision. For example it is feasible that the current behaviour would be deprecated in Python 3.5 and changed in 3.6 to match your needs. I don't have enough knowledge of the maths to say one way or another, but I'm certain that others will chip in with their comments. Best of luck anyway :) -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence
[toc] | [prev] | [next] | [standalone]
| From | Mark Lawrence <breamoreboy@yahoo.co.uk> |
|---|---|
| Date | 2014-09-24 11:42 +0100 |
| Message-ID | <mailman.14304.1411555403.18130.python-list@python.org> |
| In reply to | #78250 |
On 23/09/2014 23:52, Mark Lawrence wrote: > On 23/09/2014 22:48, blindanagram wrote: >> On 23/09/2014 20:30, Mark Lawrence wrote: >>> On 23/09/2014 18:43, blindanagram wrote: >>> All you need do is raise an issue on the bug tracker, provide a patch to >>> code, test and docs and the job is done. >> >> Thank you for your helpful comment. I will happily do this if after >> discussion here there is a reasonable level of support and encouragement >> for such an action. >> >> However, there is at least one person here who takes the view that >> backward compatibility outranks mathematical correctness and I don't >> want to find that 'I am banging my head against a brick wall' if this is >> likely to be the stance that Python developers take. >> > > From https://docs.python.org/devguide/experts.html Mark Dickinson and > Raymond Hettinger are listed as the maintainers of the fractions module. > If they're not lurking here I'd guess the simplest way to contact them > is via the bug tracker. That also gives the official mechanism as to > whether or not an enhancement request such as this is accepted or > rejected and the rationale behind the decision. For example it is > feasible that the current behaviour would be deprecated in Python 3.5 > and changed in 3.6 to match your needs. I don't have enough knowledge > of the maths to say one way or another, but I'm certain that others will > chip in with their comments. Best of luck anyway :) > Somebody got there first http://bugs.python.org/issue22477 -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence
[toc] | [prev] | [next] | [standalone]
| From | Mark Dickinson <mdickinson@enthought.com> |
|---|---|
| Date | 2014-09-24 11:14 +0000 |
| Message-ID | <mailman.14305.1411557316.18130.python-list@python.org> |
| In reply to | #78250 |
Mark Lawrence <breamoreboy <at> yahoo.co.uk> writes:
> Somebody got there first http://bugs.python.org/issue22477
I think there's good reason to suspect that Brian Gladman and
blindanagram are one and the same. :-)
>>> sorted("BrianGladman".lower()) == sorted("blindanagram")
True
[toc] | [prev] | [next] | [standalone]
| From | Mark Lawrence <breamoreboy@yahoo.co.uk> |
|---|---|
| Date | 2014-09-24 17:34 +0100 |
| Message-ID | <mailman.14322.1411576500.18130.python-list@python.org> |
| In reply to | #78250 |
On 24/09/2014 12:14, Mark Dickinson wrote:
> Mark Lawrence <breamoreboy <at> yahoo.co.uk> writes:
>> Somebody got there first http://bugs.python.org/issue22477
>
> I think there's good reason to suspect that Brian Gladman and
> blindanagram are one and the same. :-)
>
>>>> sorted("BrianGladman".lower()) == sorted("blindanagram")
> True
>
Is that considered proof that I still reign supreme as the most
unobservant person on the planet? :)
--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.
Mark Lawrence
[toc] | [prev] | [next] | [standalone]
| From | blindanagram <noone@nowhere.net> |
|---|---|
| Date | 2014-09-24 18:31 +0100 |
| Message-ID | <fP2dnUmJkYOQnb7JnZ2dnUVZ7tidnZ2d@brightview.co.uk> |
| In reply to | #78297 |
On 24/09/2014 17:34, Mark Lawrence wrote:
> On 24/09/2014 12:14, Mark Dickinson wrote:
>> Mark Lawrence <breamoreboy <at> yahoo.co.uk> writes:
>>> Somebody got there first http://bugs.python.org/issue22477
>>
>> I think there's good reason to suspect that Brian Gladman and
>> blindanagram are one and the same. :-)
>>
>>>>> sorted("BrianGladman".lower()) == sorted("blindanagram")
>> True
>>
> Is that considered proof that I still reign supreme as the most
> unobservant person on the planet? :)
I am afraid not - you are far from alone :-)
I have used this alias for quite a few years now on sci.crypt without
people realising who 'owns' it (there are reasons why people on
sci.crypt might discover this).
[toc] | [prev] | [next] | [standalone]
| From | Akira Li <4kir4.1i@gmail.com> |
|---|---|
| Date | 2014-09-25 14:56 +0400 |
| Message-ID | <mailman.14352.1411642602.18130.python-list@python.org> |
| In reply to | #78250 |
Mark Lawrence <breamoreboy@yahoo.co.uk> writes:
> On 24/09/2014 12:14, Mark Dickinson wrote:
>> Mark Lawrence <breamoreboy <at> yahoo.co.uk> writes:
>>> Somebody got there first http://bugs.python.org/issue22477
>>
>> I think there's good reason to suspect that Brian Gladman and
>> blindanagram are one and the same. :-)
>>
>>>>> sorted("BrianGladman".lower()) == sorted("blindanagram")
>> True
>>
>
> Is that considered proof that I still reign supreme as the most
> unobservant person on the planet? :)
It might mean that you are *too observant* because I've noticed that
the order of the letters is different just now.
http://english.stackexchange.com/questions/8628/is-it-true-that-only-the-positions-of-the-first-and-last-letter-in-a-word-matter
[spoiler: it is not true in general but brains can do a lot of
"error-correction" subconsciously]
--
Akira
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-09-25 21:03 +1000 |
| Message-ID | <mailman.14353.1411642997.18130.python-list@python.org> |
| In reply to | #78250 |
On Thu, Sep 25, 2014 at 8:56 PM, Akira Li <4kir4.1i@gmail.com> wrote: > It might mean that you are *too observant* because I've noticed that > the order of the letters is different just now. > > http://english.stackexchange.com/questions/8628/is-it-true-that-only-the-positions-of-the-first-and-last-letter-in-a-word-matter > > [spoiler: it is not true in general but brains can do a lot of > "error-correction" subconsciously] It's definitely not true, and has been frequently debunked. But brains do error-correct, and not just on the order of letters. I spend a lot of time on MUDs, where the typographical quality is comparable to IRC; those of you who hang out on #python can probably attest to the same thing. When people type quickly, they make errors... and they're often the same errors (one hand not on the home keys, two letters transposed, omitted letters, etc). Those of us who hang out there tend to get familiar enough with the errors to autocorrect them - and sometimes not even notice them :) ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2014-09-23 11:39 -0600 |
| Message-ID | <mailman.14278.1411494006.18130.python-list@python.org> |
| In reply to | #78209 |
On Tue, Sep 23, 2014 at 11:26 AM, Stefan Behnel <stefan_ml@behnel.de> 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. > > 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 I don't think documentation is sufficient in this case. This is the kind of thing though that is easy to forget about if you haven't read the documentation recently. And with a function like gcd, one generally wouldn't expect to *need* to read the documentation. >> 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. I'm not convinced it's all that clear. In addition to Mathworld and Wikipedia that were already cited, ProofWiki provides an actual proof that gcd(a, b) = gcd(|a|, |b|), by way of noting that a and |a| have the same factors.
[toc] | [prev] | [next] | [standalone]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2014-09-23 11:40 -0600 |
| Message-ID | <mailman.14279.1411494462.18130.python-list@python.org> |
| In reply to | #78209 |
On Tue, Sep 23, 2014 at 11:39 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote: > I'm not convinced it's all that clear. In addition to Mathworld and > Wikipedia that were already cited, ProofWiki provides an actual proof > that gcd(a, b) = gcd(|a|, |b|), by way of noting that a and |a| have > the same factors. I forgot to include the link: https://proofwiki.org/wiki/GCD_for_Negative_Integers
[toc] | [prev] | [next] | [standalone]
| From | Stefan Behnel <stefan_ml@behnel.de> |
|---|---|
| Date | 2014-09-23 20:09 +0200 |
| Message-ID | <mailman.14282.1411495781.18130.python-list@python.org> |
| In reply to | #78209 |
Ian Kelly schrieb am 23.09.2014 um 19:39: > On Tue, Sep 23, 2014 at 11:26 AM, 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. >> >> 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 > > I don't think documentation is sufficient in this case. This is the > kind of thing though that is easy to forget about if you haven't read > the documentation recently. And with a function like gcd, one > generally wouldn't expect to *need* to read the documentation. Interesting. I would definitely consult the documentation first thing if I were considering to pass negative values into a gcd function - into any implementation, even if I had been the very author myself, just two months back. I might even take a look at the source to make sure the docs are correct and up to date, and to look for comments that give further insights. But maybe that's just me. Stefan
[toc] | [prev] | [next] | [standalone]
| From | Terry Reedy <tjreedy@udel.edu> |
|---|---|
| Date | 2014-09-23 15:31 -0400 |
| Message-ID | <mailman.14286.1411500739.18130.python-list@python.org> |
| In reply to | #78199 |
On 9/23/2014 4:16 AM, blindanagram wrote: > 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, Since the doc says "the result will have the same sign as b", this is intentinal. However, I consider this a *design* bug. Both -1 and +1 are common divisors, and 1 is the greatest. So I consider the previous line "Calculate the Greatest Common Divisor of a and b" to be incorrect. > 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. > -- Terry Jan Reedy
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | comp.lang.python
csiph-web