<div dir="ltr"><div>In theory, yes. You would just need to generate more bits of randomness to have enough entropy.</div><div><br></div><div>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.</div><div>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. <br></div><div><br></div><div>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.<br></div><div><br></div><div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div>Thomas Depierre</div><div><div> <a href="https://calendly.com/thomas-depierre/30min" target="_blank"> Schedule a meeting with me </a> </div></div></div></div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, 14 Sept 2021 at 02:29, Richard O'Keefe <<a href="mailto:raoknz@gmail.com">raoknz@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I am grateful for these references.  Not having had time to read them yet,<br>
I wonder if this applies equally well to large integers?<br>
<br>
On Tue, 14 Sept 2021 at 12:28, Richard O'Keefe <<a href="mailto:raoknz@gmail.com" target="_blank">raoknz@gmail.com</a>> wrote:<br>
><br>
> On Tue, 14 Sept 2021 at 03:51, Thomas Depierre<br>
> <<a href="mailto:depierre.thomas@gmail.com" target="_blank">depierre.thomas@gmail.com</a>> wrote:<br>
> ><br>
> > Generating an unbiased random integer in a range 0..N where N is not a power of two requires rejection sampling.<br>
> ><br>
> > `rand` uses the "Java" algorithm for this as far as i can tell (could not find a better name). <a href="https://github.com/erlang/otp/blob/master/lib/stdlib/src/rand.erl#L150" rel="noreferrer" target="_blank">https://github.com/erlang/otp/blob/master/lib/stdlib/src/rand.erl#L150</a><br>
> ><br>
> > Daniel Lemire presents a good analysis of the current field in <a href="https://arxiv.org/abs/1805.10941" rel="noreferrer" target="_blank">https://arxiv.org/abs/1805.10941</a> and then propose a "near divisionless" algorithm that should provide speedup. This could already provide interesting results.<br>
> ><br>
> > A few days ago, the Swift team came up with an algorithm that:<br>
> > - never divides<br>
> > - avoids rejection sampling entirely<br>
> > - achieves a theoretically optimal bound on the amount of randomness consumed to generate a sample<br>
> > - delivers actual performance improvements for most real cases<br>
> ><br>
> > <a href="https://github.com/apple/swift/pull/39143" rel="noreferrer" target="_blank">https://github.com/apple/swift/pull/39143</a><br>
> ><br>
> > Am I understanding this right ? As far as i can tell, our expert is Raimo Niskanen.<br>
> ><br>
> > 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<br>
> ><br>
> > Thomas Depierre<br>
> > Schedule a meeting with me<br>
</blockquote></div>