Skip to content
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

Correct C++ floor division for integers #1496

Merged
merged 5 commits into from Jan 8, 2024
Merged

Conversation

mstimberg
Copy link
Member

This fixes #1495. As mentioned in the issue, the problem is that we use floor(1.0*x/y) to calculate floor division with Python semantics in C++. By default, we have unsafe math optimizations enabled, which leads to this not always being correct (e.g. 98/98 would be rounded down to 0). I think this is due to replacing the division by multiplication with an approximated reciprocal, or something along these lines. Switching off unsafe optimizations would be an option, but it would slow down code in other places.
In this PR, I instead create function specializations for integer arguments, which then use a rather complex calculation to get the value:

q = a / b;
r = a - q*b;
q -= ((r != 0) & ((r ^ b) < 0));  // result

This is the implementation used by Cython (cdivision: false, obviously), and it should cover all corner cases. I didn't benchmark this, but it is probably quite a bit slower than the previous solution. This could bring up #993 on the table (the issue is about Cython, but the same is now relevant for C++), but on the other hand all use cases I can think of for floor division and modulo operations are initializations and run_regularly operations, nothing that is time-critical. As a data point, all usages of // in our examples are for initializations like x = i // columns.

@mstimberg mstimberg merged commit c5fe583 into master Jan 8, 2024
50 checks passed
@mstimberg mstimberg deleted the floor_div_integers branch January 8, 2024 13:37
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.

Floor division of integer values sometimes incorrect on C++ standalone
1 participant