lobsters score: 5 · tags: programming
u64 r = random_u64(); // uniform chance over [0..UINT64_MAX] T chosen = choices[r % 10];we might think every item has a 1/10 chance of being chosen. It does not.
…technically. Though how likely are you to actually see the difference? The relative chances of picking
0..10are 1844674407370955162 for0..6and 1844674407370955161 for7..10. Suppose you instead panicked for the largest 6 possible results ofrandom_u64(), making the remaining distribution uniform. The chance of encountering that error is6/2^64 = 3*10^-19, which you’re realistically not going to hit. That’s getting to the point where you’re more likely to notice a cosmic ray bit flip than to encounter the distribution being off.
score 1 · canonical
In fairness this is such an easy mistake most rng libraries include random in range functions nowadays.
That said the only place this kind of bias matters is gambling (because gambling games are not designed around powers of two), every other environment where the bias matters are place cryptographic security properties are required in which case the APIs used are the bulk “fill a buffer” ones. Which you should be using - the majority of random() style functions are not guaranteed to be cryptographically secure and don’t necessarily guarantee that they even can produce every number in their output range - I recall there being a few where even internally to the rng they didn’t cover [0,2^maxbits)
score 1 · canonical
It would be more sensible to just resample in that case (this is just rejection sampling). This is also similar to “cycle walking” in format-preserving encryption.
score 1 · canonical
This is exactly what the linked python code is doing, right? Just retrying the random call if the sampled value is outside of the acceptable range (adjusted for the fact that Python generally makes random numbers only available between 0-1).
So for my simple coin flipping app, i have the choice between doing it right, and using up more of the randomness my computer has stored suring runtim, or doing it wrong, and by the end of human existence, the coin will have come up heads once too often. I think this isn’t something terribly problematic. Still an interesting read though.
Also, I don’t know that much about how the computer creates random numbers, but how certain can we be that the original random call actually is uniformely distributed to begin with?
score 1 · canonical
Ugh, getting back to properly distributed random from the FP representation is almost as annoying as generating them properly in the first place. I have a recollection that most approaches now only give you 27/53 bits of entropy due to the misery of dealing with over representation of more heavily fractional values. Essentially generate a random value between 1 and 2 (which is easy in a bitwise manner) and then subtract 1.
score 1 · canonical
Another reason for using an API like
random_range()orrandom_choice()is that they can be faster than naïvely using %(I wonder how much we are fussing over uniformity out of habit, because it used to matter back in the days of bad 16 bit RNGs.)
score 1 · canonical