4 ms·
Dissecting Lemire’s nearly divisionless random
- deleted 6y ago[deleted]
- kwillets 6y agoOops, I started on an entry for this, and then went off with some new variants on the algo and forgot my original goal. But I did make it fairly readable: FixedPoint<uint32_t> x; do { x.setFraction(src()); x *= range; } while(isRejectedValue(x.fraction())); return x.floor(); Basically all the weird casts and things in Lemire are parts of 32.32 fixed point arithmetic; we stuff a random value into the .32 part to make a number in [0,1) and multiply. The rejection condition is a bit of modular arithmetic but not super hard. https://github.com/KWillets/range_generator/blob/59ffea502c4a76ad059ea7b06b29b9d00e0a3e26/include/range_generator.hpp#L49 https://github.com/KWillets/range_generator/blob/59ffea502c4... I added another method where it doesn't reject but extends right (variable-precision) until it's certain of the exact answer (ie that the floor() cannot change). I believe the Ryu printf algorithm does something similar to get the requested number of digits. It's unbiased but uses more random bits, which are expensive.