[issue22486] Add math.gcd()

STINNER Victor added the comment: New changeset 4691a2f2a2b8174a6c958ce6976ed5f3354c9504 by Victor Stinner in branch 'master': bpo-39350: Remove deprecated fractions.gcd() (GH-18021) https://github.com/python/cpython/commit/4691a2f2a2b8174a6c958ce6976ed5f3354c9504 --

[issue22486] Add math.gcd()

Change by STINNER Victor : -- pull_requests: +17417 pull_request: https://github.com/python/cpython/pull/18021 ___ Python tracker ___

[issue22486] Add math.gcd()

Changes by Berker Peksag berker.pek...@gmail.com: -- stage: patch review - resolved ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___ ___

[issue22486] Add math.gcd()

Roundup Robot added the comment: New changeset 34648ce02bd4 by Serhiy Storchaka in branch 'default': Issue #22486: Added the math.gcd() function. The fractions.gcd() function now is https://hg.python.org/cpython/rev/34648ce02bd4 -- nosy: +python-dev

[issue22486] Add math.gcd()

Changes by Benjamin Peterson benja...@python.org: -- resolution: - fixed status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___

[issue22486] Add math.gcd()

Stefan Behnel added the comment: 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

[issue22486] Add math.gcd()

STINNER Victor added the comment: What's the status of this issue? See also the issue #22477. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: 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.

[issue22486] Add math.gcd()

Changes by Serhiy Storchaka storch...@gmail.com: Added file: http://bugs.python.org/file37422/lehmer_gcd_8.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___

[issue22486] Add math.gcd()

Stefan Behnel added the comment: Any objections to merging the last patch? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___ ___

[issue22486] Add math.gcd()

Mark Dickinson added the comment: Any objections to merging the last patch? Yes! Please don't make these changes to `Fractions.gcd`: they'll cause regressions for existing uses of `Fractions.gcd` with objects not of type `int`. -- ___ Python

[issue22486] Add math.gcd()

Stefan Behnel added the comment: 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. -- ___ Python tracker rep...@bugs.python.org

[issue22486] Add math.gcd()

Mark Dickinson added the comment: 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?) -- ___ Python tracker

[issue22486] Add math.gcd()

STINNER Victor added the comment: 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

[issue22486] Add math.gcd()

Mark Dickinson added the comment: 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

[issue22486] Add math.gcd()

Stefan Behnel added the comment: +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. -- ___ Python tracker rep...@bugs.python.org

[issue22486] Add math.gcd()

Mark Dickinson added the comment: One other suggestion: I think math.gcd should work with arbitrary Python objects implementing __index__, and not just with instances of int. -- ___ Python tracker rep...@bugs.python.org

[issue22486] Add math.gcd()

Mark Dickinson added the comment: 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

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: 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

[issue22486] Add math.gcd()

Changes by Alexander Belopolsky alexander.belopol...@gmail.com: -- nosy: +belopolsky ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___ ___

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: Here is fixed patch. There was integer overflow. In C short*short is extended to int, but int*int results int. -- Added file: http://bugs.python.org/file36741/lehmer_gcd_7.patch ___ Python tracker

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: And for comparison here is simpler patch with Euclidean algorithm. -- Added file: http://bugs.python.org/file36742/euclidean_gcd.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486

[issue22486] Add math.gcd()

Stefan Behnel added the comment: Patch 7 works for me. Why are the two Py_ABS() calls at the end needed when we start off the algorithm with long_abs()? The Lehmer code is complex (I guess that's why you added the pure Euclidean implementation), but it's the right algorithm to use here, so

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: Why are the two Py_ABS() calls at the end needed when we start off the algorithm with long_abs()? Because long_abs()'s are omitted for small enough numbers (common case). So we avoid a copying for negative numbers or int subclasses. I guess that's why

[issue22486] Add math.gcd()

Stefan Behnel added the comment: My personal take is: if there is an implementation in the stdlib, it should be the one that's most widely applicable. And that includes large numbers. We have a working implementation that is algorithmically faster for large numbers, so I can't see why we

[issue22486] Add math.gcd()

Stefan Behnel added the comment: Thanks, Serhiy. However, something is wrong with the implementation. The benchmark runs into an infinite loop (it seems). And so do the previous patches. Does it work for you? -- ___ Python tracker

[issue22486] Add math.gcd()

Stefan Behnel added the comment: I compiled it with 30 bit digits, in case that's relevant. (It might be.) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: It works to me (compiled with 15-bit digits). Cold you please add debugging prints (before and after the call of math.gcd()) and find which operation is looping (math.gcd() itself, and for what arguments, or some Python code)? --

[issue22486] Add math.gcd()

Stefan Behnel added the comment: This is what hangs for me: math.gcd(1216342683557601535506311712, 436522681849110124616458784) a and b keep switching between both values, but otherwise, the loop just keeps running. The old fractions.gcd() gives 32 for them. --

[issue22486] Add math.gcd()

Stefan Behnel added the comment: I can confirm that it works with 15 bit digits. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___ ___

[issue22486] Add math.gcd()

Mark Dickinson added the comment: To avoid regressions, please can we leave the old `fractions.gcd` exactly as it was? For example, the current `fractions.gcd` *does* work for Fraction instances [1]. That's certainly not its intended use, but I wouldn't be surprised if there's code out

[issue22486] Add math.gcd()

Mark Dickinson added the comment: This is what hangs for me: Uh-oh. Sounds like I screwed up somewhere. I'll take a look this weekend, unless Serhiy beats me too it. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486

[issue22486] Add math.gcd()

Mark Dickinson added the comment: too it. Bah. to it. Stupid fingers. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___ ___

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: Thank you Stefan. I confirm that it hangs with 30-bit digits. One existing bug is in the use of PyLong_AsLong() before simple Euclidean loop. It should be PyLong_AsLongLong() if the long is not enough for two digits. But there is another bug in inner

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: Here is updated Mark's patch from issue1682. 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

[issue22486] Add math.gcd()

Changes by Serhiy Storchaka storch...@gmail.com: -- keywords: +patch Added file: http://bugs.python.org/file36722/lehmer_gcd_4.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___

[issue22486] Add math.gcd()

Stefan Behnel added the comment: 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. -- components:

[issue22486] Add math.gcd()

Stefan Behnel added the comment: Oh, and thanks for working on it, Serhiy! :) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___ ___

[issue22486] Add math.gcd()

Wolfgang Maier added the comment: see issue22477 for a discussion of whether the behavior of fractions.gcd should be changed or not -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486

[issue22486] Add math.gcd()

Wolfgang Maier added the comment: sorry, forgot to format the link: issue22477 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___ ___

[issue22486] Add math.gcd()

Stefan Behnel added the comment: The thing is, if we add something new in a substantially more exposed place (the math module), then why break legacy code *in addition*? Just leaving it the way it is won't harm anyone, really. -- ___ Python tracker

[issue22486] Add math.gcd()

Wolfgang Maier added the comment: I wasn't arguing for or against anything, just providing a link to the relevant discussion. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue22486 ___

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: Well, here is a patch which keeps the same weird behavior of fractions.gcd(). -- Added file: http://bugs.python.org/file36723/lehmer_gcd_5.patch ___ Python tracker rep...@bugs.python.org

[issue22486] Add math.gcd()

gladman added the comment: I am inclined to think that a maths.gcd() makes sense as this would be where I would go first to find this function. And the prospect of better performance is attractive since the gcd is an important operation in work with number theory algorithms. Would it

[issue22486] Add math.gcd()

Mark Dickinson added the comment: Or would it co-exist with fractions.gcd(), with the 'less surprising' semantics that are under discussion in the 'GCD in Fractions' thread? Yes, exactly. math.gcd will always give a nonnegative result. The output of fractions.gcd remains unchanged for

[issue22486] Add math.gcd()

Mark Dickinson added the comment: Serhiy: thank you! I've been meaning to update that patch for a long time, but hadn't found the courage or time to face the inevitable bitrot. -- ___ Python tracker rep...@bugs.python.org

[issue22486] Add math.gcd()

Serhiy Storchaka added the comment: Now I spent more time on the patch. Changes in updated patch: * Removed code duplication for odd and even k. * Temporary buffers c and d no longer allocated on every iteration. * Long result now compacted. No longer unused allocated size. * Added checks for