c++ - random over a range, is number bias present for new rand() version?

Question

reading from various other SO questions, when using rand() % N you may happen to modify the bias for the pseudo number you get, so you usually have to introduce some range handling.

However in all cases rand() was always mentioned, and not the newer random() or arcrandom4() functions or the native C++11 methods. What happens when you run these routines over a set? Do you get a bias like rand()?

Thanks.

Answer 1

The following answer does not go into as much detail as Eric Lippert's blog post on the same topic. Also, this question and its answers deal with the same topic.

Most of the bias that comes from doing rand() % N isn't from the rand() part - it's from the % N part.

Let's consider a 'good' implementation of rand() that generates all numbers from 0 to 100 (picked for simplicity) with equal probability - a uniform distribution. Next let's say that we want to use this implementation of rand() to generate random numbers between 0 and 80, so we do rand() % 80. Let's break down the possibilities of what could happen next:

1. rand() generates a number from 0 to 79. Any number from 0 to 79 % 80 stays the same number
2. rand() generates a number from 80 to 100. Any number from 80 to 100 % 80 gets converted to 0 to 20

This means that there are two ways to end up with a number from 0 and 20 but only one way to end up with a number from 21 to 79. Getting a number from 0 to 20 is more likely than getting a number from 21 to 79. This is usually not a desirable property.

Any value of N that divides evenly into the max value of rand() won't have this problem because there will be an equal number of ways to generate any value. Furthermore the bias is much smaller for small values of N than it is for values of N closer to the max value of rand().

So, what about functions other than rand()? If they return values from some fixed range and you do a mod operation, they will suffer from the same bias. If you're calling a random function that takes a range as arguments, then you don't need to do the mod operation. The function will probably handle any biases internally.