Skip to content

gh-90716: add _pylong.py module #96673

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
nascheme merged 6 commits into from
Oct 26, 2022
Merged

gh-90716: add _pylong.py module #96673

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
136fad2
Add _pylong.py module.
nascheme Sep 8, 2022
0df1528
Avoid the quadratic behaviour inside _divmod_pos.
nascheme Sep 26, 2022
bd6cd70
Improve comments, remove unneeded case.
nascheme Sep 26, 2022
68b1737
Tweak _DIV_LIMIT and improve test.
nascheme Sep 26, 2022
43d61e3
Add divmod_threshold.py script.
nascheme Sep 26, 2022
ed50a4a
Fix error handling in pylong_int_from_string().
nascheme Oct 25, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Tweak _DIV_LIMIT and improve test. 
Another optimization from Bjorn.  Adjust threshold limits in
longobject.c since the _pylong version is faster.
  • Loading branch information
@nascheme
nascheme committed Oct 25, 2022
commit 68b17374aabcfd87a9aa35998dacc4463f07b0ca
4 changes: 2 additions & 2 deletions Lib/_pylong.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -168,7 +168,7 @@ def str_to_int(s):
# algorithm is due to Burnikel and Ziegler, in their paper "Fast Recursive
# Division".

_DIV_LIMIT = 1000
_DIV_LIMIT = 4000


def _div2n1n(a, b, n):
Expand All @@ -184,7 +184,7 @@ def _div2n1n(a, b, n):
(q, r) such that a = b*q+r and 0 <= r < b.

"""
if n <= _DIV_LIMIT:
if a.bit_length() - n <= _DIV_LIMIT:
return divmod(a, b)
pad = n & 1
if pad:
Expand Down
4 changes: 2 additions & 2 deletions Objects/longobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4122,11 +4122,11 @@ l_divmod(PyLongObject *v, PyLongObject *w,
#if WITH_PYLONG_MODULE
Py_ssize_t size_v = Py_ABS(Py_SIZE(v)); /* digits in numerator */
Py_ssize_t size_w = Py_ABS(Py_SIZE(w)); /* digits in denominator */
if (size_w > 500 && (size_v - size_w) > 250) {
if (size_w > 300 && (size_v - size_w) > 150) {
/* Switch to _pylong.int_divmod(). If the quotient is small then
"schoolbook" division is linear-time so don't use in that case.
These limits are empirically determined and should be slightly
conservative so that _pylong gets used in cases it is likely
conservative so that _pylong is used in cases it is likely
to be faster. */
return pylong_int_divmod(v, w, pdiv, pmod);
}
Expand Down