frand
frand copied to clipboard
Implement "nearly-divisionless" Uint64n
Uint64n
uses the same approach as Go's math/rand
: truncate the range [0, math.MaxUint64]
to the nearest multiple of n
, then resample until we get a value within the truncated range and take the modulus. This is fairly fast, and easy to understand, but there's a faster approach that requires no divisions in the common case (whereas the current approach requires at least two). Indeed, math/rand
adopted this approach for its Shuffle
API (other APIs can't be changed due to the compatibility promise).
For Hacktoberfest, I'm inviting anyone to implement Lemire's algorithm for the Uint64n
function. I expect that the speedup will be relatively small, but frand
is all about speed, so we might as well push it to the limit.