Skip to content

WiP Optimize 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.

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

Draft
wants to merge 4 commits into
base: main
Choose a base branch
from

Conversation

sjrd
Copy link
Member

@sjrd sjrd commented Jun 4, 2025

TODO: Check the case where the divisor is >= 2^62.
TODO: Write down the proof.

@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 added 4 commits June 23, 2025 15:05
It turns out the computation we did in the non-negative case also
works for the negative case. The proof relies on elementary
properties of the two's complement representation.

I don't know how I never saw this before. To make things worse, it
seems that Kotlin and J2CL knew all along, and I never realized
when skimming through their implementations either.
Since conversions of signed longs to doubles is in fact no more
expensive than the unsigned longs, we can take shorter paths for
values that fit in the *signed* safe range.

This applies to the conversions to string (including in the
javalib) and to float.
TODO: Check the case where the divisor is >= 2^62.
TODO: Write down the proof.
Now that the worst case isn't so bad anymore, we remove the fast
paths for small values of the numerator.

It does make them slower. However, it also makes division more
predictable: the time is now dependent only on the divisor, which
should be more stable in most applications. It also reduces the
overall code size.
@sjrd sjrd force-pushed the opt-rt-long-divide branch from b500b8f to 442e307 Compare June 23, 2025 15:06
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

1 participant