[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

Re: GCD in Fractions

[Akira Li]

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

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Chris Angelico]

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.

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

[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

Re: GCD in Fractions

[Mark Lawrence]

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

--
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Mark Dickinson]

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


 




-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Steven D'Aprano]

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.

GCD is well-defined for **positive integers only**.

Mathworld emphasises positive integers in their definition, repeating the
phrase THREE times in the first paragraph:

The greatest common divisor, sometimes also called the highest 
common divisor (Hardy and Wright 1979, p. 20), of two positive 
integers a and b is the largest divisor common to a and b. For 
example, GCD(3,5)=1, GCD(12,60)=12, and GCD(12,90)=6. The 
greatest common divisor GCD(a,b,c,...) can also be defined for 
three or more positive integers as the largest divisor shared 
by all of them. Two or more positive integers that have greatest
common divisor 1 are said to be relatively prime to one another,
often simply just referred to as being relatively prime. 

http://mathworld.wolfram.com/GreatestCommonDivisor.html

The rest of the page avoids mentioning anything about negative values. There
are five graphs on the page, all five are limited to only positive values.

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.

http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/


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.

Here's an example using Euclid's algorithm to calculate the GCD of negative
numbers, and sure enough, you get a negative result:

https://answers.yahoo.com/question/index?qid=20111021023909AA8bCjB

Wikipedia, on the other hand, defines GCD:

In mathematics, the greatest common divisor (gcd), also 
known as the greatest common factor (gcf), highest common 
factor (hcf), or greatest common measure (gcm), of two or 
more integers (when at least one of them is not zero), is 
the largest positive integer that divides the numbers 
without a remainder.

https://en.wikipedia.org/wiki/Greatest_common_divisor


So:

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

- Euclid's algorithm returns negative values for the GCD of two negatives;

- Collins Dictionary gives a definition which is met by either positive
  or negative results.




-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

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 looking at these (and several other) on-line mathematical sites, I
realised that I would have to go back to long standing mathemmatical
references to find how the gcd is defined by those that explicitly cover
the greatest common divisor for negative integers (I did this before
raising the issue here).

All four that I have so far looked at have definitions that lead to
gcd(a, b) for integers being equal to gcd(|a|, |b|). I hope to visit a
University library shortly to review more.  Does anyone know of such a
reference that uses a definition that conflicts with gcd(a, b) for
integers being equal to gcd(|a|, |b|)?

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Ian Kelly]

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

Well, this definition would imply that gcd(a, b) should always return
*two* results, one positive and one negative. I don't think anybody
wants that. It would make more sense to standardize on one of them,
and if we take sqrt as an example, then the result should be positive.

 Here's an example using Euclid's algorithm to calculate the GCD of negative
 numbers, and sure enough, you get a negative result:

 https://answers.yahoo.com/question/index?qid=20111021023909AA8bCjB

This depends entirely on your implementation of the modulo operation,
which is an issue of computing since the operator is not used in
mathematics.  The algorithm itself only specifies at each step to
solve the equation R_{n-2} = Q * R_{n-1} + R_{n}, such that |R_{n}| 
|R_{n-1}|. For any given input there can be many possible solutions,
both positive and negative, regardless of the signs of the inputs, and
it doesn't matter which solution you choose. So one could implement
Euclid's algorithm to return either a positive or negative result for
any arbitrary pair of integers.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Stefan Behnel]

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 Mathematica and disagrees with Mathworld;
 
 After looking at these (and several other) on-line mathematical sites, I
 realised that I would have to go back to long standing mathemmatical
 references to find how the gcd is defined by those that explicitly cover
 the greatest common divisor for negative integers (I did this before
 raising the issue here).
 
 All four that I have so far looked at have definitions that lead to
 gcd(a, b) for integers being equal to gcd(|a|, |b|). I hope to visit a
 University library shortly to review more.  Does anyone know of such a
 reference that uses a definition that conflicts with gcd(a, b) for
 integers being equal to gcd(|a|, |b|)?

Steven has already given sources that suggest that the result of gcd()
should be positive. Just like he gave sources that suggest the opposite.
So, the question is not how or where to find even more sources, or to
decide which of those sources is more right than the others, the question
is whether such a shaky ground is a reasonable foundation for breaking
other people's code.

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 want it (as in need it for their code, not just want it
for purity reasons or sleep better when they know it's out there), but
please, everyone, stop complaining about fractions.gcd not catering for
your needs. It does what it's there for, even if the name is more public or
more generic than you might want. There are other ways to fix the actual
problem and move on.

Stefan


-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Mark Lawrence]

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

--
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[random832]

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, the remainder is always positive. (whereas
either C or Python allows the modulo to be negative, in different
situations: in python [round quotient down] the modulo has the same sign
as b, whereas in C [round quotient to zero] the modulo has the same sign
as a).

def mod(a, b):
   r = a % b
   return r + abs(b) if r  0 else r

def gcd(a, b):
if b == 0: return a
else: return gcd(b, mod(a, b))

This appears to give a negative result when:
  a  0 and b == 0, obviously. A is returned as the gcd.
  a == 0 and b  0. B is returned as the gcd
  |a| is exactly divisible by |b| and b  0. B is returned as the gcd.

However, it still lacks the symmetry of gcd(a, b) == gcd(b, a) in some
cases. For example, gcd(-2, 6) is 2, whereas gcd(6, -2) is -2.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

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 want it (as in need it for their code, not just want it
 for purity reasons or sleep better when they know it's out there), but
 please, everyone, stop complaining about fractions.gcd not catering for
 your needs. It does what it's there for, even if the name is more public or
 more generic than you might want. There are other ways to fix the actual
 problem and move on.

This has never been about my need to use fractions.gcd since I don't
even use it (I have my own implementation).

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

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

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Terry Reedy]

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

--
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Johann Hibschman]

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

Re: GCD in Fractions

[Robert E. Beaudoin]

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 and disagrees with Mathworld;


After looking at these (and several other) on-line mathematical sites, I
realised that I would have to go back to long standing mathemmatical
references to find how the gcd is defined by those that explicitly cover
the greatest common divisor for negative integers (I did this before
raising the issue here).

All four that I have so far looked at have definitions that lead to
gcd(a, b) for integers being equal to gcd(|a|, |b|). I hope to visit a
University library shortly to review more.  Does anyone know of such a
reference that uses a definition that conflicts with gcd(a, b) for
integers being equal to gcd(|a|, |b|)?



I doubt you'll find an advanced mathematical text that has such a 
definition.  I think most abstract algebra texts would give a definition 
equivalent to saying that for any integers n and m the ideal generated 
by n and m is equal to the principal ideal generated by gcd(n,m); that 
is the heart of the matter mathematically, and this definition 
generalizes to other so-called principal ideal domains than the integers.


(Don't want to Google for ideal and principal ideal?  OK:  an ideal 
is a subset of the integers closed under addition of any two of its 
elements, and under multiplication of any of its elements by any 
integer; a set of integers generates an ideal if that ideal is the 
intersection of all ideals containing that set, and a principal ideal is 
an ideal generated by a singleton set.  For more elaboration, though, 
I'm going to point you at the internet, or better, some of those 
advanced texts in the library.)


After working through what the definitions of ideals and principal 
ideals imply for the the definition above of gcd, you get the statement 
that k is the (or, better, a) gcd of n and m if and only if k divides n 
and m, and any other integer that divides both n and m divides k.  The 
upshot is that, mathematically, gcd is only defined up to a change of 
sign, which helps explain why references may disagree with each other. 
Some authors may impose the restriction than gcd(n,m) = 0 for all n and 
m (which does have the advantage that then greatest really means 
greatest and not just greatest absolute value), but that isn't really 
a necessary part of the definition as far as the mathematically 
important properties of gcd are concerned.  All that the abstract 
algebra requires is that


|gcd(n,m)| = |gcd(|n|,|m|)|.

So implementations of gcd that sometimes return a negative value are 
not, it seems to me, mathematically broken, though they might violate 
the principle of least surprise.


for-whatever-it's-worth'ly-yrs,

R. Beaudoin

--
https://mail.python.org/mailman/listinfo/python-list

[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

GCD in Fractions

[blindanagram]

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 than |x|, returning -|x| rather than
|x| is not returning the greatest common divisor of x and y when y is
negative.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Wolfgang Maier]

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 test that
would work in many other languages 'if gcd(x, y) == 1' will fail in
Python for negative y.



On the other hand, it allows:
 Fraction(3, -7)
Fraction(-3, 7)

and:
 Fraction(3, -7) == Fraction(-3, 7)
True

Given that the implementation is particularly useful for Fraction() it 
is debatable whether the function shouldn't be called _gcd instead of 
gcd, but otherwise it makes sense.



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.



however, you can always use abs on y before passing it to gcd.

Wolfgang

--
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

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 guaranteed once it is exposed as a function that is
available to all Python users.

 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.

[snip]
 Given that the implementation is particularly useful for Fraction() it
 is debatable whether the function shouldn't be called _gcd instead of
 gcd, but otherwise it makes sense.

As you imply, it would make sense if it hadn't been exposed for more
general use.

However, I am less sure that it is sensible to have a gcd function
exposed for end user use when it conflicts with the function's usual
definition.

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Steven D'Aprano]

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

http://mathworld.wolfram.com/GreatestCommonDivisor.html

although buried deep in the documentation for Mathematica's GCD function is
hidden the fact that it treats GCD(-a, -b) the same as GCD(a, b):

http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/

and sure enough Wolfram Alpha tells me that the GCD of *all* of:

(100, 20)
(-100, 20)
(100, -20)
(-100, -20)

are equal to +20. On the other hand, Excel and LibreOffice both give an
error for the GCD of a negative value, and I've seen versions of gcd()
which do the same as fractions.gcd. So I think there is not one single
standard way to extend GCD to negative numbers.

 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.

True, but either of:

abs(gcd(x, y)) == 1
gcd(x, y) in (1, -1)

will work.


 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.

That's a good argument for gcd if it were in a general maths module, but
since it is specifically used for generating fractions, I guess that the
developers won't be very convinced by that.




-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

On 23/09/2014 13:50, Steven D'Aprano wrote:
 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):
 
 http://mathworld.wolfram.com/GreatestCommonDivisor.html
 
 although buried deep in the documentation for Mathematica's GCD function is
 hidden the fact that it treats GCD(-a, -b) the same as GCD(a, b):
 
 http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/
 
 and sure enough Wolfram Alpha tells me that the GCD of *all* of:
 
 (100, 20)
 (-100, 20)
 (100, -20)
 (-100, -20)
 
 are equal to +20. On the other hand, Excel and LibreOffice both give an
 error for the GCD of a negative value, and I've seen versions of gcd()
 which do the same as fractions.gcd. So I think there is not one single
 standard way to extend GCD to negative numbers.
 
 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.
 
 True, but either of:
 
 abs(gcd(x, y)) == 1
 gcd(x, y) in (1, -1)
 
 will work.
 
 
 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.
 
 That's a good argument for gcd if it were in a general maths module, but
 since 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

[Chris Angelico]

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

Re: GCD in Fractions

[Wolfgang Maier]

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 documentation for Mathematica's GCD function is
hidden the fact that it treats GCD(-a, -b) the same as GCD(a, b):

http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/

and sure enough Wolfram Alpha tells me that the GCD of *all* of:

(100, 20)
(-100, 20)
(100, -20)
(-100, -20)

are equal to +20. On the other hand, Excel and LibreOffice both give an
error for the GCD of a negative value, and I've seen versions of gcd()
which do the same as fractions.gcd. So I think there is not one single
standard way to extend GCD to negative numbers.



Well, Excel and LibreOffice can hardly be considered the gold standard 
when it comes to mathematical definitions.
I'm no mathematician either, but Wikipedia has this to say about the 
properties of gcd:

http://en.wikipedia.org/wiki/Greatest_common_divisor#Properties

fractions.gcd violates several of them, like:

#2:
gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the 
greatest divisor of a is |a|.


fractions.gcd(-7, 0)
-7

#8:
The gcd is a commutative function: gcd(a, b) = gcd(b, a).

fractions.gcd(3, -7) == fractions.gcd(-7, 3)
False

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


Maybe fractions.gcd could be renamed, but be wrapped or reimplemented 
correctly somewhere else in the stdlib or even in fractions ?


Wolfgang


--
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Ian Kelly]

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 right
place, as that module houses wrappers of C functions that operate on
floats. I'm also not sure where is better, though. Maybe the
reimplemented version should just keep the name fractions.gcd.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Stefan Behnel]

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


 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.

Stefan


-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

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 math module as suggested upthread is the right
 place, as that module houses wrappers of C functions that operate on
 floats. I'm also not sure where is better, though. Maybe the
 reimplemented version should just keep the name fractions.gcd.

Since the gcd is only used once in fractions anyway, it would be easy to
change gcd here with very little impact on the performance of the
fractions module (if necessary a local version could be added to work
within fractions as it does now).

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Ian Kelly]

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

Re: GCD in Fractions

[blindanagram]

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.



-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Ian Kelly]

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

I forgot to include the link:

https://proofwiki.org/wiki/GCD_for_Negative_Integers
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Stefan Behnel]

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

May I ask how you get from one little function in the well-defined scope of
a data type module (which is not named math or integers or natural or
anything like it) to the extrapolation that Python doesn't take
mathematical properties serious?

If the scope of that function's applicability does not match what you want
in your specific use case, then by all means, don't use it for your
specific use case.

Stefan


-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Stefan Behnel]

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


-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Mark Lawrence]

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

--
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Terry Reedy]

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

--
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

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 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.
 
 May I ask how you get from one little function in the well-defined scope of
 a data type module (which is not named math or integers or natural or
 anything like it) to the extrapolation that Python doesn't take
 mathematical properties serious?

Firstly I have to choose between two possibilities:

(a) that the name of the function has been deliberately chosen to imply
that it calculates the mathematical function known as the 'greatest
commmon divisor'; or

(b) that the initials 'gcd' have been chosen by pure chance and the
association between this function and the 'greatest commmon divisor' has
arisen from pure coincidence.

Of these, I find (a) overwhelmingly more likely.

Seccondly (as others here have pointed out), the mathematical properties
of the greatest common divisor are well defined for both positive and
negative integers.  But the Python function called gcd doesn't have some
of these properties.

I hence conclude that Python doesn't take the mathematical properties of
the greatest common divisor seriously since it doesn't ensure that its
version of this function has these properties.

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[blindanagram]

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.

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: GCD in Fractions

[Mark Lawrence]

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

--
https://mail.python.org/mailman/listinfo/python-list