I have been trying to understand how using modulus can be dangerous and can introduce nasty but into the software.
Here is an illustration: https://gist.github.com/anon7238593-create/5719c2ac8824650abbac4592ceee9408
in the notebook we can see that we used modulus to generate another random variable range which seems correct. you try to generate few number and they looks random but are they? no. here for sake of simplicity I have choose random range of 0-255 which I then convert to 0-100 range. here the probability that 0 comes is greater than having 100 because 101 doesn’t evenly divide 255. there is a remainder of 53. which means the first 53 numbers are more likely to be chosen than the rest of the numbers which we can see in the graph.
you might be wondering why? it’s rather simple. there are exactly 3 numbers in 0-255 that maps to number let’s say 3 ( or any number less than or equal to 53 ). while there are only 2 numbers that maps to any number greater than 53. this affects their likeliness of being chosen.
which case this is fine?
only and only when the number of elements in bigger range is evenly divisible by the number of elements in smaller range.
eg, 0-2 ( 3 elements ) 255 % 3 = 0 0-4 ( 4 elements ) 256 % 4 = 0
in this case the likeliness of an element being chosen doesn’t change.
hope this was useful :)
Edit:
off by one correction. thanks to @eleijeep@piefed.social
You must log in or register to comment.
Never is a strong word. In cases where you don’t need strong cryptographic or statistical properties it’s totally fine. That’s 99% of cases.
Nobody is modding a single byte. You’re going to have a 32-bit PRNG at least. 32-bits mod 100 is easily random enough for almost every use.
I guess it’s a good thing to be aware of though.
If you use something like four bytes instead of one, your error drops dramatically… If you’re generating numbers from 0-100, You’d have ~50 “bad” cases (just imagine the remainder is the same) out of 4 billion instead of ~50 out of 256. Unless you’re running a casino or something (and even then…) it’s probably “fine enough” but of course you have to know about it!
that’s a great observation. the difference in size of the original evenly distributed random integer space and smaller integer space is important too. if the difference is big enough the smaller random integer space will be equally likely.
Unless you’re running a casino I wonder if a good CTF could be made making use of this. eg, having a casino software and task is to exploit it to have infinite money glitch or something.
Be careful of off-by-one errors!
only when the number of elements in bigger range is evenly divisible by the number of elements in smaller range. eg, 0-2 ( 3 elements ) 255 % 3 = 0 in this case the likeliness of an element being chosen doesn’t change.
In the range 0-255 there are 256 values, so you need to test 256 % n, which in your example 256 % 3 = 1, so this would give a very slightly uneven distribution.
As to your main point, you’re right, and I believe the standard procedure is to just roll the random variable again any time it falls outside the largest integer multiple of the desired output range.
The last point is a correct method if you’re accepting the theoretical risk that it could run forever. In case of an uniform distribution on the original range the probabilities converge to an uniform distribution on the smaller range. For non-uniform distributions you also get a distribution where the new probabilities are scaled sums of the original probabilities.
In reality you should probably introduce a maximum number of rerolls. In that case you have your issue again but you can easily calculate error estimates to choose a good tradeoff limit for your purposes.
The probability of going for
prepeats without hitting the lower end of the range is((N - M) / N) ^ pwhereNis the size of the input range andMis the size of the largest integer multiple of the output range, which falls exponentially towards zero aspincreases, so the chance of the process not terminating is zero.With OP’s example, with an input range of 256 and an output range of 202, this would mean the probability of making 10 unsuccessful attempts would be
(54/256) ^ 10 = 0.00000017or about 1 in 6 million. The probability of making 20 unsuccessful attempts would be 1 in 36 trillion, and so on.
Thank you for the correction! I wrote the post in hurry that’s why this mistake.
RNG is hard. I also do not like the modulo technique, it’s generally wrong.
Random bit floats are (symmetric) log-uniform distributed, which isn’t surprising if you know how they work, but also has implications when you want to generate random floats in a large range.
On that note, scaling a float between 0 and 1 to your target range introduces aliasing artifacts, so it’s best to generate the highest precision floats your machine can handle then downcast.
