Faster bounded random integers

Thomas Depierre depierre.thomas@REDACTED
Mon Sep 13 17:50:44 CEST 2021

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

Daniel Lemire presents a good analysis of the current field in 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

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

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 <>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the erlang-questions mailing list