In September 2021, Stephen Canon published an algorithm to derive random integers from a random bitstream, achieving maximal efficiency wrt bits consumed in the single-draw case.
This [Pull Request] introduces a novel algorithm that:
- never divides
- avoids rejection sampling entirely
- achieves a theoretically optimal bound on the amount of randomness consumed to generate a sample
He cites previous work that achieved unbiased output but failed to achieve optimality of entropy consumed in the single-draw case.
Not cited, Canon's algorithm appears to be identical to (i.e. an independent re-discovery of) the "fast dice roller" introduced by Jérémie Lumbroso in April 2013:
This article introduces an algorithm to draw random discrete uniform variables within a given range of size n from a source of random bits. The algorithm aims to be simple to implement and optimal [with] regards to the amount of random bits consumed …
My question is: was Lumbroso really the first person in history to publish this algorithm, or had someone beat him to the discovery, too?