What is a pseudorandom number? How to use random numbers?

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.

The rand function

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.

Exercises 1

[Roberts] The following program promises to emulate the throw of a fair die. What is the flaw in the program?

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;
}

[Roberts] The following program promises to emulate the rolling of a fair die. What is the flaw in the program?

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;
}

[Roberts] Subtle. The following program promises to emulate the tossing of a fair coin. What is the flaw in the program?
```
char *cointoss (void) {
    int r;
    r = rand () % 2;
    if (r == 1) return "head";
    else return "tail";
}
```

Random integers

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:

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.

Exercises 2

In the code of randint, why not write (RAND_MAX+1) in place of ((double)RAND_MAX+1)? Why not write RAND_MAX instead of ((double)RAND_MAX+1)?
Analyse the code of randint to check that the integer randint (0, RAND_MAX) is equal to rand ().
Prove that the number k returned by randint is such that low ≤ k ≤ high. Prove that randint returns low when rand () returns 0. Prove that randint returns high when rand () returns RAND_MAX.
Use the function randint to emulate the rolling of a die.

Seed

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:

Exercises 3

Write and test a program to receive two positive integers n and s on the command line and then print the sequence of numbers produced by n calls to rand starting with seed s.
Write and test a program to receive positive integers n, l, h, and s on the command line and then print the sequence of numbers produced by n calls to randint with arguments l and h and seed s.

Random permutations

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.

Exercises 4

Write and test a program to receive positive integers m and n on the command line and then print m successive random permutations of the array v[0 .. n−1] defined by v[i] = i.
Write and test a program to receive positive integers m, n, v₀, … , v_n−1 on the command line and then print m successive random permutations of the sequence v₀, … , v_n−1.

Random numbers