Pseudo-random number generators

In this section we will simply review some possible alternatives for pseudo-random number generators. These go from the simplest ``congruential'' or ``power residue'' algorithm to more sophisticated ones that can be found in the literature. We will limit ourselves to understand this simple example. We want to generate a sequence $\{r_i\}$ over an interval $[0,M-1]$. You multiply the previous random number $r_i$ by a constant $a$, add on another constant $c$, take the modulus by $M$, and then keep just the fractional part, the reminder, as the next rendom number $r_{i+1}$:

$$r_{i+1}=(ar_i+c)\mathrm{mod}{M}=\mathrm{remainder}\left(\frac{ar_i+c}{M}\right).$$

The value $r_1$ has to be supplied by the user, and it is called the ``seed'' of the sequence. The sequence will be uniquely pre-determined by the seed.

As an example, let us pick $c=1$,$a=4$,$M=9$ and $r_1=3$. We obtain the sequence:

$$r_1 = 3,$$ (257)

$$r_2 = (4\times 3+1)\mathrm{mod}{9}=4,$$ (258)

$$r_3 = (4\times 4+1)\mathrm{mod}{9}=8,$$ (259)

$$r_4 = (4\times 8+1)\mathrm{mod}{9}=6,$$ (260)

$$, 7, 2, 0, 1, 5, 3, ...$$ (261)

We get a sequence of length $M=9$ after which the entire sequence repeats. This means that the ``period'' of the sequence is $M-1$. If we want the numbers in the range $[0,1]$ we would divide these values by $M$. This algorithm is extremely simple and portable, and it's particularly suitable for simple applications. As we have seen, the longer the $M$, the longer the ``period'' of the sequence. Using large integer raises the problem of protability. Most processors use 32-bit representation for integers (some 64). This limits the largest possible integer that can be used. However, there are ways to work around this issue.

The C++ Standard Library provides a psuedo-random number generator. It provides a function to initialize the seed of the sequence:

srand(size_t seed); and the actual call to retrieve a new random number

rand();

The generator provides a sequence between 0 and RAND_MAX, which is a large integer that deppends on the implementation. A common way to generate independent sequences is to use the internal clock of the computer to generate a relatively random seed.

For more on random number generators read Knuth, Numerical Recipes.