Created
April 18, 2019 20:24
-
-
Save simonlindholm/5a7decb29486805d5f3cf15fcddc1db9 to your computer and use it in GitHub Desktop.
Fast modulo/division; C++ port of https://github.com/ejmahler/strength_reduce/blob/master/src/lib.rs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| typedef unsigned long long ull; | |
| struct FastMod { | |
| ull multiplier; | |
| ull divisor; | |
| int shift_size; | |
| int mode = 0; | |
| FastMod(ull divisor) : divisor(divisor) { | |
| shift_size = 64 - __builtin_clzll(divisor) - 1; | |
| if (divisor & (divisor - 1)) { | |
| auto a = (__uint128_t)1 << (shift_size + 64); | |
| multiplier = (ull)(a / divisor); | |
| ull remainder = (ull)(a % divisor); | |
| ull error = divisor - remainder; | |
| mode = 1 + (error >= (1ULL << shift_size)); | |
| multiplier *= mode; | |
| multiplier++; | |
| } | |
| else { | |
| multiplier = 1; | |
| mode = 0; | |
| } | |
| } | |
| pair<ull, ull> div_rem(ull numerator) { | |
| ull quotient; | |
| if (mode == 0) { | |
| quotient = numerator >> shift_size; | |
| } | |
| else { | |
| ull up = (ull)((__uint128_t(numerator) * multiplier) >> 64); | |
| if (mode == 1) { | |
| quotient = up >> shift_size; | |
| } | |
| else { | |
| quotient = (up + (numerator - up) / 2) >> shift_size; | |
| } | |
| } | |
| ull remainder = numerator - quotient * divisor; | |
| return {quotient, remainder}; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment