Algorithm for getting an integer in a range

[bakkot]

[Edit: Transferred from the Seeded Random proposal.]

The output of the underlying PRNG is generally some number of bytes. Converting that to an integer in an arbitrary range can be done in a few different ways, and we'll need to pick one. This blog post gives a good general overview but predates swiftlang/swift#39143 ("Canon's method"), which claims to be optimal. That PR has a good description as well as many useful pingbacks; note that it comes in both biased and unbiased variants (where the bias, at least if your underlying PRNG gives you 64-bit integers, affects at most 1/2**64 samples).

The links in this PR to Rust's rand crate point to more discussion/tradeoffs (especially rust-random/rand#1196) and the code provides both biased and unbiased implementations of Canon's method. Their benchmarks claim the unbiased implementation is often 10-20% slower but microbenchmarks are hard.

Go recently updated to use Lemire's method but there is only very brief discussion of Canon's method so I'm not totally sure why they went with the slightly older approach.

[lemire]

The following might be relevant:

"Faster random integer generation with batching," in Daniel Lemire's blog, August 17, 2024, https://lemire.me/blog/2024/08/17/faster-random-integer-generation-with-batching/.