alt Hacker NewsRandom numbers aren't precious, but they do take time to generate. Rejection sampling adds a branch and it can matter how often it's taken. In my property-testing framework, generating a large, random array of numbers more efficiently improved performance.
Replies
deathanatos • today at 3:38 AM
If your RNG outputs a u64 (a getrandom() call can do this, or even a simple RNG like xoshiro), a random int in TFA's range of [0, 10) has a very small (6 in 2⁶⁴ chance, or 3.2e-17%, might as well be 0) chance of needing to redraw.
Obviously, wider ranges will (possibly) reject more often, but unless the range is huge, rejection should be a very cold branch.
➕ show 2 replies
Rejection is unavoidable if you want a uniform distribution for a number of choices that is not a power of two.
Nonetheless, the rejection can be done either before or after the multiplication or division that does most of the job for passing from the input range to the output range.
The place where rejection is done can be chosen to minimize the amount of values that are rejected, making thus unlikely that the branch is taken, so it will be correctly predicted most of the time.
For maximum speed, it is preferable to use multiplication instead of division, i.e. the input is seen as a fraction less than 1 and after multiplication only the integer part is retained. Taking care to use multiplication is normally more important than worrying that rejection may decrease the performance.