Title: modulo for huge integers has the wrong complexity · Issue #160050 · python/cpython · GitHub
Open Graph Title: modulo for huge integers has the wrong complexity · Issue #160050 · python/cpython
X Title: modulo for huge integers has the wrong complexity · Issue #160050 · python/cpython
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...
Open Graph 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, wh...
X 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, wh...
Opengraph URL: https://github.com/python/cpython/issues/160050
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"modulo for huge integers has the wrong complexity","articleBody":"### Bug report\n\nin PR https://github.com/python/cpython/pull/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.\n\nthis has the paradoxical effect that calling divmod and discarding the division result can become arbitrarily much faster than just using `%`.\n\ntrivial benchmark script:\n\n```python\nimport random\nimport timeit\n\nrng = random.Random(1729)\nbits = 1000\n\n# import the python implementation early\ndivmod((1 \u003c\u003c 32768) - 1, (1 \u003c\u003c 16384) + 1)\n\nprint(\"divisor bits // (s) % (s) divmod (s) mod vs div slowdown\")\nwhile True:\n a = rng.getrandbits(2 * bits) | (1 \u003c\u003c (2 * bits - 1))\n b = rng.getrandbits(bits) | (1 \u003c\u003c (bits - 1))\n print(f\"{bits:12,d}\", end=\"\", flush=True)\n results = []\n for expression in (\"a // b\", \"a % b\", \"divmod(a, b)\"):\n elapsed = timeit.timeit(expression, number=1, globals={\"a\": a, \"b\": b})\n results.append(elapsed)\n print(f\" {elapsed:12.6f}\", end=\"\", flush=True)\n print(f\" {results[1]/results[0]:12.3}x\")\n bits *= 2\n```\n\nresults on my laptop with current main:\n\n```\ndivisor bits // (s) % (s) divmod (s) mod vs div slowdown\n 1,000 0.000002 0.000002 0.000002 0.85x\n 2,000 0.000005 0.000005 0.000006 0.986x\n 4,000 0.000018 0.000018 0.000018 0.992x\n 8,000 0.000068 0.000068 0.000068 0.998x\n 16,000 0.000180 0.000270 0.000174 1.5x\n 32,000 0.000511 0.001074 0.000489 2.1x\n 64,000 0.001403 0.004048 0.001447 2.89x\n 128,000 0.004176 0.018183 0.004565 4.35x\n 256,000 0.013406 0.066950 0.013006 4.99x\n 512,000 0.041252 0.259250 0.040267 6.28x\n 1,024,000 0.114946 1.021364 0.118319 8.89x\n 2,048,000 0.341928 4.115463 0.344250 12.0x\n 4,096,000 1.038594 16.368831 1.016546 15.8x\n```\n\nresults in pypy3:\n\n```\ndivisor bits // (s) % (s) divmod (s) mod vs div slowdown\n 1,000 0.000004 0.000003 0.000005 0.738x\n 2,000 0.000003 0.000003 0.000003 0.926x\n 4,000 0.000016 0.000013 0.000013 0.843x\n 8,000 0.000036 0.000034 0.000035 0.947x\n 16,000 0.001038 0.000263 0.000120 0.254x\n 32,000 0.000357 0.000491 0.000358 1.37x\n 64,000 0.001301 0.001189 0.001136 0.914x\n 128,000 0.003612 0.003099 0.003865 0.858x\n 256,000 0.013143 0.010523 0.011387 0.801x\n 512,000 0.031886 0.031680 0.032254 0.994x\n 1,024,000 0.092896 0.082590 0.080995 0.889x\n 2,048,000 0.242731 0.237929 0.240054 0.98x\n 4,096,000 0.717197 0.713346 0.714341 0.995x\n 8,192,000 2.150150 2.185075 2.148571 1.02x\n 16,384,000 6.418406 6.434706 6.483382 1.0x\n```\n\n### CPython versions tested on:\n\nCPython main branch\n\n### Operating systems tested on:\n\nLinux\n\n\u003c!-- gh-linked-prs -->\n### Linked PRs\n* gh-160443\n\u003c!-- /gh-linked-prs -->\n","author":{"url":"https://github.com/cfbolz","@type":"Person","name":"cfbolz"},"datePublished":"2026-10-21T16:42:29Z","url":"https://github.com/python/cpython/issues/160050"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:c65afd93-4ca5-9f56-f5e6-298cd1764a88 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | 9946:1F927B:1725FD5:1E8CFC1:6B020238 |
| html-safe-nonce | 5887193794ff34eb3cccbe2823be346bb758d0c6a8ff7c3da474e61d3a1f2c92 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI5OTQ2OjFGOTI3QjoxNzI1RkQ1OjFFOENGQzE6NkIwMjAyMzgiLCJ2aXNpdG9yX2lkIjoiNTU2OTUwNjk2NDY2NjQ1MDQ4OCIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | e81229ffaeb0236db2deb394dd89264027350410696881f06308dde9129cf9ed |
| hovercard-subject-tag | issue:5964649223 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/160050/issue_layout |
| twitter:image | https://opengraph.githubassets.com/638ef1578238eb79267be1b2eb3c56d4ee1679d7fcc6c0436817273a10383acb/python/cpython/issues/160050 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/638ef1578238eb79267be1b2eb3c56d4ee1679d7fcc6c0436817273a10383acb/python/cpython/issues/160050 |
| og:image:alt | 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, wh... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | cfbolz |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width