Skip to content

Optimize the worst case of RuntimeLong division and remainder. #5190

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

Jump to bottom
Open
wants to merge 1 commit into
base: main
Choose a base branch
from
Open

Optimize the worst case of RuntimeLong division and remainder. #5190

wants to merge 1 commit into from
+404 −87

Conversation

sjrd
Copy link
Member

@sjrd sjrd commented Jun 4, 2025 •
edited
Loading

These changes make the worst-worst case (we reach unsignedDivModHelper and b is small, so we need all 11 iterations of the loop) as fast as the best-worst case (we also reach the method but b is large and we only need 1 iteration). The cases where b <= 2^21 even become faster.

@sjrd sjrd force-pushed the opt-rt-long-divide branch 2 times, most recently from 3883616 to b500b8f Compare June 13, 2025 18:33
@sjrd sjrd force-pushed the opt-rt-long-divide branch from b500b8f to 442e307 Compare June 23, 2025 15:06
@sjrd sjrd force-pushed the opt-rt-long-divide branch 3 times, most recently from 65fd9b0 to 1d9f4bd Compare July 22, 2025 11:06
@sjrd sjrd changed the title WiP Optimize RuntimeLong division and remainder. Optimize RuntimeLong division and remainder. Jul 22, 2025
@sjrd sjrd force-pushed the opt-rt-long-divide branch 2 times, most recently from 6aa0198 to 16de707 Compare July 22, 2025 12:20
@sjrd sjrd changed the title Optimize RuntimeLong division and remainder. Optimize the worst case of RuntimeLong division and remainder. Jul 22, 2025
@sjrd sjrd marked this pull request as ready for review July 22, 2025 12:25
@sjrd sjrd requested a review from gzm0 July 22, 2025 12:25
@sjrd
Copy link
Member Author

sjrd commented Jul 22, 2025

@gzm0 This is now ready for review. The code is straightforward, but the proof is hairy.

@sjrd sjrd force-pushed the opt-rt-long-divide branch 4 times, most recently from a4d73cc to 6423179 Compare July 26, 2025 13:10
@sjrd sjrd force-pushed the opt-rt-long-divide branch from 6423179 to e6fe198 Compare July 28, 2025 17:04
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@gzm0 gzm0 Awaiting requested review from gzm0

At least 1 approving review is required to merge this pull request.

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
1 participant
@sjrd