[issue22477] GCD in Fractions

Mark Dickinson added the comment: As far as I know, we're all done here. -- status: pending -> open ___ Python tracker ___

[issue22477] GCD in Fractions

Changes by Mark Dickinson : -- resolution: -> fixed stage: -> resolved ___ Python tracker ___

[issue22477] GCD in Fractions

Changes by Mark Dickinson : -- status: open -> closed ___ Python tracker ___ ___

[issue22477] GCD in Fractions

Serhiy Storchaka added the comment: Is there something to do with this issue? -- nosy: +serhiy.storchaka status: open -> pending ___ Python tracker ___

[issue22477] GCD in Fractions

gladman added the comment: I notice on the documentation for Python 3.5 that this proposed addition is not mentioned. Is it still the intention to add this proposed change to Python 3.5? -- ___ Python tracker rep...@bugs.python.org

[issue22477] GCD in Fractions

STINNER Victor added the comment: I see that the issue #22486 is still open. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477 ___ ___

[issue22477] GCD in Fractions

gladman added the comment: You might be right that it is not worth adding the ability to handle a variable number of parameters in the new gcd. But this depends on whether you are right that this would add a significant burden to the implementation. I am not sure that it would. But for

[issue22477] GCD in Fractions

Stefan Behnel added the comment: it might be worth at least considering how a 'one or more parameter' gcd compares on performance grounds with a two parameter one. There shouldn't be a difference in practice. The bulk of the work is in the algorithm that finds the GCD of two numbers, and

Re: GCD in Fractions

Mark Lawrence breamore...@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

Re: GCD in Fractions

On Thu, Sep 25, 2014 at 8:56 PM, Akira Li 4kir4...@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.

[issue22477] GCD in Fractions

Stefan Behnel added the comment: Also see issue 22486. There is an unmerged C implementation in the old issue 1682 that would go into the math module. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477

[issue22477] GCD in Fractions

Matthew Barnett added the comment: After some thought, I've come to the conclusion that the GCD of two integers should be negative only if both of those integers are negative. The basic algorithm is that you find all of the prime factors of the integers and then return the product of the

[issue22477] GCD in Fractions

gladman added the comment: On 25/09/2014 15:55, Matthew Barnett wrote: Matthew Barnett added the comment: After some thought, I've come to the conclusion that the GCD of two integers should be negative only if both of those integers are negative. The basic algorithm is that you find

[issue22477] GCD in Fractions

Matthew Barnett added the comment: As it appears that there isn't general agreement on how to calculate the GCD when negative numbers are involved, I needed to look for another way of thinking about it. Splitting off the sign as another factor was what I came up with. Pragmatism beats

[issue22477] GCD in Fractions

Stefan Behnel added the comment: IMHO, the most straight forward way for a new gcd() function to work would be to always, predictably return a non-negative value and let users handle all cases themselves where a negative sign of any or all input values has a specific meaning to them. That's

[issue22477] GCD in Fractions

Mark Dickinson added the comment: IMHO, the most straight forward way for a new gcd() function to work would be to always, predictably return a non-negative value. Yes. Any new gcd implementation (in the math module, for example) should definitely return the unique nonnegative gcd of its

[issue22477] GCD in Fractions

Mark Dickinson added the comment: On second thoughts, I'm withdrawing this part of the proposal: 3. Remove fractions.gcd in Python 3.6. That just falls under 'gratuitous breakage'. Instead, we should modify the `fractions.gcd` docstring to point users to math.gcd. --

[issue22477] GCD in Fractions

supports a common idiom for checking for co-prime numbers by testing if the gcd is equal to 1. But we are not starting from scratch and it is hard to see that it makes much sense to change the GCD in fractions given the backwards compatibilty issues that this might create. So, it would seem that we

[issue22477] GCD in Fractions

gladman added the comment: On 25/09/2014 17:44, Mark Dickinson wrote: Mark Dickinson added the comment: IMHO, the most straight forward way for a new gcd() function to work would be to always, predictably return a non-negative value. Yes. Any new gcd implementation (in the math

[issue22477] GCD in Fractions

fractions.gcd docstring Return signed version of math.gcd. ... I think this would be double win (users get fast, 'proper' gcd; fractions work faster too). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477

[issue22477] GCD in Fractions

Stefan Behnel added the comment: +1 for Mark Terry, just for the record -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477 ___ ___

[issue22477] GCD in Fractions

Changes by Akira Li 4kir4...@gmail.com: -- nosy: -akira ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477 ___ ___ Python-bugs-list mailing list

[issue22477] GCD in Fractions

Matthew Barnett added the comment: +1 for leaving it to the user to make it negative if so desired. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477 ___

[issue22477] GCD in Fractions

gladman added the comment: On 25/09/2014 17:44, Mark Dickinson wrote: Mark Dickinson added the comment: IMHO, the most straight forward way for a new gcd() function to work would be to always, predictably return a non-negative value. Yes. Any new gcd implementation (in the math

Re: GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

On Wed, Sep 24, 2014 at 5:44 AM, Steven D'Aprano steve+comp.lang.pyt...@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

Re: GCD in Fractions

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

Re: GCD in Fractions

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()) ==

Re: GCD in Fractions

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,

Re: GCD in Fractions

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

Re: GCD in Fractions

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.

Re: GCD in Fractions

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

Re: GCD in Fractions

Steven D'Aprano steve+comp.lang.pyt...@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

Re: GCD in Fractions

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

[issue22477] GCD in Fractions

the mathematical properties expected of this function. If necessary a local function in the fractions module could maintain the current behaviour. -- components: Library (Lib) messages: 227410 nosy: b...@gladman.plus.com priority: normal severity: normal status: open title: GCD in Fractions type

[issue22477] GCD in Fractions

STINNER Victor added the comment: See also issue #22464. -- nosy: +haypo ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477 ___ ___

[issue22477] GCD in Fractions

Mark Dickinson added the comment: +1 from me. -- nosy: +mark.dickinson ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477 ___ ___

[issue22477] GCD in Fractions

Mark Dickinson added the comment: The current `gcd` definition is almost accidental, in that it just happens to be what's convenient for use in normalisation in the Fraction type. If people are using it as a standalone implementation of gcd, independent of the fractions module, then defining

[issue22477] GCD in Fractions

gladman added the comment: On 24/09/2014 08:58, Mark Dickinson wrote: Mark Dickinson added the comment: The current `gcd` definition is almost accidental, in that it just happens to be what's convenient for use in normalisation in the Fraction type. If people are using it as a

[issue22477] GCD in Fractions

by my assertion that the fractions module gcd is not wrong: it returns 'a' greatest common divisor for arbitrary integer inputs. A bit more: the concept of greatest common divisor is slightly ambiguous: you can define the notion of a greatest common divisor for an arbitrary commutative ring

[issue22477] GCD in Fractions

) than I care to remember, and I have plenty of my own references. I stand by my assertion that the fractions module gcd is not wrong: it returns 'a' greatest common divisor for arbitrary integer inputs. Well we will just have to agree to disagree

[issue22477] GCD in Fractions

Mark Dickinson added the comment: Well we will just have to agree to disagree on this :-) Sure. In the mean time, would you be interested in writing a patch targeting Python 3.5? (Irrespective of the arguments about the definition, I don't think this is a change that could be applied in a

[issue22477] GCD in Fractions

gcd should go (fractions or math or ...). And if it goes in math and/or we want to speed it up, I would have to learn how to integrate Python and C code (I have done almost none of this before). So I would much appreciate further discusssion of this possible change and how best to implement

[issue22477] GCD in Fractions

Stefan Behnel added the comment: I suggest adding a new implementation instead of replacing the current function in the fractions module. As Mark noted, the current gcd() is more of a sideeffect of the fractions module, but there's no real need to change that. It works perfectly ok for a) the

[issue22477] GCD in Fractions

Akira Li added the comment: Whether or not gcd(a, b) == gcd(|a|, |b|) depends on the definition if we believe to Stepanov of C++ STL fame who mentions in his lecture [1] [1] http://www.stepanovpapers.com/gcd.pdf that the current implementation that uses two operation __bool__ and __mod__:

[issue22477] GCD in Fractions

Steven D'Aprano added the comment: I would be a lot more cautious about changing the gcd function. As Mark says, there is *not* a single well-defined meaning of the gcd for negative arguments. Even Wolfram can't decide which to use: Mathworld gives one interpretation, Mathematica the

[issue22477] GCD in Fractions

Steven D'Aprano added the comment: If we are considering adding a new gcd elsewhere (say, in the math module), then it should accept any arbitrary number of arguments, not just two. (At least one argument though.) Also, Mathematica supports the GCD of rational numbers, not just integers.

[issue22477] GCD in Fractions

Wolfgang Maier added the comment: Wouldn't it make more sense to change gcd() in the fractions module to return only positive integers? The current gcd could become _gcd for private use by fractions, and the new wrapper gcd could just be implemented as: def gcd(a,b): return abs(_gcd(a, b

[issue22477] GCD in Fractions

Terry J. Reedy added the comment: If nothing else, the doc for fractions.gcd Return the greatest common divisor is wrong and should be changed. The negative of the greatest common divisor is the least common divisor in an integer range. The doc should say Return the greatest common divisor or

[issue22477] GCD in Fractions

Terry J. Reedy added the comment: Or Return a greatest magniture common divisor ..., there being two gmcds to choose from. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22477 ___

[issue22477] GCD in Fractions

Mark Dickinson added the comment: The negative of the greatest common divisor is the least common divisor in an integer range. That depends on your choice of definitions: it's perfectly reasonable to see it as another greatest common divisor, if you interpret greatest as being with respect

[issue22477] GCD in Fractions

gladman added the comment: On 24/09/2014 19:01, Mark Dickinson wrote: Mark Dickinson added the comment: The negative of the greatest common divisor is the least common divisor in an integer range. That depends on your choice of definitions: it's perfectly reasonable to see it as

[issue22477] GCD in Fractions

gladman added the comment: On 24/09/2014 17:24, Wolfgang Maier wrote: Wolfgang Maier added the comment: [snip] An aspect that hasn't really been discussed so far on the mailing list is that this is *not* only about whether the gcd of negative integers should be negative or positive, but

GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

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):

Re: GCD in Fractions

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. -- https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

On Wed, Sep 24, 2014 at 12:37 AM, blindanagram no...@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

Re: GCD in Fractions

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

Re: GCD in Fractions

On Tue, Sep 23, 2014 at 10:38 AM, Wolfgang Maier wolfgang.ma...@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

Re: GCD in Fractions

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

Re: GCD in Fractions

On 23/09/2014 18:20, Ian Kelly wrote: On Tue, Sep 23, 2014 at 10:38 AM, Wolfgang Maier wolfgang.ma...@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

Re: GCD in Fractions

On Tue, Sep 23, 2014 at 11:26 AM, Stefan Behnel stefan...@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

Re: GCD in Fractions

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

Re: GCD in Fractions

On Tue, Sep 23, 2014 at 11:39 AM, Ian Kelly ian.g.ke...@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

Re: GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

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*

Re: GCD in Fractions

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

Re: GCD in Fractions

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

Re: GCD in Fractions

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