<div dir="ltr">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">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">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">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><div>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</div><div><br></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></div>