this is what has always baffled me about statistics...having the opportunity to make things exact, with little effort, it is dismissed just because the small error
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.
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.
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.
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.
I don’t think the “random uint” api is too low-level, or lacks a pit of success - I think you’re just reaching for the wrong api. The problem of “make n bits pseudo randomly set to either 1 or 0” is nearby to your problem of “choose an element according to a probability distribution”, but it’s a separate problem in its own right.
I think actually this is an argument for language designers to include a “std.choice” in their standard library that consumes random bytes and correctly performs common ergonomic operations like “get one element at random from this collection”.
(If your standard library tries to make a distinction between “regular random number generators” and “cryptographically secured random number generators”, I think this distinction between “generate random bits” and “make probabilistic choices” is about equally important.)
The modulo operator is not a uniform mapping; use Lemire's nearly divisionless method or simple rejection sampling and move on.
I got lost when OP talked about using 10 integers to choose from 3 choices. I think I figured out what was missing in the explanation.
random_u64() Mod 3 does indeed have a single bucket that is oversized. This overweights one option by about 5×10^-20.
rand() Itself has only 32767 possible values, so it's also common for a bucket to be overweighted depending on the number of buckets.
> rand() Itself has only 32767 possible values
For MingW maybe (due to MSVCRT). I think most libraries such as glibc have RAND_MAX at 2147483647.
Makes you wonder at what point overweighting by about 5×10^-20 is something you'd want to care about.
this is what has always baffled me about statistics...having the opportunity to make things exact, with little effort, it is dismissed just because the small error
Picking that from the noise would take quite a while.
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.
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.
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.
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.
I don’t think the “random uint” api is too low-level, or lacks a pit of success - I think you’re just reaching for the wrong api. The problem of “make n bits pseudo randomly set to either 1 or 0” is nearby to your problem of “choose an element according to a probability distribution”, but it’s a separate problem in its own right.
I think actually this is an argument for language designers to include a “std.choice” in their standard library that consumes random bytes and correctly performs common ergonomic operations like “get one element at random from this collection”.
(If your standard library tries to make a distinction between “regular random number generators” and “cryptographically secured random number generators”, I think this distinction between “generate random bits” and “make probabilistic choices” is about equally important.)
so it's not really *random* that isn't random enough - it's the operator% that worsens it
Randomness test > Specific tests for randomness: https://en.wikipedia.org/wiki/Randomness_test
Which NIST SP-800-22 implementation instead of the now-archived paranoid_crypto randomness tests?
paranoid_crypto/docs/randomness_tests.md : https://github.com/google/paranoid_crypto/blob/main/docs/ran...
/? NIST SP-800-22 Rust: https://www.google.com/search?q=NIST+SP-800-22+rust&oq=NIST+...
Sometimes it's possible to whiten random to make it uniform random or normal random;
Whitening transformation: https://en.wikipedia.org/wiki/Whitening_transformation