X Tutup
Skip to content

Commit 48e47aa

Browse files
serhiy-storchakaserhiy-storchaka
committed
Issue python#22486: Added the math.gcd() function. The fractions.gcd() function now is
deprecated. Based on patch by Mark Dickinson.
1 parent f0eeedf commit 48e47aa

File tree

9 files changed

+342
-13
lines changed

9 files changed

+342
-13
lines changed

‎Doc/library/fractions.rst‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -172,6 +172,9 @@ another rational number, or from a string.
172172
sign as *b* if *b* is nonzero; otherwise it takes the sign of *a*. ``gcd(0,
173173
0)`` returns ``0``.
174174

175+
.. deprecated:: 3.5
176+
Use :func:`math.gcd` instead.
177+
175178

176179
.. seealso::
177180

‎Doc/library/math.rst‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,14 @@ Number-theoretic and representation functions
100100
<http://code.activestate.com/recipes/393090/>`_\.
101101

102102

103+
.. function:: gcd(a, b)
104+
105+
Return the greatest common divisor of the integers *a* and *b*. If either
106+
*a* or *b* is nonzero, then the value of ``gcd(a, b)`` is the largest
107+
positive integer that divides both *a* and *b*. ``gcd(0, 0)`` returns
108+
``0``.
109+
110+
103111
.. function:: isfinite(x)
104112

105113
Return ``True`` if *x* is neither an infinity nor a NaN, and

‎Include/longobject.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -198,6 +198,9 @@ PyAPI_FUNC(int) _PyLong_FormatAdvancedWriter(
198198
PyAPI_FUNC(unsigned long) PyOS_strtoul(const char *, char **, int);
199199
PyAPI_FUNC(long) PyOS_strtol(const char *, char **, int);
200200

201+
/* For use by the gcd function in mathmodule.c */
202+
PyAPI_FUNC(PyObject *) _PyLong_GCD(PyObject *, PyObject *);
203+
201204
#ifdef __cplusplus
202205
}
203206
#endif

‎Lib/fractions.py‎

Lines changed: 19 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,17 @@ def gcd(a, b):
2020
Unless b==0, the result will have the same sign as b (so that when
2121
b is divided by it, the result comes out positive).
2222
"""
23+
import warnings
24+
warnings.warn('fractions.gcd() is deprecated. Use math.gcd() instead.',
25+
DeprecationWarning, 2)
26+
if type(a) is int is type(b):
27+
if (b or a) < 0:
28+
return -math.gcd(a, b)
29+
return math.gcd(a, b)
30+
return _gcd(a, b)
31+
32+
def _gcd(a, b):
33+
# Supports non-integers for backward compatibility.
2334
while b:
2435
a, b = b, a%b
2536
return a
@@ -159,7 +170,7 @@ def __new__(cls, numerator=0, denominator=None, _normalize=True):
159170
"or a Rational instance")
160171

161172
elif type(numerator) is int is type(denominator):
162-
pass # *very* normal case
173+
pass # *very* normal case
163174

164175
elif (isinstance(numerator, numbers.Rational) and
165176
isinstance(denominator, numbers.Rational)):
@@ -174,7 +185,13 @@ def __new__(cls, numerator=0, denominator=None, _normalize=True):
174185
if denominator == 0:
175186
raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
176187
if _normalize:
177-
g = gcd(numerator, denominator)
188+
if type(numerator) is int is type(denominator):
189+
# *very* normal case
190+
g = math.gcd(numerator, denominator)
191+
if denominator < 0:
192+
g = -g
193+
else:
194+
g = _gcd(numerator, denominator)
178195
numerator //= g
179196
denominator //= g
180197
self._numerator = numerator

‎Lib/test/test_fractions.py‎

Lines changed: 22 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
import fractions
99
import sys
1010
import unittest
11+
import warnings
1112
from copy import copy, deepcopy
1213
from pickle import dumps, loads
1314
F = fractions.Fraction
@@ -49,7 +50,7 @@ class DummyRational(object):
4950
"""Test comparison of Fraction with a naive rational implementation."""
5051

5152
def __init__(self, num, den):
52-
g = gcd(num, den)
53+
g = math.gcd(num, den)
5354
self.num = num // g
5455
self.den = den // g
5556

@@ -83,16 +84,26 @@ class DummyFraction(fractions.Fraction):
8384
class GcdTest(unittest.TestCase):
8485

8586
def testMisc(self):
86-
self.assertEqual(0, gcd(0, 0))
87-
self.assertEqual(1, gcd(1, 0))
88-
self.assertEqual(-1, gcd(-1, 0))
89-
self.assertEqual(1, gcd(0, 1))
90-
self.assertEqual(-1, gcd(0, -1))
91-
self.assertEqual(1, gcd(7, 1))
92-
self.assertEqual(-1, gcd(7, -1))
93-
self.assertEqual(1, gcd(-23, 15))
94-
self.assertEqual(12, gcd(120, 84))
95-
self.assertEqual(-12, gcd(84, -120))
87+
# fractions.gcd() is deprecated
88+
with self.assertWarnsRegex(DeprecationWarning, r'fractions\.gcd'):
89+
gcd(1, 1)
90+
with warnings.catch_warnings():
91+
warnings.filterwarnings('ignore', r'fractions\.gcd',
92+
DeprecationWarning)
93+
self.assertEqual(0, gcd(0, 0))
94+
self.assertEqual(1, gcd(1, 0))
95+
self.assertEqual(-1, gcd(-1, 0))
96+
self.assertEqual(1, gcd(0, 1))
97+
self.assertEqual(-1, gcd(0, -1))
98+
self.assertEqual(1, gcd(7, 1))
99+
self.assertEqual(-1, gcd(7, -1))
100+
self.assertEqual(1, gcd(-23, 15))
101+
self.assertEqual(12, gcd(120, 84))
102+
self.assertEqual(-12, gcd(84, -120))
103+
self.assertEqual(gcd(120.0, 84), 12.0)
104+
self.assertEqual(gcd(120, 84.0), 12.0)
105+
self.assertEqual(gcd(F(120), F(84)), F(12))
106+
self.assertEqual(gcd(F(120, 77), F(84, 55)), F(12, 385))
96107

97108

98109
def _components(r):

‎Lib/test/test_math.py‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -175,6 +175,14 @@ def parse_testfile(fname):
175175
flags
176176
)
177177

178+
# Class providing an __index__ method.
179+
class MyIndexable(object):
180+
def __init__(self, value):
181+
self.value = value
182+
183+
def __index__(self):
184+
return self.value
185+
178186
class MathTests(unittest.TestCase):
179187

180188
def ftest(self, name, value, expected):
@@ -595,6 +603,49 @@ def msum(iterable):
595603
s = msum(vals)
596604
self.assertEqual(msum(vals), math.fsum(vals))
597605

606+
def testGcd(self):
607+
gcd = math.gcd
608+
self.assertEqual(gcd(0, 0), 0)
609+
self.assertEqual(gcd(1, 0), 1)
610+
self.assertEqual(gcd(-1, 0), 1)
611+
self.assertEqual(gcd(0, 1), 1)
612+
self.assertEqual(gcd(0, -1), 1)
613+
self.assertEqual(gcd(7, 1), 1)
614+
self.assertEqual(gcd(7, -1), 1)
615+
self.assertEqual(gcd(-23, 15), 1)
616+
self.assertEqual(gcd(120, 84), 12)
617+
self.assertEqual(gcd(84, -120), 12)
618+
self.assertEqual(gcd(1216342683557601535506311712,
619+
436522681849110124616458784), 32)
620+
c = 652560
621+
x = 434610456570399902378880679233098819019853229470286994367836600566
622+
y = 1064502245825115327754847244914921553977
623+
a = x * c
624+
b = y * c
625+
self.assertEqual(gcd(a, b), c)
626+
self.assertEqual(gcd(b, a), c)
627+
self.assertEqual(gcd(-a, b), c)
628+
self.assertEqual(gcd(b, -a), c)
629+
self.assertEqual(gcd(a, -b), c)
630+
self.assertEqual(gcd(-b, a), c)
631+
self.assertEqual(gcd(-a, -b), c)
632+
self.assertEqual(gcd(-b, -a), c)
633+
c = 576559230871654959816130551884856912003141446781646602790216406874
634+
a = x * c
635+
b = y * c
636+
self.assertEqual(gcd(a, b), c)
637+
self.assertEqual(gcd(b, a), c)
638+
self.assertEqual(gcd(-a, b), c)
639+
self.assertEqual(gcd(b, -a), c)
640+
self.assertEqual(gcd(a, -b), c)
641+
self.assertEqual(gcd(-b, a), c)
642+
self.assertEqual(gcd(-a, -b), c)
643+
self.assertEqual(gcd(-b, -a), c)
644+
645+
self.assertRaises(TypeError, gcd, 120.0, 84)
646+
self.assertRaises(TypeError, gcd, 120, 84.0)
647+
self.assertEqual(gcd(MyIndexable(120), MyIndexable(84)), 12)
648+
598649
def testHypot(self):
599650
self.assertRaises(TypeError, math.hypot)
600651
self.ftest('hypot(0,0)', math.hypot(0,0), 0)

‎Misc/NEWS‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,9 @@ Core and Builtins
4242
Library
4343
-------
4444

45+
- Issue #22486: Added the math.gcd() function. The fractions.gcd() function now is
46+
deprecated. Based on patch by Mark Dickinson.
47+
4548
- Issue #22681: Added support for the koi8_t encoding.
4649

4750
- Issue #22682: Added support for the kz1048 encoding.

‎Modules/mathmodule.c‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -685,6 +685,33 @@ m_log10(double x)
685685
}
686686

687687

688+
static PyObject *
689+
math_gcd(PyObject *self, PyObject *args)
690+
{
691+
PyObject *a, *b, *g;
692+
693+
if (!PyArg_ParseTuple(args, "OO:gcd", &a, &b))
694+
return NULL;
695+
696+
a = PyNumber_Index(a);
697+
if (a == NULL)
698+
return NULL;
699+
b = PyNumber_Index(b);
700+
if (b == NULL) {
701+
Py_DECREF(a);
702+
return NULL;
703+
}
704+
g = _PyLong_GCD(a, b);
705+
Py_DECREF(a);
706+
Py_DECREF(b);
707+
return g;
708+
}
709+
710+
PyDoc_STRVAR(math_gcd_doc,
711+
"gcd(x, y) -> int\n\
712+
greatest common divisor of x and y");
713+
714+
688715
/* Call is_error when errno != 0, and where x is the result libm
689716
* returned. is_error will usually set up an exception and return
690717
* true (1), but may return false (0) without setting up an exception.
@@ -1987,6 +2014,7 @@ static PyMethodDef math_methods[] = {
19872014
{"frexp", math_frexp, METH_O, math_frexp_doc},
19882015
{"fsum", math_fsum, METH_O, math_fsum_doc},
19892016
{"gamma", math_gamma, METH_O, math_gamma_doc},
2017+
{"gcd", math_gcd, METH_VARARGS, math_gcd_doc},
19902018
{"hypot", math_hypot, METH_VARARGS, math_hypot_doc},
19912019
{"isfinite", math_isfinite, METH_O, math_isfinite_doc},
19922020
{"isinf", math_isinf, METH_O, math_isinf_doc},

0 commit comments

Comments
 (0)
X Tutup