news.ycombinator.com
Untitled
The thing you actually want is rejection sampling: https://en.wikipedia.org/wiki/Rejection_sampling. That Wiki page makes it sound very complicated but for this purpose our implementation can be laughably simple which has the advantage that you know why it works and can maintain it properly with confidence. Get suitably large inputs, for example if you're trying to pick integers between 2 and 11 inclusive, a nibble (half a byte) would be fine. Now, is the random input in the range you wanted? If so, you've got your answer. If not, throw this random input away and get more. Too many programmers act as though random numbers were a precious resource.
Comments
4 preview comments · loading full threadLog in to h4cker, then connect Hacker News to publish comments.
Random 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.
That's what for example the Doom "fizzle" effect does. You can pick taps for an LFSR that generates a sequence 2^n -1 steps long - it can never contain zero and all numbers from 1 to 2^n -1 will appear exactly once. So to "fizzle" a 320x200 resolution you generate a 17-bit LFSR, the lower 8 bits being the Y co-ordinate and the upper 9 being the X co-ordinate (or the other way round, don't you let me tell you how to live). Some of those are off the screen! Ignore them. The "off the edges" fizzles that you don't draw are so randomly dispersed that you never actually notice them. Then eventually the LFSR loops back to the seed value, and you know you've done them all.
Wow that page really gets lost in the weeds of multiple dimensions. And yeah it's just rerolling when your random number is out of range. If you want it as simple as possible, always generate from 0-n, and grab barely enough random bits for n to fit.
Rejection sampling has a chance to never terminate. I think it can be perfectly fair to treat it like a last resort.