11.11 Getting a Random Integer in a Range

11.11.1 Problem

You want to choose a number in a particular range, with each possible value equally likely. For example, you may be simulating dice rolling and do not want any number to be more likely to come up than any other. You want all numbers in the range to be possible values, including both endpoints. That is, if you ask for a number between 1 and 6, you'd like both 1 and 6 to be as likely as 2, 3, 4, or 5.

11.11.2 Solution

There are multiple ways to handle this problem. The most common is the least correct, and that is to simply reduce a random integer (see Recipe 11.10) modulo the size of the range and add to the minimum possible value. This can lead to slight biases in your random numbers, which can sometimes lead to practical attacks, because it means that some outputs are more likely than others.

We discuss more exact solutions in the next section.

11.11.3 Discussion

In all cases, you will start with a function that gives you a random unsigned number that can be any value, such as spc_rand_uint( ) from Recipe 11.10. You will mold numbers returned from this function into numbers in a specific range.

If you need random numbers in a particular range, the general approach is to get a number between zero and one less than the number of values in the range, then add the result to the smallest possible value in the range.

Ideally, when picking a random number in a range, you would like every possible value to be equally likely. However, if you map from an arbitrary unsigned integer into a range, where the range does not divide evenly into the number of possible integers, you are going to run into problems.

Suppose you want to create a random number in a range using an unsigned 8-bit type. When you get a random unsigned 8-bit value, it can take on 256 possible values, from 0 to 255. If you are asking for a number between 0 and 9 inclusive, you could simply take a random value and reduce it modulo 10.

The problem is that the numbers 0 through 5 are more likely values than are 6 through 9. 26 possible values will reduce to each number between 0 and 5, but only 25 values will yield 6 through 9.

In this example, the best way to solve this problem is to discard any random numbers that fall in the range 250-255. In such a case, simply get another random value and try again. We took this approach in implementing the function spc_rand_range( ). The result will be a number greater than or equal to a minimum value and less than or equal to maximum value.

Some programmers may expect this function to exclude the upper limit as a possible value; however, we implement this function in such a way that it is not excluded.

#include <limits.h> #include <stdlib.h>     int spc_rand_range(int min, int max) {   unsigned int rado;   int          range = max - min + 1;       if (max < min) abort(  ); /* Do your own error handling if appropriate.*/   do {     rado = spc_rand_uint(  );   } while (rado > UINT_MAX - (UINT_MAX % range));   return min + (rado % range); }

You might worry about a situation where performance suffers because this code has to retry too many times. The worst case for this solution is when the size of the range is UINT_MAX / 2 + 1. Even in such a case, you would not expect to call spc_rand_uint( ) very many times. The average number of times it would be called here would be slightly less than two. While the worst-case performance is theoretically unbounded, the chances of calling spc_rand_uint( ) more than a dozen times are essentially zero. Therefore, this technique will not have a significant performance impact for most applications.

If you are okay with some items being slightly more likely than others, there are two different things you can do, both of which are fairly easy. First, you can perform a modulo operation and an addition to get the integer in the right range, and just not worry about the fact that some values are more likely than others:

#include <stdlib.h>     int spc_rand_range(int min, int max) {   if (max < min) abort(  );   return min + (spc_rand_uint(  ) % (max - min + 1)); }

Of course, this solution clumps together all the values that are more likely to be chosen, which is somewhat undesirable. As an alternative, you can spread them out by using division and rounding down, instead of a simple modulus:

#include <limits.h>     int spc_rand_range(int min, int max) {   if (max < min) abort(  );   return min + (int)((double)spc_rand_uint(  ) *                       (max - min + 1) / (double)UINT_MAX) % (max - min); }

Note the modulo operation in this solution. That is to prevent getting a value that is out of range in the very rare occasion that spc_rand_uint( ) returns UINT_MAX.

11.11.4 See Also

Recipe 11.10