Faster bounded random integers

[Thomas Depierre]

Generating an unbiased random integer in a range 0..N where N is not a
power of two requires rejection sampling.

`rand` uses the "Java" algorithm for this as far as i can tell (could not
find a better name).
https://github.com/erlang/otp/blob/master/lib/stdlib/src/rand.erl#L150

Daniel Lemire presents a good analysis of the current field in
https://arxiv.org/abs/1805.10941 and then propose a "near divisionless"
algorithm that should provide speedup. This could already provide
interesting results.

A few days ago, the Swift team came up with an algorithm that:
- never divides
- avoids rejection sampling entirely
- achieves a theoretically optimal bound on the amount of randomness
consumed to generate a sample
- delivers actual performance improvements for most real cases

https://github.com/apple/swift/pull/39143

Am I understanding this right ? As far as i can tell, our expert is Raimo
Niskanen.

The EEF would be interested in funding me trying to explore the potential
gains and possibly implement it for `rand`. Would this be of interest ? I
expect the maintenance to be relatively low, this is not a lot of SLOC

Thomas Depierre
Schedule a meeting with me <https://calendly.com/thomas-depierre/30min>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20210913/7fff18ef/attachment.htm>