Add math.gcd()

@mdickinson

BPO	22486
Nosy	@mdickinson, @abalkin, @pitrou, @scoder, @vstinner, @serhiy-storchaka, @wm75
PRs	bpo-39350: Remove deprecated fractions.gcd() #18021
Files	lehmer_gcd_4.patch lehmer_gcd_5.patch lehmer_gcd_6.patch lehmer_gcd_7.patch euclidean_gcd.patch lehmer_gcd_8.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2015-05-12.23:26:09.896>
created_at = <Date 2014-09-24.20:40:35.148>
labels = ['library', 'performance']
title = 'Add math.gcd()'
updated_at = <Date 2020-01-16.10:02:58.267>
user = 'https://github.com/scoder'

bugs.python.org fields:

activity = <Date 2020-01-16.10:02:58.267>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2015-05-12.23:26:09.896>
closer = 'benjamin.peterson'
components = ['Library (Lib)']
creation = <Date 2014-09-24.20:40:35.148>
creator = 'scoder'
dependencies = []
files = ['36722', '36723', '36726', '36741', '36742', '37422']
hgrepos = []
issue_num = 22486
keywords = ['patch']
message_count = 48.0
messages = ['227487', '227507', '227522', '227524', '227525', '227527', '227528', '227529', '227531', '227532', '227533', '227534', '227535', '227536', '227537', '227538', '227554', '227555', '227570', '227619', '227620', '227623', '227629', '227630', '227637', '227638', '227640', '227641', '227663', '227664', '227670', '227672', '227711', '228544', '228545', '228546', '228547', '228548', '228549', '228550', '228551', '228552', '228556', '232521', '232523', '242048', '243015', '360112']
nosy_count = 9.0
nosy_names = ['mark.dickinson', 'belopolsky', 'pitrou', 'scoder', 'vstinner', 'python-dev', 'serhiy.storchaka', 'wolma', 'gladman']
pr_nums = ['18021']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue22486'
versions = ['Python 3.5']

fractions.gcd() is required for normalising numerator and denominator of the Fraction data type. Some speed improvements were applied to Fraction in bpo-22464, now the gcd() function takes up about half of the instantiation time in the benchmark in bpo-22458, which makes it quite a heavy part of the overall Fraction computation time.

The current implementation is

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

Reimplementing it in C would provide for much faster calculations. Here is a Cython version that simply drops the calculation loop into C as soon as the numbers are small enough to fit into a C long long int:

def _gcd(a, b):
    # Try doing all computation in C space.  If the numbers are too large
    # at the beginning, retry until they are small enough.
    cdef long long ai, bi
    while b:
        try:
            ai, bi = a, b
        except OverflowError:
            pass
        else:
            # switch to C loop
            while bi:
                ai, bi = bi, ai%bi
            return ai
        a, b = b, a%b
    return a

It's substantially faster already because the values will either be small enough right from the start or quickly become so after a few iterations with Python objects.

Further improvements should be possible with a dedicated PyLong implementation based on Lehmer's GCD algorithm:

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

In case it's useful, see issue bpo-1682 for my earlier Lehmer gcd implementation. At the time, that approach was dropped as being premature optimisation.

If Python grows an optimized implementation, how about exposing it in the math module?

If Python grows an optimized implementation, how about exposing it in the math module?

+1.

That's what the patch does anyway. +1

Hmm... which patch?

http://bugs.python.org/file9486/lehmer_gcd.patch

(see bpo-1682)

Here is updated Mark's patch from bpo-1682. It is ported to 3.5, slightly simplified and optimized (I did not touched the main algorithm still), utilized in the fractions module, added tests and documentation.

It speeds up Stefan's fractions benchmark about 20%.

The problem is that this changes the behaviour of fractions.gcd() w.r.t. negative numbers. It's a public function, so we should keep it for backwards compatibility reasons, *especially* when adding a new function in the math module.

There are not such changes in patch 7. The fractions.gcd() function is unchanged but no longer used by the Fraction type, which now uses math.gcd() internally instead.

Ah, I misread; thanks.

What happens with this patch if a Fraction has been created with Integrals that aren't of type int? (E.g., with NumPy int32 instances, for example?)

Why patching fraction.Fraction constructor instead of fractions.gcd()?

I don't like the idea of having two functions, math.gcd and fractions.gcd, which do almost the same, but one is slow, whereas the other is fast. It's harder to write efficient code working on Python < 3.5 (use fractions) and Python >= 3.5 (use math or fractions?).

I suggest to modify fractions.gcd() to use math.gcd() if the two parameters are int. We just have to adjust the sign: if the second parameter is negative, return -math.gcd(a, b). (I guess that we have unit tests for fractions.gcd checking the 4 cases for signed parameters.)

I suggest to modify fractions.gcd() to use math.gcd() if the two parameters are int.

Sounds fine to me, so long as the code (both fractions.gcd and the fractions.Fraction implementation) continues to function as before for objects that don't have exact type int.

+1

I mean, there is already such a type check in Fraction.__init__(), but I can see a case for also optimising fraction.gcd() for exact ints.

One other suggestion: I think math.gcd should work with arbitrary Python objects implementing __index__, and not just with instances of int.

I mean, there is already such a type check in Fraction.__init__()

That type-check doesn't protect us from non-int Integrals, though, as far as I can tell. It looks to me as though doing Fraction(numpy.int32(3), numpy.int32(2)) would fail with a TypeError after this patch. (It works in Python 3.4.)

I suggest just add deprecation warning in fractions.gcd(). Or at least add
notes which recommend math.gcd() in the docstring and the documentation of
fractions.gcd().

One other suggestion: I think math.gcd should work with arbitrary Python
objects implementing __index__, and not just with instances of int.

Agree.

What's the status of this issue? See also the issue bpo-22477.

Here is a patch which addresses both Mark's suggestions.

math.gcd() now work with arbitrary Python objects implementing __index__.
fractions.gcd() and Fraction's constructor now use math.gcd() if both arguments are int, but also support non-ints (e.g. Fractions or floats).
fractions.gcd() now is deprecated.

But before committing I want to experiment with simpler implementation and compare it with current complex implementation. If the difference will be not too large, we could use simpler implementation.

Any more comments on this? The deadlines for new features in Py3.5 are getting closer. It seems we're just discussing details here, but pretty much everyone wants this feature.

So, what are the things that still need to be done? Serhiy submitted working patches months ago.

New changeset 34648ce02bd4 by Serhiy Storchaka in branch 'default':
Issue bpo-22486: Added the math.gcd() function. The fractions.gcd() function now is
https://hg.python.org/cpython/rev/34648ce02bd4

New changeset 4691a2f by Victor Stinner in branch 'master':
bpo-39350: Remove deprecated fractions.gcd() (GH-18021)
4691a2f

Navigation Menu

Repository navigation

Add math.gcd() #66676

29 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Add math.gcd() #66676

Description

Activity

scoder commented on Sep 24, 2014

mdickinson commented on Sep 25, 2014

pitrou commented on Sep 25, 2014

mdickinson commented on Sep 25, 2014

scoder commented on Sep 25, 2014

pitrou commented on Sep 25, 2014

scoder commented on Sep 25, 2014

serhiy-storchaka commented on Sep 25, 2014

scoder commented on Sep 25, 2014

29 remaining items

scoder commented on Oct 5, 2014

mdickinson commented on Oct 5, 2014

vstinner commented on Oct 5, 2014

mdickinson commented on Oct 5, 2014

scoder commented on Oct 5, 2014

mdickinson commented on Oct 5, 2014

mdickinson commented on Oct 5, 2014

serhiy-storchaka commented on Oct 5, 2014

vstinner commented on Dec 12, 2014

serhiy-storchaka commented on Dec 12, 2014

scoder commented on Apr 26, 2015

python-dev commented on May 12, 2015

vstinner commented on Jan 16, 2020

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions