Repository navigation
modulo for huge integers has the wrong complexity #160050
Description
Bug report
in PR #96673 the complexity of integer division and divmod was improved. however, plain modulo still uses the previous code path. specifically, long_div and long_divmod call l_divmod, which dispatches to pylong_int_divmod when the sizes get large enough. otoh, long_mod calls l_mod, which calls long_rem, never going to the asymptotically faster pure python version.
this has the paradoxical effect that calling divmod and discarding the division result can become arbitrarily much faster than just using %.
trivial benchmark script:
import random
import timeit
rng = random.Random(1729)
bits = 1000
# import the python implementation early
divmod((1 << 32768) - 1, (1 << 16384) + 1)
print("divisor bits // (s) % (s) divmod (s) mod vs div slowdown")
while True:
a = rng.getrandbits(2 * bits) | (1 << (2 * bits - 1))
b = rng.getrandbits(bits) | (1 << (bits - 1))
print(f"{bits:12,d}", end="", flush=True)
results = []
for expression in ("a // b", "a % b", "divmod(a, b)"):
elapsed = timeit.timeit(expression, number=1, globals={"a": a, "b": b})
results.append(elapsed)
print(f" {elapsed:12.6f}", end="", flush=True)
print(f" {results[1]/results[0]:12.3}x")
bits *= 2results on my laptop with current main:
divisor bits // (s) % (s) divmod (s) mod vs div slowdown
1,000 0.000002 0.000002 0.000002 0.85x
2,000 0.000005 0.000005 0.000006 0.986x
4,000 0.000018 0.000018 0.000018 0.992x
8,000 0.000068 0.000068 0.000068 0.998x
16,000 0.000180 0.000270 0.000174 1.5x
32,000 0.000511 0.001074 0.000489 2.1x
64,000 0.001403 0.004048 0.001447 2.89x
128,000 0.004176 0.018183 0.004565 4.35x
256,000 0.013406 0.066950 0.013006 4.99x
512,000 0.041252 0.259250 0.040267 6.28x
1,024,000 0.114946 1.021364 0.118319 8.89x
2,048,000 0.341928 4.115463 0.344250 12.0x
4,096,000 1.038594 16.368831 1.016546 15.8x
results in pypy3:
divisor bits // (s) % (s) divmod (s) mod vs div slowdown
1,000 0.000004 0.000003 0.000005 0.738x
2,000 0.000003 0.000003 0.000003 0.926x
4,000 0.000016 0.000013 0.000013 0.843x
8,000 0.000036 0.000034 0.000035 0.947x
16,000 0.001038 0.000263 0.000120 0.254x
32,000 0.000357 0.000491 0.000358 1.37x
64,000 0.001301 0.001189 0.001136 0.914x
128,000 0.003612 0.003099 0.003865 0.858x
256,000 0.013143 0.010523 0.011387 0.801x
512,000 0.031886 0.031680 0.032254 0.994x
1,024,000 0.092896 0.082590 0.080995 0.889x
2,048,000 0.242731 0.237929 0.240054 0.98x
4,096,000 0.717197 0.713346 0.714341 0.995x
8,192,000 2.150150 2.185075 2.148571 1.02x
16,384,000 6.418406 6.434706 6.483382 1.0x
CPython versions tested on:
CPython main branch
Operating systems tested on:
Linux
Activity
lazerg commentedon Oct 21, 2026
Are you planning to send a PR for this? If not, I have a small patch that makes
l_mod()use the same_pylongpath asl_divmod()and can open it.cfbolz commentedon Oct 21, 2026
I don't necessarily want to work on this, if you have a draft go for it
skirpichev commentedon Oct 22, 2026
Patch should be trivial (size constraints are same as for divmod):
With above: