Sequences of random (i.e., unpredictable) numbers
are used by many applications.
In particular, they are used to generate test data for programs.
Truly random numbers are very difficult to obtain
(see random.org);
so, we must be satisfied with
pseudorandom numbers,
generated by algorithms.
To simplify the language, we shall omit the pseudo
in what follows.
Table of contents:
The function rand from the stdlib library generates random integers. Each call to the function produces a random integer in the closed interval 0 .. RAND_MAX. The RAND_MAX macro is defined in the stdlib.h interface and is no larger than INT_MAX.
For applications that are not too demanding, we may assume that the numbers generated by rand are more or less uniformly distributed over the interval 0 .. RAND_MAX, i.e., that each number in the interval has approximately the same probability of being generated.
int throwdie (void) { int r = rand (); if (r < RAND_MAX/6) return 1; else if (r < 2 * RAND_MAX/6) return 2; else if (r < 3 * RAND_MAX/6) return 3; else if (r < 4 * RAND_MAX/6) return 4; else if (r < 5 * RAND_MAX/6) return 5; else return 6; }
int rolldie (void) { int r = rand (); if (r < RAND_MAX/6) return 1; else if (r < RAND_MAX/6 * 2) return 2; else if (r < RAND_MAX/6 * 3) return 3; else if (r < RAND_MAX/6 * 4) return 4; else if (r < RAND_MAX/6 * 5) return 5; else return 6; }
char *cointoss (void) { int r; r = rand () % 2; if (r == 1) return "head"; else return "tail"; }
How to obtain a random integer in the interval 0..N-1 for N ≤ RAND_MAX? The first ideia is to use the expression rand() % N (that produces the remainder of the division of rand() by N ). This ideia would be reasonable if rand did produce truly random numbers. But the last digits of a number produced by rand need not be random (they could all be odd, for example).
Eric Roberts wrote a small random library that tries to circumvent the difficulty and provide reasonably random integers in the interval low..high. Here is one of the functions in the library:
// The function randint returns a random integer
// between low and high, i.e., in the closed
// interval low..high. We assume that low <=
// high and that high - low <= RAND_MAX.
// (The code was copied from the library random
// by Eric Roberts.)
int randint (int low, int high)
{
double d;
d = (double) rand () / ((double) RAND_MAX + 1);
int k = d * (high - low + 1);
return low + k;
}
First, the function transforms the integer produced by rand into a real number d in the half-open interval [0,1). Next, it transforms d into an integer k in the interval 0 .. high-low. Finally, it transforms k into an integer in the interval low..high.
We may assume that the numbers produced by randint are distributed more or less uniformly in the interval low..high, especially if high − low is much smaller than RAND_MAX.
The function rand has an internal memory that stores the integer, say r, produced by the previous execution of the function. Each new execution of the function uses r to compute a new integer (and that integer becomes the new value of r).
Where does it all begin? The integer r that corresponds to the first call to rand is known as seed. Given the seed, the sequence of integers produced by rand is completely determined.
The programmer can specify the seed by means of the function srand from the stdlib library. The function receives the desired value of the seed (an unsigned int) as argument. If the programmer does not specify a seed, the system uses the value 0. The following function of Roberts' library uses the system clock to specify the seed:
#include <time.h>
// The function randomize initializes
// the random number generator to make
// the output of randint unpredictable.
void randomize (void)
{
srand (time (NULL));
}
A permutation (or shuffle) of an array is a rearrangement of the elements of the array (each element of the array may change position or stay put).
The following function does a random permutation of an array v[0..n-1]. If the elements of the array are pairwise distinct, all the n! permutations are equally likely.
// Does a random permutation of the elements // of the array v[0..n-1]. void randpermute (int v[], int n) { int r, k, t; for (k = n-1; k > 0; k--) { r = randint (0, k); // 0 <= r <= k t = v[k], v[k] = v[r], v[r] = t; } }
See the shuffling animation produced by Mike Bostock.