René's URL Explorer Experiment


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

direct link

Domain: github.com


Hey, it has json ld scripts:
{"@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-profiling0
react-import-mapreact,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-controllervoltron_issues_fragments
route-actionissue_layout
fetch-noncev2:c65afd93-4ca5-9f56-f5e6-298cd1764a88
current-catalog-service-hash81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114
request-id9946:1F927B:1725FD5:1E8CFC1:6B020238
html-safe-nonce5887193794ff34eb3cccbe2823be346bb758d0c6a8ff7c3da474e61d3a1f2c92
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI5OTQ2OjFGOTI3QjoxNzI1RkQ1OjFFOENGQzE6NkIwMjAyMzgiLCJ2aXNpdG9yX2lkIjoiNTU2OTUwNjk2NDY2NjQ1MDQ4OCIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9
visitor-hmace81229ffaeb0236db2deb394dd89264027350410696881f06308dde9129cf9ed
hovercard-subject-tagissue:5964649223
github-keyboard-shortcutsrepository,issues,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///voltron/issues_fragments/issue_layout
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/160050/issue_layout
twitter:imagehttps://opengraph.githubassets.com/638ef1578238eb79267be1b2eb3c56d4ee1679d7fcc6c0436817273a10383acb/python/cpython/issues/160050
twitter:cardsummary_large_image
og:imagehttps://opengraph.githubassets.com/638ef1578238eb79267be1b2eb3c56d4ee1679d7fcc6c0436817273a10383acb/python/cpython/issues/160050
og:image:altBug 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:width1200
og:image:height600
og:site_nameGitHub
og:typeobject
og:author:usernamecfbolz
hostnamegithub.com
expected-hostnamegithub.com
None87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456
turbo-cache-controlno-preview
go-importgithub.com/python/cpython git https://github.com/python/cpython.git
octolytics-dimension-user_id1525981
octolytics-dimension-user_loginpython
octolytics-dimension-repository_id81598961
octolytics-dimension-repository_nwopython/cpython
octolytics-dimension-repository_publictrue
octolytics-dimension-repository_is_forkfalse
octolytics-dimension-repository_network_root_id81598961
octolytics-dimension-repository_network_root_nwopython/cpython
turbo-body-classeslogged-out env-production page-responsive
disable-turbofalse
browser-stats-urlhttps://api.github.com/_private/browser/stats
browser-errors-urlhttps://api.github.com/_private/browser/errors
release423dbb54c5e7bfecc838eb387c1435eb3d0e760d
ui-targetfull
theme-color#1e2327
color-schemelight dark
react-app-nameissues

Links:

Skip to contenthttps://github.com/python/cpython/issues/160050#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fissues%2F160050
GitHubRepository hosting, code review, and collaborationhttps://github.com/platform
CopilotAI coding agent for tasks, projects, and automated workhttps://github.com/features/copilot
ActionsCI/CD and automationhttps://github.com/features/actions
Code QualityQuality analysis, fixes, and enforcementhttps://github.com/features/code-quality
CodespacesCloud development environmentshttps://github.com/features/codespaces
Code SecurityVulnerability detection and remediationhttps://github.com/security/advanced-security/code-security
Secret ProtectionSecret scanning and leak preventionhttps://github.com/security/advanced-security/secret-protection
All Featureshttps://github.com/features
Documentationhttps://docs.github.com/en
Traininghttps://learn.github.com/skills
Certificationshttps://learn.github.com/credentials
Build with Copilothttps://github.com/features/ai
Customize Copilothttps://docs.github.com/en/copilot/how-tos/copilot-on-github/customize-copilot/customize-copilot-overview
Integrationshttps://github.com/marketplace
Trending reposhttps://github.com/trending
GitHub Sponsorshttps://github.com/open-source/sponsors
Developer articleshttps://github.com/resources/articles
ChangelogYour source for the latest features, improvements, and fixes across GitHub products, all in one place.https://github.blog/changelog/
Enterpriseshttps://github.com/enterprise
Teamhttps://github.com/team
Startupshttps://github.com/enterprise/startups
Nonprofitshttps://github.com/solutions/industry/nonprofits
Healthcarehttps://github.com/solutions/industry/healthcare
Financial serviceshttps://github.com/solutions/industry/financial-services
Manufacturinghttps://github.com/solutions/industry/manufacturing
Governmenthttps://github.com/solutions/industry/government
See all industrieshttps://github.com/solutions/industry
Why GitHubhttps://github.com/why-github
Customer Storieshttps://github.com/customer-stories
Business insightshttps://github.com/solutions/executive-insights
Trust Centerhttps://github.com/trust-center
GitHub Advanced SecurityEnterprise-grade code securityhttps://github.com/security/advanced-security
Copilot for businessEnterprise-grade AI featureshttps://github.com/features/copilot/copilot-business
Premium SupportEnterprise-grade 24/7 supporthttps://github.com/enterprise/premium-support
Documentationhttps://docs.github.com/en
Resource centerhttps://github.com/resources
Bloghttps://github.blog/
Events & webinarshttps://github.com/resources/events
Community Forumhttps://github.com/orgs/community/discussions
Customer Storieshttps://github.com/customer-stories
Integrationshttps://github.com/marketplace
Customer supporthttps://help.github.com/
Traininghttps://learn.github.com/skills
GitHub Statushttps://www.githubstatus.com/
Abouthttps://github.com/about
Partnershttps://github.com/partners
Changeloghttps://github.blog/changelog/
GitHub UniverseThe event for developers, by developers — talks, workshops, and what’s next for GitHub.https://githubuniverse.com/
Pricinghttps://github.com/pricing
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fissues%2F160050
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fvoltron%2Fissues_fragments%2Fissue_layout&source=header-repo&source_repo=python%2Fcpython
Reloadhttps://github.com/python/cpython/issues/160050
Reloadhttps://github.com/python/cpython/issues/160050
Reloadhttps://github.com/python/cpython/issues/160050
pythonhttps://github.com/python
cpythonhttps://github.com/python/cpython
Codehttps://github.com/python/cpython
Issues5k+ (5k+)https://github.com/python/cpython/issues
Pull requests2.4k (2.4k)https://github.com/python/cpython/pulls
Actionshttps://github.com/python/cpython/actions
Projectshttps://github.com/python/cpython/projects
Security and qualityhttps://github.com/python/cpython/security
Insightshttps://github.com/python/cpython/insights
https://github.com/python/cpython
New issuehttps://github.com/login?return_to=https://github.com/python/cpython/issues/160050
New issuehttps://github.com/login?return_to=https://github.com/python/cpython/issues/160050
#160443https://github.com/python/cpython/pull/160443
modulo for huge integers has the wrong complexityhttps://github.com/python/cpython/issues/160050#top
#160443https://github.com/python/cpython/pull/160443
easyhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22easy%22
interpreter-core(Objects, Python, Grammar, and Parser dirs)https://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22interpreter-core%22
performancePerformance or resource usagehttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22performance%22
type-bugAn unexpected behavior, bug, or errorhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22type-bug%22
https://github.com/cfbolz
cfbolzhttps://github.com/cfbolz
on Oct 21, 2026https://github.com/python/cpython/issues/160050#issue-5964649223
#96673https://github.com/python/cpython/pull/96673
gh-160050: Use asymptotically faster divmod in l_mod for large integers #160443https://github.com/python/cpython/pull/160443
cfbolzhttps://github.com/cfbolz
performancePerformance or resource usagehttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22performance%22
on Oct 21, 2026https://github.com/python/cpython/issues/160050#event-33867470223
picnixzhttps://github.com/picnixz
docsDocumentation in the Doc dirhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22docs%22
on Oct 21, 2026https://github.com/python/cpython/issues/160050#event-33869732433
github-project-automationhttps://github.com/apps/github-project-automation
docs issueshttps://github.com/orgs/python/projects/52
on Oct 21, 2026https://github.com/python/cpython/issues/160050#event-33869736884
github-project-automationhttps://github.com/apps/github-project-automation
docs issueshttps://github.com/orgs/python/projects/52
on Oct 21, 2026https://github.com/python/cpython/issues/160050
picnixzhttps://github.com/picnixz
interpreter-core(Objects, Python, Grammar, and Parser dirs)https://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22interpreter-core%22
type-bugAn unexpected behavior, bug, or errorhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22type-bug%22
docsDocumentation in the Doc dirhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22docs%22
on Oct 21, 2026https://github.com/python/cpython/issues/160050#event-33869759828
https://github.com/lazerg
lazerghttps://github.com/lazerg
on Oct 21, 2026https://github.com/python/cpython/issues/160050#issuecomment-6322995017
https://github.com/cfbolz
cfbolzhttps://github.com/cfbolz
on Oct 21, 2026https://github.com/python/cpython/issues/160050#issuecomment-6324821207
https://github.com/skirpichev
skirpichevhttps://github.com/skirpichev
on Oct 22, 2026https://github.com/python/cpython/issues/160050#issuecomment-6330645536
skirpichevhttps://github.com/skirpichev
docs issueshttps://github.com/orgs/python/projects/52
on Oct 22, 2026https://github.com/python/cpython/issues/160050
skirpichevhttps://github.com/skirpichev
easyhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22easy%22
on Oct 22, 2026https://github.com/python/cpython/issues/160050#event-33909325862
emirplushttps://github.com/emirplus
on Oct 25, 2026https://github.com/python/cpython/issues/160050#event-34173480612
pythongh-160050: Add comment referencing l_divmod in l_modhttps://github.com/emirplus/cpython/commit/7faf1993dbe84debf62b29cd51de04bc6f7a4653
pythongh-160050https://github.com/python/cpython/issues/160050
7faf199https://github.com/emirplus/cpython/commit/7faf1993dbe84debf62b29cd51de04bc6f7a4653
emirplushttps://github.com/emirplus
on Nov 6, 2026https://github.com/python/cpython/issues/160050#event-35387298551
pythongh-160050: Update test_pylong_int_mod to meet digit threshold r…https://github.com/emirplus/cpython/commit/adaef851245da5e15220bad530889414476bae1e
pythongh-160050https://github.com/python/cpython/issues/160050
adaef85https://github.com/emirplus/cpython/commit/adaef851245da5e15220bad530889414476bae1e
StanFromIrelandhttps://github.com/StanFromIreland
on Nov 7, 2026https://github.com/python/cpython/issues/160050#event-35454864649
gh-160050: Use asymptotically faster divmod in `l_mod` for large inte…https://github.com/python/cpython/commit/63e7b1889beec3e67db0448ae055c5b68e7b64f3
gh-160050https://github.com/python/cpython/issues/160050
63e7b18https://github.com/python/cpython/commit/63e7b1889beec3e67db0448ae055c5b68e7b64f3
StanFromIrelandhttps://github.com/StanFromIreland
completedhttps://github.com/python/cpython/issues?q=is%3Aissue%20state%3Aclosed%20archived%3Afalse%20reason%3Acompleted
#160443https://github.com/python/cpython/pull/160443
on Nov 7, 2026https://github.com/python/cpython/issues/160050#event-35454865033
Sign up for freehttps://github.com/signup?return_to=https://github.com/python/cpython/issues/160050
Sign in to commenthttps://github.com/login?return_to=https://github.com/python/cpython/issues/160050
easyhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22easy%22
interpreter-core(Objects, Python, Grammar, and Parser dirs)https://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22interpreter-core%22
performancePerformance or resource usagehttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22performance%22
type-bugAn unexpected behavior, bug, or errorhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22type-bug%22
https://github.com
Termshttps://docs.github.com/site-policy/github-terms/github-terms-of-service
Privacyhttps://docs.github.com/site-policy/privacy-policies/github-privacy-statement
Securityhttps://github.com/security
Statushttps://www.githubstatus.com/
Communityhttps://github.community/
Docshttps://docs.github.com/
Contacthttps://support.github.com?tags=dotcom-footer

Viewport: width=device-width


URLs of crawlers that visited me.