[issue22486] Add math.gcd()

[STINNER Victor]

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


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[STINNER Victor]

Change by STINNER Victor :


--
pull_requests: +17417
pull_request: https://github.com/python/cpython/pull/18021

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Berker Peksag]

Changes by Berker Peksag :


--
stage: patch review -> resolved

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Benjamin Peterson]

Changes by Benjamin Peterson :


--
resolution:  -> fixed
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Roundup Robot]

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

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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 
patches months ago.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


Added file: http://bugs.python.org/file37422/lehmer_gcd_8.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[STINNER Victor]

STINNER Victor added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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 implementing __index__, and not just with instances of int.

Agree.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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 after this patch.  (It works in 
Python 3.4.)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[STINNER Victor]

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

--
nosy: +haypo

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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 tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

Stefan Behnel added the comment:

Any objections to merging the last patch?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Alexander Belopolsky]

Changes by Alexander Belopolsky :


--
nosy: +belopolsky

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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 should drop it unused.

I'm for merging patch 7.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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 you added the pure Euclidean implementation

Euclidean algorithm is required step at the end of Lehmer algorithm.

> It's 4% faster than the Euclidean code for the fractions benchmark
> when using 30 bit digits, but (surprisingly enough) about the same speed
> with 15 bit digits.

May be because Lehmer code uses 64-bit computation for 30-bit digits, and 
Euclidean code always uses 32-bit computation.

> The difference for big numbers is substantial though:

1000-bit integers are big, but can be encountered in real word (e.g. in 
cryptography). So may be there is need in Lehmer algorithm.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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 I'd say we 
should. It's 4% faster than the Euclidean code for the fractions benchmark when 
using 30 bit digits, but (surprisingly enough) about the same speed with 15 bit 
digits. There is no major difference to expect here as the numbers are 
perpetually normalised in Fractions and thus kept small (usually small enough 
to fit into a 64bit integer), i.e. Euclid should do quite well on them.

The difference for big numbers is substantial though:

Euclid:

$ ./python -m timeit -s 'from math import gcd; a = 2**123 + 3**653 + 5**23 + 
7**49; b = 2**653 + 2**123 + 5**23 + 11**34' 'gcd(a,b)'
1 loops, best of 3: 71 usec per loop

Lehmer:

$ ./python -m timeit -s 'from math import gcd; a = 2**123 + 3**653 + 5**23 + 
7**49; b = 2**653 + 2**123 + 5**23 + 11**34' 'gcd(a,b)'
10 loops, best of 3: 11.6 usec per loop

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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 

___diff -r e9d4288c32de Doc/library/math.rst
--- a/Doc/library/math.rst  Wed Sep 24 13:29:27 2014 +0300
+++ b/Doc/library/math.rst  Fri Sep 26 21:37:23 2014 +0300
@@ -100,6 +100,14 @@ Number-theoretic and representation func
`_\.
 
 
+.. function:: gcd(a, b)
+
+   Return the greatest common divisor of the integers *a* and *b*.  If either
+   *a* or *b* is nonzero, then the value of ``gcd(a, b)`` is the largest
+   positive integer that divides both *a* and *b*.  ``gcd(0, 0)`` returns
+   ``0``.
+
+
 .. function:: isfinite(x)
 
Return ``True`` if *x* is neither an infinity nor a NaN, and
diff -r e9d4288c32de Include/longobject.h
--- a/Include/longobject.h  Wed Sep 24 13:29:27 2014 +0300
+++ b/Include/longobject.h  Fri Sep 26 21:37:23 2014 +0300
@@ -198,6 +198,9 @@ PyAPI_FUNC(int) _PyLong_FormatAdvancedWr
 PyAPI_FUNC(unsigned long) PyOS_strtoul(const char *, char **, int);
 PyAPI_FUNC(long) PyOS_strtol(const char *, char **, int);
 
+/* For use by the gcd function in mathmodule.c */
+PyAPI_FUNC(PyObject *) _PyLong_GCD(PyObject *, PyObject *);
+
 #ifdef __cplusplus
 }
 #endif
diff -r e9d4288c32de Lib/fractions.py
--- a/Lib/fractions.py  Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/fractions.py  Sat Sep 27 11:09:15 2014 +0300
@@ -174,9 +174,12 @@ class Fraction(numbers.Rational):
 if denominator == 0:
 raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
 if _normalize:
-g = gcd(numerator, denominator)
+g = math.gcd(numerator, denominator)
 numerator //= g
 denominator //= g
+if denominator < 0:
+numerator = -numerator
+denominator = -denominator
 self._numerator = numerator
 self._denominator = denominator
 return self
diff -r e9d4288c32de Lib/test/test_math.py
--- a/Lib/test/test_math.py Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/test/test_math.py Sat Sep 27 11:09:15 2014 +0300
@@ -595,6 +595,45 @@ class MathTests(unittest.TestCase):
 s = msum(vals)
 self.assertEqual(msum(vals), math.fsum(vals))
 
+def testGcd(self):
+gcd = math.gcd
+self.assertEqual(gcd(0, 0), 0)
+self.assertEqual(gcd(1, 0), 1)
+self.assertEqual(gcd(-1, 0), 1)
+self.assertEqual(gcd(0, 1), 1)
+self.assertEqual(gcd(0, -1), 1)
+self.assertEqual(gcd(7, 1), 1)
+self.assertEqual(gcd(7, -1), 1)
+self.assertEqual(gcd(-23, 15), 1)
+self.assertEqual(gcd(120, 84), 12)
+self.assertEqual(gcd(84, -120), 12)
+self.assertEqual(gcd(1216342683557601535506311712,
+ 436522681849110124616458784), 32)
+c = 652560
+x = 434610456570399902378880679233098819019853229470286994367836600566
+y = 1064502245825115327754847244914921553977
+a = x * c
+b = y * c
+self.assertEqual(gcd(a, b), c)
+self.assertEqual(gcd(b, a), c)
+self.assertEqual(gcd(-a, b), c)
+self.assertEqual(gcd(b, -a), c)
+self.assertEqual(gcd(a, -b), c)
+self.assertEqual(gcd(-b, a), c)
+self.assertEqual(gcd(-a, -b), c)
+self.assertEqual(gcd(-b, -a), c)
+c = 576559230871654959816130551884856912003141446781646602790216406874
+a = x * c
+b = y * c
+self.assertEqual(gcd(a, b), c)
+self.assertEqual(gcd(b, a), c)
+self.assertEqual(gcd(-a, b), c)
+self.assertEqual(gcd(b, -a), c)
+self.assertEqual(gcd(a, -b), c)
+self.assertEqual(gcd(-b, a), c)
+self.assertEqual(gcd(-a, -b), c)
+self.assertEqual(gcd(-b, -a), c)
+
 def testHypot(self):
 self.assertRaises(TypeError, math.hypot)
 self.ftest('hypot(0,0)', math.hypot(0,0), 0)
diff -r e9d4288c32de Modules/mathmodule.c
--- a/Modules/mathmodule.c  Wed Sep 24 13:29:27 2014 +0300
+++ b/Modules/mathmodule.c  Fri Sep 26 21:37:23 2014 +0300
@@ -656,6 +656,22 @@ m_log10(double x)
 }
 
 
+static PyObject *
+math_gcd(PyObject *self, PyObject *args)
+{
+PyObject *a, *b;
+
+if (!PyArg_ParseTuple(args, "O!O!:gcd", &PyLong_Type, &a, &PyLong_Type, 
&b))
+return NULL;
+
+return _PyLong_GCD(a, b);
+}
+
+PyDoc_STRVAR(math_gcd_doc,
+"gcd(x, y) -> int\n\
+greatest common divisor of x and y");
+
+
 /* Call is_error when errno != 0, and where x is the result libm
  * returned.  is_error will usually set up an exception and return
  * true (1), but may return false (0) without setting up an exception.
@@ -1958,6 +1974,7 @@ static PyMethodDef math_methods[] = {
 {"frexp",   math

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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 

___diff -r e9d4288c32de Doc/library/math.rst
--- a/Doc/library/math.rst  Wed Sep 24 13:29:27 2014 +0300
+++ b/Doc/library/math.rst  Sat Sep 27 11:09:15 2014 +0300
@@ -100,6 +100,14 @@ Number-theoretic and representation func
`_\.
 
 
+.. function:: gcd(a, b)
+
+   Return the greatest common divisor of the integers *a* and *b*.  If either
+   *a* or *b* is nonzero, then the value of ``gcd(a, b)`` is the largest
+   positive integer that divides both *a* and *b*.  ``gcd(0, 0)`` returns
+   ``0``.
+
+
 .. function:: isfinite(x)
 
Return ``True`` if *x* is neither an infinity nor a NaN, and
diff -r e9d4288c32de Include/longobject.h
--- a/Include/longobject.h  Wed Sep 24 13:29:27 2014 +0300
+++ b/Include/longobject.h  Sat Sep 27 11:09:15 2014 +0300
@@ -198,6 +198,9 @@ PyAPI_FUNC(int) _PyLong_FormatAdvancedWr
 PyAPI_FUNC(unsigned long) PyOS_strtoul(const char *, char **, int);
 PyAPI_FUNC(long) PyOS_strtol(const char *, char **, int);
 
+/* For use by the gcd function in mathmodule.c */
+PyAPI_FUNC(PyObject *) _PyLong_GCD(PyObject *, PyObject *);
+
 #ifdef __cplusplus
 }
 #endif
diff -r e9d4288c32de Lib/fractions.py
--- a/Lib/fractions.py  Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/fractions.py  Sat Sep 27 11:09:15 2014 +0300
@@ -174,9 +174,12 @@ class Fraction(numbers.Rational):
 if denominator == 0:
 raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
 if _normalize:
-g = gcd(numerator, denominator)
+g = math.gcd(numerator, denominator)
 numerator //= g
 denominator //= g
+if denominator < 0:
+numerator = -numerator
+denominator = -denominator
 self._numerator = numerator
 self._denominator = denominator
 return self
diff -r e9d4288c32de Lib/test/test_math.py
--- a/Lib/test/test_math.py Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/test/test_math.py Sat Sep 27 11:09:15 2014 +0300
@@ -595,6 +595,45 @@ class MathTests(unittest.TestCase):
 s = msum(vals)
 self.assertEqual(msum(vals), math.fsum(vals))
 
+def testGcd(self):
+gcd = math.gcd
+self.assertEqual(gcd(0, 0), 0)
+self.assertEqual(gcd(1, 0), 1)
+self.assertEqual(gcd(-1, 0), 1)
+self.assertEqual(gcd(0, 1), 1)
+self.assertEqual(gcd(0, -1), 1)
+self.assertEqual(gcd(7, 1), 1)
+self.assertEqual(gcd(7, -1), 1)
+self.assertEqual(gcd(-23, 15), 1)
+self.assertEqual(gcd(120, 84), 12)
+self.assertEqual(gcd(84, -120), 12)
+self.assertEqual(gcd(1216342683557601535506311712,
+ 436522681849110124616458784), 32)
+c = 652560
+x = 434610456570399902378880679233098819019853229470286994367836600566
+y = 1064502245825115327754847244914921553977
+a = x * c
+b = y * c
+self.assertEqual(gcd(a, b), c)
+self.assertEqual(gcd(b, a), c)
+self.assertEqual(gcd(-a, b), c)
+self.assertEqual(gcd(b, -a), c)
+self.assertEqual(gcd(a, -b), c)
+self.assertEqual(gcd(-b, a), c)
+self.assertEqual(gcd(-a, -b), c)
+self.assertEqual(gcd(-b, -a), c)
+c = 576559230871654959816130551884856912003141446781646602790216406874
+a = x * c
+b = y * c
+self.assertEqual(gcd(a, b), c)
+self.assertEqual(gcd(b, a), c)
+self.assertEqual(gcd(-a, b), c)
+self.assertEqual(gcd(b, -a), c)
+self.assertEqual(gcd(a, -b), c)
+self.assertEqual(gcd(-b, a), c)
+self.assertEqual(gcd(-a, -b), c)
+self.assertEqual(gcd(-b, -a), c)
+
 def testHypot(self):
 self.assertRaises(TypeError, math.hypot)
 self.ftest('hypot(0,0)', math.hypot(0,0), 0)
diff -r e9d4288c32de Modules/mathmodule.c
--- a/Modules/mathmodule.c  Wed Sep 24 13:29:27 2014 +0300
+++ b/Modules/mathmodule.c  Sat Sep 27 11:09:15 2014 +0300
@@ -656,6 +656,22 @@ m_log10(double x)
 }
 
 
+static PyObject *
+math_gcd(PyObject *self, PyObject *args)
+{
+PyObject *a, *b;
+
+if (!PyArg_ParseTuple(args, "O!O!:gcd", &PyLong_Type, &a, &PyLong_Type, 
&b))
+return NULL;
+
+return _PyLong_GCD(a, b);
+}
+
+PyDoc_STRVAR(math_gcd_doc,
+"gcd(x, y) -> int\n\
+greatest common divisor of x and y");
+
+
 /* Call is_error when errno != 0, and where x is the result libm
  * returned.  is_error will usually set up an exception and return
  * true (1), but may return false (0) without setting up an exception.
@@ -1958,6 +1974,7 @@ static PyMethodDef mat

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

Mark Dickinson added the comment:

> too it.

Bah. "to it".  Stupid fingers.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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 there that uses it in that way.  It also just happens to work 
for nonnegative finite float inputs, because a % b gives exact results when a 
and b are positive floats, so no error is introduced at any point.

I'd also worry about breaking existing uses involving integer-like objects 
(instances of numpy.int64, for example) in place of instances of ints.

[1] By "works", I mean that if a and b are Fractions then gcd(a, b) returns a 
Fraction such that (1) a and b are integer multiples of gcd(a, b), and (2) 
gcd(a, b) is an integer multiple of any other number with this property.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

Stefan Behnel added the comment:

I can confirm that it works with 15 bit digits.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

Stefan Behnel added the comment:

I compiled it with 30 bit digits, in case that's relevant. (It might be.)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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 results of long_abs() (it can fail).
* Merged _PyLong_GCD and long_gcd. Fast path for small negative integers no 
longer need to copy long objects in long_abs().
* Added tests for large negative numbers and for case Py_SIZE(a) - Py_SIZE(b) > 
3.

--
Added file: http://bugs.python.org/file36726/lehmer_gcd_6.patch

___
Python tracker 

___diff -r e9d4288c32de Doc/library/math.rst
--- a/Doc/library/math.rst  Wed Sep 24 13:29:27 2014 +0300
+++ b/Doc/library/math.rst  Thu Sep 25 23:10:36 2014 +0300
@@ -100,6 +100,14 @@ Number-theoretic and representation func
`_\.
 
 
+.. function:: gcd(a, b)
+
+   Return the greatest common divisor of the integers *a* and *b*.  If either
+   *a* or *b* is nonzero, then the value of ``gcd(a, b)`` is the largest
+   positive integer that divides both *a* and *b*.  ``gcd(0, 0)`` returns
+   ``0``.
+
+
 .. function:: isfinite(x)
 
Return ``True`` if *x* is neither an infinity nor a NaN, and
diff -r e9d4288c32de Include/longobject.h
--- a/Include/longobject.h  Wed Sep 24 13:29:27 2014 +0300
+++ b/Include/longobject.h  Thu Sep 25 23:10:36 2014 +0300
@@ -198,6 +198,9 @@ PyAPI_FUNC(int) _PyLong_FormatAdvancedWr
 PyAPI_FUNC(unsigned long) PyOS_strtoul(const char *, char **, int);
 PyAPI_FUNC(long) PyOS_strtol(const char *, char **, int);
 
+/* For use by the gcd function in mathmodule.c */
+PyAPI_FUNC(PyObject *) _PyLong_GCD(PyObject *, PyObject *);
+
 #ifdef __cplusplus
 }
 #endif
diff -r e9d4288c32de Lib/fractions.py
--- a/Lib/fractions.py  Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/fractions.py  Thu Sep 25 23:10:36 2014 +0300
@@ -20,9 +20,9 @@ def gcd(a, b):
 Unless b==0, the result will have the same sign as b (so that when
 b is divided by it, the result comes out positive).
 """
-while b:
-a, b = b, a%b
-return a
+if (b or a) < 0:
+return -math.gcd(a, b)
+return math.gcd(a, b)
 
 # Constants related to the hash implementation;  hash(x) is based
 # on the reduction of x modulo the prime _PyHASH_MODULUS.
@@ -174,9 +174,12 @@ class Fraction(numbers.Rational):
 if denominator == 0:
 raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
 if _normalize:
-g = gcd(numerator, denominator)
+g = math.gcd(numerator, denominator)
 numerator //= g
 denominator //= g
+if denominator < 0:
+numerator = -numerator
+denominator = -denominator
 self._numerator = numerator
 self._denominator = denominator
 return self
diff -r e9d4288c32de Lib/test/test_math.py
--- a/Lib/test/test_math.py Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/test/test_math.py Thu Sep 25 23:10:36 2014 +0300
@@ -595,6 +595,43 @@ class MathTests(unittest.TestCase):
 s = msum(vals)
 self.assertEqual(msum(vals), math.fsum(vals))
 
+def testGcd(self):
+gcd = math.gcd
+self.assertEqual(gcd(0, 0), 0)
+self.assertEqual(gcd(1, 0), 1)
+self.assertEqual(gcd(-1, 0), 1)
+self.assertEqual(gcd(0, 1), 1)
+self.assertEqual(gcd(0, -1), 1)
+self.assertEqual(gcd(7, 1), 1)
+self.assertEqual(gcd(7, -1), 1)
+self.assertEqual(gcd(-23, 15), 1)
+self.assertEqual(gcd(120, 84), 12)
+self.assertEqual(gcd(84, -120), 12)
+c = 652560
+x = 434610456570399902378880679233098819019853229470286994367836600566
+y = 1064502245825115327754847244914921553977
+a = x * c
+b = y * c
+self.assertEqual(gcd(a, b), c)
+self.assertEqual(gcd(b, a), c)
+self.assertEqual(gcd(-a, b), c)
+self.assertEqual(gcd(b, -a), c)
+self.assertEqual(gcd(a, -b), c)
+self.assertEqual(gcd(-b, a), c)
+self.assertEqual(gcd(-a, -b), c)
+self.assertEqual(gcd(-b, -a), c)
+c = 576559230871654959816130551884856912003141446781646602790216406874
+a = x * c
+b = y * c
+self.assertEqual(gcd(a, b), c)
+self.assertEqual(gcd(b, a), c)
+self.assertEqual(gcd(-a, b), c)
+self.assertEqual(gcd(b, -a), c)
+self.assertEqual(gcd(a, -b), c)
+self.assertEqual(gcd(-b, a), c)
+self.assertEqual(gcd(-a, -b), c)
+self.assertEqual(gcd(-b, -a), c)
+
 def testHypot(self):
 self.assertRaises(TypeError, math.hypot)
 self.ftest('hypot(0,0)', math.hypot(0,0), 0)
diff -r e9d4288c32de Modules/mathmodule.c
--- a/Modules/mathmodule.c  Wed Sep 24 13:2

[issue22486] Add math.gcd()

[Mark Dickinson]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Mark Dickinson]

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 integer inputs, for backwards compatibility.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[gladman]

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 co-exist with fractions.gcd(), with identical semantics?

Or would it co-exist with fractions.gcd(), with the 'less surprising' semantics 
that are under discussion in the 'GCD in Fractions' thread?

Would it take on the suggestion of operating on one or more input parameters?

--
nosy: +gladman

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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 

___diff -r e9d4288c32de Doc/library/math.rst
--- a/Doc/library/math.rst  Wed Sep 24 13:29:27 2014 +0300
+++ b/Doc/library/math.rst  Thu Sep 25 15:51:26 2014 +0300
@@ -100,6 +100,14 @@ Number-theoretic and representation func
`_\.
 
 
+.. function:: gcd(a, b)
+
+   Return the greatest common divisor of the integers *a* and *b*.  If either
+   *a* or *b* is nonzero, then the value of ``gcd(a, b)`` is the largest
+   positive integer that divides both *a* and *b*.  ``gcd(0, 0)`` returns
+   ``0``.
+
+
 .. function:: isfinite(x)
 
Return ``True`` if *x* is neither an infinity nor a NaN, and
diff -r e9d4288c32de Include/longobject.h
--- a/Include/longobject.h  Wed Sep 24 13:29:27 2014 +0300
+++ b/Include/longobject.h  Thu Sep 25 15:51:26 2014 +0300
@@ -198,6 +198,9 @@ PyAPI_FUNC(int) _PyLong_FormatAdvancedWr
 PyAPI_FUNC(unsigned long) PyOS_strtoul(const char *, char **, int);
 PyAPI_FUNC(long) PyOS_strtol(const char *, char **, int);
 
+/* For use by the gcd function in mathmodule.c */
+PyAPI_FUNC(PyObject *) _PyLong_GCD(PyObject *, PyObject *);
+
 #ifdef __cplusplus
 }
 #endif
diff -r e9d4288c32de Lib/fractions.py
--- a/Lib/fractions.py  Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/fractions.py  Thu Sep 25 15:51:26 2014 +0300
@@ -20,9 +20,9 @@ def gcd(a, b):
 Unless b==0, the result will have the same sign as b (so that when
 b is divided by it, the result comes out positive).
 """
-while b:
-a, b = b, a%b
-return a
+if (b or a) < 0:
+return -math.gcd(a, b)
+return math.gcd(a, b)
 
 # Constants related to the hash implementation;  hash(x) is based
 # on the reduction of x modulo the prime _PyHASH_MODULUS.
@@ -174,9 +174,12 @@ class Fraction(numbers.Rational):
 if denominator == 0:
 raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
 if _normalize:
-g = gcd(numerator, denominator)
+g = math.gcd(numerator, denominator)
 numerator //= g
 denominator //= g
+if denominator < 0:
+numerator = -numerator
+denominator = -denominator
 self._numerator = numerator
 self._denominator = denominator
 return self
diff -r e9d4288c32de Lib/test/test_math.py
--- a/Lib/test/test_math.py Wed Sep 24 13:29:27 2014 +0300
+++ b/Lib/test/test_math.py Thu Sep 25 15:51:26 2014 +0300
@@ -595,6 +595,24 @@ class MathTests(unittest.TestCase):
 s = msum(vals)
 self.assertEqual(msum(vals), math.fsum(vals))
 
+def testGcd(self):
+self.assertEqual(gcd(0, 0), 0)
+self.assertEqual(gcd(1, 0), 1)
+self.assertEqual(gcd(-1, 0), 1)
+self.assertEqual(gcd(0, 1), 1)
+self.assertEqual(gcd(0, -1), 1)
+self.assertEqual(gcd(7, 1), 1)
+self.assertEqual(gcd(7, -1), 1)
+self.assertEqual(gcd(-23, 15), 1)
+self.assertEqual(gcd(120, 84), 12)
+self.assertEqual(gcd(84, -120), 12)
+self.assertEqual(gcd(190738355881570558882299312308821696901058000,
+ 76478560266291874249006856460326062498333440),
+ 652560)
+
self.assertEqual(gcd(83763289342793979220453055528167457860243376086879213707165435635135627040075,
+ 
33585776402955145260404154387726204875807368546078094789530226423049489520976),
+ 286573572687563623189610484223662247799)
+
 def testHypot(self):
 self.assertRaises(TypeError, math.hypot)
 self.ftest('hypot(0,0)', math.hypot(0,0), 0)
diff -r e9d4288c32de Modules/mathmodule.c
--- a/Modules/mathmodule.c  Wed Sep 24 13:29:27 2014 +0300
+++ b/Modules/mathmodule.c  Thu Sep 25 15:51:26 2014 +0300
@@ -656,6 +656,22 @@ m_log10(double x)
 }
 
 
+static PyObject *
+math_gcd(PyObject *self, PyObject *args)
+{
+PyObject *a, *b;
+
+if (!PyArg_ParseTuple(args, "O!O!:gcd", &PyLong_Type, &a, &PyLong_Type, 
&b))
+return NULL;
+
+return _PyLong_GCD(a, b);
+}
+
+PyDoc_STRVAR(math_gcd_doc,
+"gcd(x, y) -> int\n\
+greatest common divisor of x and y");
+
+
 /* Call is_error when errno != 0, and where x is the result libm
  * returned.  is_error will usually set up an exception and return
  * true (1), but may return false (0) without setting up an exception.
@@ -1958,6 +1974,7 @@ static PyMethodDef math_methods[] = {
 {"frexp",   math_frexp, METH_O, math_frexp_doc},
 {"fsum",math_fsum,  METH_O, math_fsum_doc},
 {"gamma",   math_gamma, METH_O, math_gamma_doc},
+

[issue22486] Add math.gcd()

[Wolfgang Maier]

Wolfgang Maier added the comment:

I wasn't arguing for or against anything, just providing a link to the relevant 
discussion.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Wolfgang Maier]

Wolfgang Maier added the comment:

sorry, forgot to format the link:
issue<22477>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Wolfgang Maier]

Wolfgang Maier added the comment:

see issue22477 for a discussion of whether the behavior of fractions.gcd should 
be changed or not

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

Stefan Behnel added the comment:

Oh, and thanks for working on it, Serhiy! :)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Stefan Behnel]

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:  -Extension Modules
type: enhancement -> performance

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
keywords: +patch
Added file: http://bugs.python.org/file36722/lehmer_gcd_4.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue22486] Add math.gcd()

[Serhiy Storchaka]

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 about 20%.

--
components: +Extension Modules
nosy: +serhiy.storchaka
stage:  -> patch review
title: Speed up fractions.gcd() -> Add math.gcd()
type: performance -> enhancement

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com