[issue22477] GCD in Fractions

[Mark Dickinson]

Mark Dickinson added the comment:

As far as I know, we're all done here.

--
status: pending -> open

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

Changes by Mark Dickinson :


--
resolution:  -> fixed
stage:  -> resolved

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

Changes by Mark Dickinson :


--
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Is there something to do with this issue?

--
nosy: +serhiy.storchaka
status: open -> pending

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[STINNER Victor]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 Python implementations of gcd and gcdm:

def gcd(a, b):
  while b:
a, b = b, a % b
  return a

def gcdm(a, *r):
  for b in r:
while b:
  a, b = b, a % b
  return a

using the second of these alone when compared with the first plus reduce on a 
1 length sequence of random numbers in 0 = r  10 ** 12 gives speed 
improvement of over 25%.  

And, since we are looking for speed improvements, a further possible 25% is a 
worthwhile gain for a common pattern of gcd use.  Which is why I believe it is 
worth asking the question.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Stefan Behnel]

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 finding the GCD of multiple 
numbers is simply

functools.reduce(math.gcd, seq_of_numbers)

Since the most common use case is finding the GCD of two numbers, I don't see a 
reason to burden the implementation with a special case here.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Stefan Behnel]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Matthew Barnett]

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 common subset (multiset, actually).

For example, to calculate the GCD of 6 and 15:

6 = [2, 3]
15 = [3, 5]
The largest common subset is [3].
Therefore the GCD is 3.

What about negative integers?

Well, what you could do is make one of the factors -1.

For example, to calculate the GCD of -6 and 15:

-6 = [-1, 2, 3]
15 = [3, 5]
The largest common subset is [3].
Therefore the GCD is 3.

Another example, to calculate the GCD of -6 and -15:

-6 = [-1, 2, 3]
-15 = [-1, 3, 5]
The largest common subset is [-1, 3].
Therefore the GCD is -3.

--
nosy: +mrabarnett

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 all of the prime factors of the integers and then 
 return the product of the common subset (multiset, actually).
 
 For example, to calculate the GCD of 6 and 15:
 
 6 = [2, 3]
 15 = [3, 5]
 The largest common subset is [3].
 Therefore the GCD is 3.
 
 What about negative integers?
 
 Well, what you could do is make one of the factors -1.
 
 For example, to calculate the GCD of -6 and 15:
 
 -6 = [-1, 2, 3]
 15 = [3, 5]
 The largest common subset is [3].
 Therefore the GCD is 3.
 
 Another example, to calculate the GCD of -6 and -15:
 
 -6 = [-1, 2, 3]
 -15 = [-1, 3, 5]
 The largest common subset is [-1, 3].
 Therefore the GCD is -3.

But should the computation of the GCD of two integers by finding the
intersection of their prime factors include -1 or 1 given that neither
of these is a prime?  :-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Matthew Barnett]

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, and all that! :-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Stefan Behnel]

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 the path of least surprise, and it's very easy 
to implement at the C level for PyLong values (as they are internally unsigned 
anyway).

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

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

In an effort to concentrate the discussion a bit, here's a specific
proposal, deliberately limited in scope:

1. Add a new (faster) math.gcd function for Python 3.5, taking two integral 
arguments, and returning the unique nonnegative greatest common divisor of 
those arguments.

2. Deprecate fractions.gcd in Python 3.5 (with a message suggesting that 
math.gcd should be used instead), but don't change its behaviour.  (The 
fractions module would likely be using math.gcd by this point.)

3. Remove fractions.gcd in Python 3.6.

I'd suggest that tangents about gcd of more than two arguments, gcd of rational 
/ Decimal / float inputs, etc. be discussed elsewhere.  Those are all things 
that can be added later if there's a real use-case.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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.
 
 Splitting off the sign as another factor was what I came up with.
 
 Pragmatism beats purity, and all that! :-)

I understand :-)

But I think we now know that we are not going to get agreement here on
grounds of principles for what the gcd should return for negative
integers.

First, in order to preserve my sanity, I am going to concede Mark's
point that returning a negative value from GCD is not wrong :-)

For negative integers we have now amassed quite a few alternatives:

1) return the GCD that is non-negative (my preference)

2) return the GCD that is negative (your suggestion)

3) return the GCD that has the same sign as its first input

4) return the GCD that has the same sign as its second input (as now)

and, I suspect, a few more I haven't thought of.

I may be wrong here, but I suspect that if we were starting from scratch
the first of these would quickly be adopted for several reasons:

1) it yields the least surprising results and the one that most users
probably both want and expect.

2) For me, Wolfgang Maier's point about the commutative properties of
the gcd is rather important since finding that gcd(a, b) != gcd(b, a) is
a real loss, not just an inconvenience.

3) Its 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 should eiher do nothing or we should introduce
a gcd in, say math, that adopts approach (1) above and document its
difference when compared with that in fractions, allowing both to
co-exist.

We can, hopefully speed it up (see the related threads) and it might
over time come to be the gcd that people come to use as the norm (also
nothing would stop its internal use in fractions).

We might also allow one or more inputs.

Last but not least I hope I have not done anyone a disservice in this
summary.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 module, for example) should 
 definitely return the unique nonnegative gcd of its inputs.
 
 In an effort to concentrate the discussion a bit, here's a specific
 proposal, deliberately limited in scope:
 
 1. Add a new (faster) math.gcd function for Python 3.5, taking two integral 
 arguments, and returning the unique nonnegative greatest common divisor of 
 those arguments.
 
 2. Deprecate fractions.gcd in Python 3.5 (with a message suggesting that 
 math.gcd should be used instead), but don't change its behaviour.  (The 
 fractions module would likely be using math.gcd by this point.)
 
 3. Remove fractions.gcd in Python 3.6.
 
 I'd suggest that tangents about gcd of more than two arguments, gcd of 
 rational / Decimal / float inputs, etc. be discussed elsewhere.  Those are 
 all things that can be added later if there's a real use-case.

My summary crossed with this plan from Mark, which I support (minus the
bit he subsequently retracted).

+1

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Terry J. Reedy]

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 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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Stefan Behnel]

Stefan Behnel added the comment:

+1 for Mark  Terry, just for the record

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Akira Li]

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
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Matthew Barnett]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 module, for example) should 
 definitely return the unique nonnegative gcd of its inputs.
 
 In an effort to concentrate the discussion a bit, here's a specific
 proposal, deliberately limited in scope:
 
 1. Add a new (faster) math.gcd function for Python 3.5, taking two integral 
 arguments, and returning the unique nonnegative greatest common divisor of 
 those arguments.
 
 2. Deprecate fractions.gcd in Python 3.5 (with a message suggesting that 
 math.gcd should be used instead), but don't change its behaviour.  (The 
 fractions module would likely be using math.gcd by this point.)
 
 3. Remove fractions.gcd in Python 3.6.
 
 I'd suggest that tangents about gcd of more than two arguments, gcd of 
 rational / Decimal / float inputs, etc. be discussed elsewhere.  Those are 
 all things that can be added later if there's a real use-case.

I don't know much about performance issues in the Python interpreter but
one point I would make here is implementing a multiple integer gcd on
top of a two input one will involve calling gcd and abs for each
parameter.

In contrast a gcd that operates on one or more parameters (e.g of the
sort that I posted earlier under the name mgcd) can avoid these extra
calls and any consequent overheads and _might_ do so with little
additional overhead of its own making (i.e. loops vs calls).  I also
felt that this could be implemented on top of the work going on on the
faster gcd.

So, while I don't think we need to consider a rational gcd, it might be
worth at least considering how a 'one or more parameter' gcd compares on
performance grounds with a two parameter one.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Brian Gladman]

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 Rosen). In particular gcd(a, 
b) = gcd(|a|, |b|).  

But the Python version of this function in the fractions module doesn't conform 
to these properties since it returns a negative value when its second parameter 
is negative.  

This behaviour is documented but I think it is undesirable to provide a 
function that has the well known and widely understood name 'gcd', but one that 
doesn't match the behaviour normally associated with this function.

I hence believe that consideration should be given to changing the behaviour of 
the Python greatest common divisor function to match 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: behavior
versions: Python 3.4

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[STINNER Victor]

STINNER Victor added the comment:

See also issue #22464.

--
nosy: +haypo

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

Mark Dickinson added the comment:

+1 from me.

--
nosy: +mark.dickinson

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

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 the result to be always nonnegative is probably 
a little less surprising than the current behaviour.

BTW, I don't think there's a universally agreed definition for the extension of 
the gcd to negative numbers (and I certainly wouldn't take Rosen's book as 
authoritative: did you notice the bit where he talks about 35-bit machines 
being common?), so I don't regard the fraction module definition as wrong, per 
se.  But I do agree that the behaviour you propose would be less surprising.

One other thought: if we're really intending for gcd to be used independently 
of the fractions module, perhaps it should be exposed as math.gcd.  (That would 
also give the opportunity for an optimised C version.)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 standalone implementation of gcd, independent of the 
 fractions module, then defining the result to be always nonnegative is 
 probably a little less surprising than the current behaviour.
 
 BTW, I don't think there's a universally agreed definition for the extension 
 of the gcd to negative numbers (and I certainly wouldn't take Rosen's book as 
 authoritative: did you notice the bit where he talks about 35-bit machines 
 being common?), so I don't regard the fraction module definition as wrong, 
 per se.  But I do agree that the behaviour you propose would be less 
 surprising.

I only quoted Rosen because I had it immediately to hand.  I will
willingly supply more references if you need them.  Sadly even some
maths books don't cover this at all but then go on to rely on the
co-prime test gcd(a, b) == 1 even when a and/or b can be negative.
So I would agree that it is easy to conclude that the gcd is not defined
for negative numbers.  But, of those maths texts that explicitly cover
the behaviour of the gcd for negative numbers, I do not know of any that
do not define gcd(a, b) to be gcd(|a|, |b|).

 One other thought: if we're really intending for gcd to be used independently 
 of the fractions module, perhaps it should be exposed as math.gcd.  (That 
 would also give the opportunity for an optimised C version.)

To me it makes more sense to put this in math as this is where I would
expect to find it.  But a comment on comp.lang.python was not in favour
of this.

--
nosy: +gladman

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

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 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-with-a-1 R:  c is a greatest common divisor of a and b if c is 
a common divisor (i.e. c divides a and c divides b, where x divides y is 
synonymous with y is a multiple of x), and any other common divisor divides 
c.  No ordering is necessary: greatest here is with respect to the 
divisibility lattice rather than with respect to any kind of total ordering.  
One advantage of this definition is that it makes it clear that 0 is a greatest 
common divisor of 0 and 0.

If further R is an integral domain, then it follows immediately from the 
definition that any two greatest common divisors of a and b (if they exist) are 
associates: a is a unit times b.  In the particular case where R is the usual 
ring of rational integers, that means that the greatest common divisor of two 
numbers a and b is only really defined up to +/-;  that is, the sign of the 
result is unimportant.  (An alternative viewpoint is to think of the gcd, when 
it exists, as a principal ideal rather than an element of the ring.)

See 
https://proofwiki.org/wiki/Definition:Greatest_Common_Divisor/Integral_Domain 
for more along these lines.

So you're using one definition, I'm using another.  Like I said, there's no 
universal agreement. ;-).

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 Rosen's) 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 on this :-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

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 3.4 bugfix release.)

--
type: behavior - enhancement
versions: +Python 3.5 -Python 3.4

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 arguments about the definition, I don't 
 think this is a change that could be applied in a 3.4 bugfix release.)

Yes, I am very willing to contribute. But I have never contributed to
Python before and I almost certainly have a lot to learn in any attempt
to do this.

In particular, I need advice on where any 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 it (if there is a consensus to do so).

Of course, there is the very simple change of adding abs(x) to the
return value for the current gcd and adjusting its single use in
fractions accordingly.  But since there is already concern about the
impact of the gcd on the performance of fractions, it deserves more
careful consideration than this approach would involve.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Stefan Behnel]

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 Fraction type and b) positive input values.

Even if there's no other module namespace for this functionality that is more 
suitable than fractions, it could still be added under a different name, say, 
absgcd() or whatever. Something that makes it clear(er) how negative input is 
handled. The mere name gcd isn't very telling on that front.

--
nosy: +scoder

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Akira Li]

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

  def gcd(a, b):
  while b:
  a, b = b, a%b
  return a

can be applied to Euclidean ring elements (not just positive or
negative integers). Despite Knuth’s objection to gcd(1, -1) = -1, 
adding `if a  0: a = -a` at the end changes the requirements for the
type. Here's the definition from the lecture [1]:

  Greatest common divisor is a common divisor that is divisible by any 
  other common divisor.

I have no opinion on whether or not fractions.gcd() should be changed. 
I thought that I should mention that different definitions exist.

--
nosy: +akira

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Steven D'Aprano]

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. See my comments here:

https://mail.python.org/pipermail/python-list/2014-September/678681.html
 
Given that there is no one definitive definition of gcd, this is not a bug fix, 
it is a backward-incompatible functional change. That means it ought to go 
through a deprecation period before changing it:

- deprecate negative arguments in 3.5;
- raise a warning in 3.6;
- change the behaviour in 3.7.

*Maybe* we could skip the silent deprecation period and jump straight to the 
warning. But I don't see any justification for fast-tracking this, and 
certainly not for jumping straight to the change of behaviour. Somebody is 
using this function and expects it to do what it currently does, and changing 
it will break their code for precious little benefit.

Another objection: this suggested change will add yet another backwards 
incompatibility between Python 2.7 and 3.x. There ought to be a good reason for 
that, not just to save a single call to abs() after gcd.

I am -1 on making this change.

--
nosy: +steven.daprano

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Steven D'Aprano]

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. 
Should we do the same?

Would it be too confusing to have fractions.gcd and fractions.Fraction.gcd both 
exist but behave differently? I fear so.

I wish we had a mathlib.py standard module for pure Python implementations...

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Wolfgang Maier]

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


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 also about the fact that in the current 
implementation the result of gcd is dependent on the order of the arguments:

 gcd(-3,6) == gcd(6,-3)
False

which I think is clearly unexpected.


@Steven:
I share your fear of generating backwards incompatibility only partially. Of 
course, there may be code out there that is relying on the current documented 
behavior for negative integer input, but probably not in too many places since 
after all it's a pretty special need and it's easy enough to implement that 
most people will not even come across the stdlib function before writing their 
own. Even if your code's affected it is really easily fixed.

I do admit though that the proposed change of behavior *could* cause 
hard-to-track bugs in pieces of code that *do* use fractions.gcd right now. So 
I do favor your scheme of raising a warning with negative numbers in Python 
3.5, then changing the behavior in 3.6.

@Steven again:
I was playing around with the idea of having a gcd that accepts more than two 
arguments (and the same for a potential lcm function), then realized that its 
easily written right now as:

reduce(gcd, (3,6,9))
3

Ironically, though, the proposed new gcd would make this slower than it has to 
be since it would do the abs() repeatedly, when

abs(reduce(_gcd, (3,6,9))) would suffice.

So, I guess that's the tradeoff coming with the proposed change:

- a more concise implementation of gcd

against

- broken backwards compatibility and
- reduced flexibility by calling abs implicitly instead of just when the user 
needs it

I guess with that I am 
+0.5 for the change though maybe an extra sentence in the docs about the 
consequences of the already documented behavior of gcd and that you really 
*should* call abs() on the result in most situations may be enough.

--
nosy: +wolma

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Terry J. Reedy]

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 its negative.  Ditto for the docstring.

--
nosy: +terry.reedy

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Terry J. Reedy]

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
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[Mark Dickinson]

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 to the divisibility lattice, not the total ordering of Z.  That's in 
some sense the correct interpretation, because it's the one that generalises to 
other interesting rings: for example, the Gaussian integers have a well-defined 
and useful notion of greatest common divisor, but aren't ordered, and the ring 
Z[sqrt 3] similarly has well-defined greatest common divisors (defined up to 
multiplication by a unit, as usual) *and* a total ordering, but greatest 
*can't* be interpreted in the ordering sense in that case (because there are 
infinitely many units).

Many textbooks will talk about a greatest common divisor rather than the 
greatest common divisor.  In that sense, -3 *is* a greatest common divisor of 
6 and -15.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 another greatest common divisor, if you interpret greatest as being 
 with respect to the divisibility lattice, not the total ordering of Z.  
 That's in some sense the correct interpretation, because it's the one that 
 generalises to other interesting rings: for example, the Gaussian integers 
 have a well-defined and useful notion of greatest common divisor, but aren't 
 ordered, and the ring Z[sqrt 3] similarly has well-defined greatest common 
 divisors (defined up to multiplication by a unit, as usual) *and* a total 
 ordering, but greatest *can't* be interpreted in the ordering sense in that 
 case (because there are infinitely many units).
 
 Many textbooks will talk about a greatest common divisor rather than the 
 greatest common divisor.  In that sense, -3 *is* a greatest common divisor 
 of 6 and -15.

Then the Python documentation should say 'a greatest ...', not 'the
greatest ...' since those who deny that the integer gcd is non-negative
can hardly deny that a positive alternative value exists :-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22477] GCD in Fractions

[gladman]

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 also about the fact that in the current 
 implementation the result of gcd is dependent on the order of the arguments:
 
 gcd(-3,6) == gcd(6,-3)
 False
 
 which I think is clearly unexpected.

Yes, that's another interesting surprise.

 Ironically, though, the proposed new gcd would make this slower than it has 
 to be since it would do the abs() repeatedly, when
 
 abs(reduce(_gcd, (3,6,9))) would suffice.
 
 So, I guess that's the tradeoff coming with the proposed change:

I must admit to being more than a little hazy about what is fast and
what isn't in the Python interpreter but wouldn't the use of reduce to
repeatedly call _gcd be slower than an alternative that avoids this?

Taking on board one of Steven D'Aprano's thoughts about multiple inputs,
I had envisaged something like this:

def mgcd(a, *r):  # multiple gcd
  for b in r:
while b:
  a, b = b, a % b
  return abs(a)

which gives:

 mgcd(0)
0
 mgcd(7, 0)
7
 mgcd(0, 7)
7
 mgcd(-3, -7)
1
 mgcd(-3, 7)
1
 mgcd(7, -3)
1
mgcd(-21, -91, 707)
7

So it has the properties that I believe it should have (yes, I know we
don't agree on this). I am not sure I would extend it to rationals,
although I don't feel strongly about this.

This could be introduced elsewhere without changing what is done in
fractions.  Having two 'gcd's that return different results in some
circumstances might be a source of confusion for some - but not more
than already exists about what values the gcd should return :-)

PS I just know that I am going to regret posting code 'on the hoof' -
it's almost certain to be wrong :-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue22477
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com