[issue22477] GCD in Fractions

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

[issue22477] GCD in Fractions

Changes by Mark Dickinson : -- resolution: -> fixed stage: -> resolved ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue22477] GCD in Fractions

Changes by Mark Dickinson : -- status: open -> closed ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://m

[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

STINNER Victor added the comment: I see that the issue #22486 is still open. -- ___ Python tracker ___ ___ Python-bugs-list mailing li

[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

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

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

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

[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 ___ ___ Pyth

[issue22477] GCD in Fractions

Changes by Akira Li <4kir4...@gmail.com>: -- nosy: -akira ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http

[issue22477] GCD in Fractions

Stefan Behnel added the comment: +1 for Mark & Terry, just for the record -- ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue22477] GCD in Fractions

Terry J. Reedy added the comment: I strongly agree with Mark's revised plan: 1. add a fast C-coded math.gcd returning the actual greatest (in normal ordered int sense) common divisor; 2. use this for reduction of fractions in the fractions module to speed up operations on fractions. 3. revised

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

[issue22477] GCD in Fractions

gladman added the comment: On 25/09/2014 17:02, Matthew Barnett wrote: > > 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. > > Sp

[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

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 i

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

[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 purity,

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

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

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

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

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

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

[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 ___ __

[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

[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

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

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

[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__: d

[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

gladman added the comment: On 24/09/2014 11:54, Mark Dickinson wrote: > > 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 argume

[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

gladman added the comment: On 24/09/2014 10:13, Mark Dickinson wrote: > > Mark Dickinson added the comment: > >> I will willingly supply more references if you need them. > > I don't. :-) I've taught more elementary number classes and reviewed more > elementary number theory texts (including

[issue22477] GCD in Fractions

Mark Dickinson added the comment: > I will willingly supply more references if you need them. I don't. :-) I've taught more elementary number classes and reviewed more elementary number theory texts (including Rosen's) than I care to remember, and I have plenty of my own references. I stand by

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

[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

Mark Dickinson added the comment: +1 from me. -- nosy: +mark.dickinson ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue22477] GCD in Fractions

STINNER Victor added the comment: See also issue #22464. -- nosy: +haypo ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue22477] GCD in Fractions

New submission from Brian Gladman: There is a discussion of this issue on comp.lang.python The function known as 'the greatest common divisor' has a number of well defined mathematical properties for both positive and negative integers (see, for example, Elementary Number Theory by Kenneth Ros