https://github.com/python/cpython/commit/63e7b1889beec3e67db0448ae055c5b68e7b64f3
commit: 63e7b1889beec3e67db0448ae055c5b68e7b64f3
branch: main
author: emirplus <[email protected]>
committer: StanFromIreland <[email protected]>
date: 2026-11-07T19:20:02Z
summary:
gh-160050: Use asymptotically faster divmod in `l_mod` for large integers
(#160443)
files:
A
Misc/NEWS.d/next/Core_and_Builtins/2026-10-23-19-37-00.gh-issue-160050.aB3x9Q.rst
M Lib/test/test_int.py
M Objects/longobject.c
diff --git a/Lib/test/test_int.py b/Lib/test/test_int.py
index fa675f626cbe10..40c636d586c550 100644
--- a/Lib/test/test_int.py
+++ b/Lib/test/test_int.py
@@ -778,6 +778,14 @@ def test_pylong_int_divmod(self):
a, b = divmod(n*3 + 1, n)
assert a == 3 and b == 1
+ def test_pylong_int_mod(self):
+ n = (1 << 100_000)
+ m = (1 << 50_000)
+ self.assertEqual((n * 3 + 1) % m, 1)
+ self.assertEqual((-n * 3 - 1) % m, m - 1)
+ self.assertEqual((n * 3 + 1) % -m, 1 - m)
+ self.assertEqual((-n * 3 - 1) % -m, -1)
+
@support.cpython_only # tests implementation details of CPython.
@unittest.skipUnless(_pylong, "_pylong module required")
def test_pylong_int_divmod_crash(self):
@@ -789,6 +797,7 @@ def test_pylong_int_divmod_crash(self):
with mock.patch.object(_pylong, "int_divmod", wraps=bad_int_divmod):
msg = r"tuple of length 2 is required from int_divmod\(\)"
self.assertRaisesRegex(ValueError, msg, divmod, a, b)
+ self.assertRaisesRegex(ValueError, msg, lambda: a % b)
def test_pylong_str_to_int(self):
v1 = 1 << 100_000
diff --git
a/Misc/NEWS.d/next/Core_and_Builtins/2026-10-23-19-37-00.gh-issue-160050.aB3x9Q.rst
b/Misc/NEWS.d/next/Core_and_Builtins/2026-10-23-19-37-00.gh-issue-160050.aB3x9Q.rst
new file mode 100644
index 00000000000000..9089e4bc4dbb14
--- /dev/null
+++
b/Misc/NEWS.d/next/Core_and_Builtins/2026-10-23-19-37-00.gh-issue-160050.aB3x9Q.rst
@@ -0,0 +1 @@
+Use asymptotically faster :func:`divmod` implementation for integer modulo of
large integers.
diff --git a/Objects/longobject.c b/Objects/longobject.c
index c96ed6a215b5a1..9d02793fdd6366 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -4564,6 +4564,14 @@ l_mod(PyLongObject *v, PyLongObject *w, PyLongObject
**pmod)
*pmod = (PyLongObject *)fast_mod(v, w);
return -(*pmod == NULL);
}
+#if WITH_PYLONG_MODULE
+ Py_ssize_t size_v = _PyLong_DigitCount(v); /* digits in numerator */
+ Py_ssize_t size_w = _PyLong_DigitCount(w); /* digits in denominator */
+ if (size_w > 300 && (size_v - size_w) > 150) {
+ /* Switch to _pylong.int_divmod(). See comments in l_divmod(). */
+ return pylong_int_divmod(v, w, NULL, pmod);
+ }
+#endif
if (long_rem(v, w, &mod) < 0)
return -1;
if ((_PyLong_IsNegative(mod) && _PyLong_IsPositive(w)) ||
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
