Re: Faster bounded random integers

On Tue, 14 Sept 2021 at 03:51, Thomas Depierre
<[email protected]> wrote:
>
> 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