search

tc39 / proposal-seeded-random

Proposal for an options argument to be added to JS's Math.random() function, and some options to start it with.
MIT License
156 stars 6 forks source link

Algorithm for getting an integer in a range #23

Open bakkot opened 3 months ago

bakkot commented 3 months ago

This is only relevant if this proposal includes randInt, which depends on whether it advances before or after https://github.com/tc39-transfer/proposal-random-functions. But I figure this commentary might as well be here.

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 https://github.com/swiftlang/swift/pull/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 https://github.com/rust-random/rand/pull/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 commented 2 months ago

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/.