Generating pseudorandom numbers with C++ rand() and srand()

Picture this: You’re working on an exciting project that requires some randomness—maybe for a video game (where you need to spawn random enemies at random spots of the labyrinth of the map of the game), statistical analysis, or even cryptography (where you need to generate a random key). The ability to generate random numbers can be a crucial component to the success of your project. In this blog, we’ll explore the powerful rand() function - a powerful tool that can help you achieve pseudorandomness in various applications.

A pseudorandom integral number refers to a number that appears to be random but is actually generated through a deterministic algorithm. In computer programming, true randomness is often difficult to achieve, so pseudorandom number generators (PRNGs) are used to generate sequences of numbers that exhibit characteristics of randomness.

Using rand() function and its problem#

In C++, the rand() function is a powerful tool that generates a pseudorandom integer within the range of 0 to RAND_MAX, equivalent to the maximum value the int data type can hold (RAND_MAX is a constant defined in cstdlib which has the value 2147483647).

Let’s see how rand() works in practice. In the following three examples, we will call the rand() function five times to generate five random numbers:

Instruction: Run each of the three tabs above at least three times and observe the following:

1. In the rand_without_srand.cpp tab

Executing this code multiple times will result in the same sequence of numbers each time, which is not desirable for random number generation.

2. In the rand_with_fixed_srand.cpp tab

In this code, we set the seed (the argument) for the random number generator to 1 using srand(). This produces the same sequence of numbers every time the program is run unless the seed value is changed. To test this, change the seed value (to srand(2), srand(3), and so on) to see how the pattern of generated numbers changes.

3. In the code-tab rand_with_srand_time_0.cpp tab

We utilize srand() to set the seed value for the random number generator in this code. The seed value is set to the current time using time(0), producing a distinct sequence of numbers every time the program is run.

time(0) returns the current time in seconds since the epoch (January 1, 1970, 00:00:00 UTC), which is a large integer that increases every second. As a result, it is frequently utilized as a seed for random number generators to generate varied outcomes each time a program is executed.

Let’s now understand how these two functions, rand() and srand(), actually work and how time(0) helps in generating these pseudorandom numbers.

How the rand() functions works#

The rand() function in C++ generates a pseudorandom number by performing some arithmetic operations on the previously generated number or the seed value (if it’s the first call). The arithmetic operations used by rand() are typically based on a linear congruential generator (LCG), which is based on a simple mathematical formula that involves multiplying the previous number by a constant and adding another constant to it and then taking the result modulo some value. The formula can be written as:

$$\begin{equation} X_{n+1} = (a X_n + c) \space mod \space m \end{equation}$$

$Z_p$ refers to the set of integers modulo $p$, where $p$ is a prime number. This set consists of integers ranging from 0 to $p-1$. For example, $Z_7$ would consist of the integers $\{0, 1, 2, 3, 4, 5, 6\}$. In this set, addition and multiplication are performed modulo $p$. For instance, if we take the example of $Z_7$, then $4+5$ would be equal to $2$ in $Z_7$ as $(4+5) \space mod \space 7 = 2$, and $45$ would be equal to $6$ in $Z_7$, as $(45) \space mod \space 7 = 6$.

Another nice observation related to modular arithmetic is that if we are working in any $Z_p$, then the following expression is equivalent:

$$(a \times b) \space mod \space p \equiv ((a \space mod \space p) \times (b \space mod \space p)) \space mod \space p$$

For example, if we are working in modulus 13, then the following expression will be equivalent:

$$(20 \times 14)\space mod\space 13 \equiv ((20\space mod \space 13) \times (14)) \equiv (7 \times 1) \space mod \space 13 \equiv 7$$

In some implementations of rand(), a polynomial is used of a small degree $d$ with $d+1$ prime coefficients (preferably). This is because prime numbers have good properties for generating seemingly random sequences of numbers within a prime modular field, such as being relatively far apart from each other and having a low correlation with other numbers. The polynomial will look like the following:

$$\begin{equation} X_{n+1} = (a_1 X_n^d + a_2 X_n^{d-1} + ... + a_{d+1}) \space mod \space m \end{equation}$$

Using prime numbers in the LCG can help to produce a more uniform distribution of random numbers.

In this blog, we will stick to a polynomial-based implementation of random number generation. Let’s revisit polynomials:

Polynomial

A polynomial is a mathematical function of the following form:

$$\begin{equation} f(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0 \end{equation}$$

In this equation, $a_0, a_1, \ldots, a_n$ are the coefficients of the polynomial, $n$ is a non-negative integer that represents the degree of the polynomial (i.e., the highest power of $x$ in the expression), and $x$ is the independent variable.

Here’s an example of evaluating a polynomial at a particular value of the independent variable $x$:

Consider the polynomial:

$$\begin{equation} f(x) = 2x^3 + 3x^2 + 5x + 1 \end{equation}$$

To evaluate $f(x)$ at $x = 2$, we substitute $x = 2$ into the polynomial expression:

$$\begin{equation} f(2) = 2(2)^3 + 3(2)^2 + 5(2) + 1 = 16 + 12 + 10 + 1 = 39 \end{equation}$$

Therefore, $f(2) = 39$.

The rand() function is implemented using a polynomial function evaluator called evals(), which evaluates the polynomial at a given parameter. The rand() function also uses a global variable called seed. When rand() is called, it passes the current value of seed to evals(), takes the result modulo a large number, preferably a prime number (in our example, we will take 593 so that values do not blow out of the range), and then stores the result back in seed before returning it. Since seed is a global variable, subsequent calls to rand() will use this changed seed as an argument to evals() and generate the next number.

Look at the example implementation:

Instruction: Execute the program multiple times and observe the sequence.

Here is a visual representation of how a polynomial function may appear to generate a sequence modulo 11 (sequence will be numbers between $\{0,1,2,...,10\}$).

Did you observe that the number sequence remains the same every time the program is executed?

Let us see why that is the case.

Every time the program is executed, the seed is initialized to 0, and the first call forces the pattern to begin the evaluation of the polynomial at 0, and afterward, the pattern follows.

Ideally, we do not want the sequence to be repeated when we execute the program again. Ideally, it should always be random, or at least it should appear random.

One way to get around this issue is to change the seed value every time the program starts. That can be done by the srand() function. Here is its possible implementation:

What is the importance of generating a unique seed with every time the execution of the program?

Generating a unique seed with every execution of the program is important to ensure the production of different random number sequences. It allows for diverse and unpredictable outcomes, enabling applications such as simulations, cryptography, and games to have varied and non-repetitive behavior.

The Unix epoch is a reference point that is used as a standard in computer systems to measure and compare time. It represents the starting point of the Unix timekeeping system, which measures time as the number of seconds that have elapsed since January 1st, 1970, 00:00:00 UTC. This system provides a universal and consistent representation of time across different platforms and programming languages. The Unix epoch is particularly useful for computer systems as it provides a standard for measuring time unaffected by different time zones or daylight saving time adjustments. This allows for more accurate and reliable time comparisons across different systems and applications.

Remember#

In applications such as machine learning, random numbers are generated and used for experimentation. To reproduce the same sequence of random numbers, we save the seed value instead of the entire sequence. This is because the seed value uniquely determines the entire sequence for a single polynomial.

In modulo $p$, the generated sequence is expected to not repeat for a small sequence. However, it is known that the sequence will start repeating after $p$ numbers, and in some cases, it can even repeat earlier. Also, we actually want the number to be repeatable (given the effect that a previously generated number is equally likely to appear again as any other number in the $Z_p = \{0,1,2,3,...,p-1\}$.

So to solve this problem, rand() functions maintains two primes, $p_{small}$ and $p_{big}$, where $p_{small} \ll p_{big}$ (reads as $p_{small}$ is very very smaller than $p_{big}$). The value of the sequence is generated in the following fashion:

• The number $x$ is generated first in the set $Z_{p_{big}} = \{0,1,2,3,...,p_{big}-1\}$.
• $x$ is saved as the seed and shrunk in modulo of $p_{small}$ yielding one of the numbers in $Z_{p_{small}} = \{0,1,2,3,...,p_{small}-1\}$ and that is returned as a pseudorandom number.

Notice now that the shrunk value $x$ is repeatable in $Z_{p_{small}}$ although it will not be repeated $Z_{p_{big}}$, as there are multiple numbers in $Z_{p_{big}}$ which will map to one numbering $Z_{p_{small}}$.