Faster bounded random integers
Tue Sep 14 02:28:17 CEST 2021
On Tue, 14 Sept 2021 at 03:51, 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
> 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
More information about the erlang-questions