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.