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 15 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 2 of 2 — ← Prev page 1 [2]


#78303

FromTerry Reedy <tjreedy@udel.edu>
Date2014-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]


#78304

FromJohann Hibschman <jhibschman@gmail.com>
Date2014-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]


#78242

FromMark Lawrence <breamoreboy@yahoo.co.uk>
Date2014-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]


#78250

Fromblindanagram <noone@nowhere.net>
Date2014-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]


#78258

FromMark Lawrence <breamoreboy@yahoo.co.uk>
Date2014-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]


#78272

FromMark Lawrence <breamoreboy@yahoo.co.uk>
Date2014-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]


#78273

FromMark Dickinson <mdickinson@enthought.com>
Date2014-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]


#78297

FromMark Lawrence <breamoreboy@yahoo.co.uk>
Date2014-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]


#78302

Fromblindanagram <noone@nowhere.net>
Date2014-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]


#78334

FromAkira Li <4kir4.1i@gmail.com>
Date2014-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]


#78335

FromChris Angelico <rosuav@gmail.com>
Date2014-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]


#78233

FromIan Kelly <ian.g.kelly@gmail.com>
Date2014-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]


#78235

FromIan Kelly <ian.g.kelly@gmail.com>
Date2014-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]


#78239

FromStefan Behnel <stefan_ml@behnel.de>
Date2014-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]


#78243

FromTerry Reedy <tjreedy@udel.edu>
Date2014-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