Faster bounded random integers

[Richard O'Keefe]

I am grateful for these references.  Not having had time to read them yet,
I wonder if this applies equally well to large integers?

On Tue, 14 Sept 2021 at 12:28, Richard O'Keefe <raoknz@REDACTED> wrote:
>
> On Tue, 14 Sept 2021 at 03:51, Thomas Depierre
> <depierre.thomas@REDACTED> 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