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.

See also issue #22464.

+1 from me.

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

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.

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

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

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

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.

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.

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.

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.

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

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.

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.

Or "Return a greatest magniture common divisor ...", there being two gmcds to choose from.

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

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

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

Also see issue 22486. There is an unmerged C implementation in the old issue 1682 that would go into the math module.

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.

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

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

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

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

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.

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.

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

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

+1 for Mark & Terry, just for the record

+1 for leaving it to the user to make it negative if so desired.

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.

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

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

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?

I see that the issue #22486 is still open.

Is there something to do with this issue?

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