Re: Faster bounded random integers

In theory, yes. You would just need to generate more bits of randomness to
have enough entropy.

There is a catch though. If you begin to need so much entropy that
generating that is far slower than divisions, then you should look at
another approach. The Lemire paper offers a reference to other approaches
more suited to these through less well known and mostly forgotten
algorithms from the 70s.
This particular paper is long (60 pages) and is not super applicable to my
needs, so I have not taken the time to dive in details yet.

In particular, you would need to have generated enough random bits to be
slower than the big int divisions you need to do. That is probably not
happening under any realistic integer range we would deal with on the BEAM
imho.

Thomas Depierre
Schedule a meeting with me <https://calendly.com/thomas-depierre/30min>


On Tue, 14 Sept 2021 at 02:29, Richard O'Keefe <[email protected]> wrote:

> 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 <[email protected]> wrote:
> >
> > 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
>