## How to generate a random integer number from within a range

### Question

This is a follow on from a previously posted question:

How to generate a random number in C?

I wish to be able to generate a random number from within a particular range, such as 1 to 6 to mimic the sides of a die.

How would I go about doing this?

### Accepted Answer

All the answers so far are mathematically wrong. Returning `rand() % N`

does not uniformly give a number in the range `[0, N)`

unless `N`

divides the length of the interval into which `rand()`

returns (i.e. is a power of 2). Furthermore, one has no idea whether the moduli of `rand()`

are independent: it's possible that they go `0, 1, 2, ...`

, which is uniform but not very random. The only assumption it seems reasonable to make is that `rand()`

puts out a Poisson distribution: any two nonoverlapping subintervals of the same size are equally likely and independent. For a finite set of values, this implies a uniform distribution and also ensures that the values of `rand()`

are nicely scattered.

This means that the only correct way of changing the range of `rand()`

is to divide it into boxes; for example, if `RAND_MAX == 11`

and you want a range of `1..6`

, you should assign `{0,1}`

to 1, `{2,3}`

to 2, and so on. These are disjoint, equally-sized intervals and thus are uniformly and independently distributed.

The suggestion to use floating-point division is mathematically plausible but suffers from rounding issues in principle. Perhaps `double`

is high-enough precision to make it work; perhaps not. I don't know and I don't want to have to figure it out; in any case, the answer is system-dependent.

The correct way is to use integer arithmetic. That is, you want something like the following:

```
#include <stdlib.h> // For random(), RAND_MAX
// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
unsigned long
// max <= RAND_MAX < ULONG_MAX, so this is okay.
num_bins = (unsigned long) max + 1,
num_rand = (unsigned long) RAND_MAX + 1,
bin_size = num_rand / num_bins,
defect = num_rand % num_bins;
long x;
do {
x = random();
}
// This is carefully written not to overflow
while (num_rand - defect <= (unsigned long)x);
// Truncated division is intentional
return x/bin_size;
}
```

The loop is necessary to get a perfectly uniform distribution. For example, if you are given random numbers from 0 to 2 and you want only ones from 0 to 1, you just keep pulling until you don't get a 2; it's not hard to check that this gives 0 or 1 with equal probability. This method is also described in the link that nos gave in their answer, though coded differently. I'm using `random()`

rather than `rand()`

as it has a better distribution (as noted by the man page for `rand()`

).

If you want to get random values outside the default range `[0, RAND_MAX]`

, then you have to do something tricky. Perhaps the most expedient is to define a function `random_extended()`

that pulls `n`

bits (using `random_at_most()`

) and returns in `[0, 2**n)`

, and then apply `random_at_most()`

with `random_extended()`

in place of `random()`

(and `2**n - 1`

in place of `RAND_MAX`

) to pull a random value less than `2**n`

, assuming you have a numerical type that can hold such a value. Finally, of course, you can get values in `[min, max]`

using `min + random_at_most(max - min)`

, including negative values.

Read more... Read less...

Following on from @Ryan Reich's answer, I thought I'd offer my cleaned up version. The first bounds check isn't required given the second bounds check, and I've made it iterative rather than recursive. It returns values in the range [min, max], where `max >= min`

and `1+max-min < RAND_MAX`

.

```
unsigned int rand_interval(unsigned int min, unsigned int max)
{
int r;
const unsigned int range = 1 + max - min;
const unsigned int buckets = RAND_MAX / range;
const unsigned int limit = buckets * range;
/* Create equal size buckets all in a row, then fire randomly towards
* the buckets until you land in one of them. All buckets are equally
* likely. If you land off the end of the line of buckets, try again. */
do
{
r = rand();
} while (r >= limit);
return min + (r / buckets);
}
```

Here is a formula if you know the max and min values of a range, and you want to generate numbers inclusive in between the range:

```
r = (rand() % (max + 1 - min)) + min
```

Wouldn't you just do:

```
srand(time(NULL));
int r = ( rand() % 6 ) + 1;
```

`%`

is the modulus operator. Essentially it will just divide by 6 and return the remainder... from 0 - 5

For those who understand the bias problem but can't stand the unpredictable run-time of rejection-based methods, this series produces a progressively less biased random integer in the `[0, n-1]`

interval:

```
r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...
```

It does so by synthesising a high-precision fixed-point random number of `i * log_2(RAND_MAX + 1)`

bits (where `i`

is the number of iterations) and performing a long multiplication by `n`

.

When the number of bits is sufficiently large compared to `n`

, the bias becomes immeasurably small.

It does not matter if `RAND_MAX + 1`

is less than `n`

(as in this question), or if it is not a power of two, but care must be taken to avoid integer overflow if `RAND_MAX * n`

is large.