frand icon indicating copy to clipboard operation
frand copied to clipboard

Implement "nearly-divisionless" Uint64n

Open lukechampine opened this issue 4 years ago • 0 comments

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.

lukechampine avatar Oct 05 '20 18:10 lukechampine