README.md

Linear Congruential Generator (LCG) in Python

For quantitative applications such as numerical simulations, it is convenient to have full control over the Pseudo-Random Number Generator we choose to use. For this reason, I implemented my own version of the Linear Congruential Generator (LCG), a simple and reliable algorithm.

Brief Theoretical Background

An LCG is a method for generating real non-negative pseudo-random numbers from the uniform distribution on $(0, 1)$.

First, an LCG produces a sequence of non-negative integers called states according to the recurring relation

$$x_i = (a \cdot x_{i-1} + c) \ mod \ m \qquad with \ i = \{0, 1, ...\}$$

Where

• $m > 0$ is the modulus; mod m stands for "modulo m", which means you divide by m and take the remainder.
• $x_i = \{0, 1, ..., m - 1\}$ is the i-th state of the generator
• $x_0 = \{0, 1, ..., m - 1\}$ is a non-negative integer constant called seed. The seed is the initial state of the generator
• $a = \{0, 1, ..., m - 1\}$ is a non-negative integer constant called multiplier
• $c = \{0, 1, ..., m - 1\}$ is a non-negative integer constant called increment

The integer constants m, a, c and x_0 specify the generator.

For each state generated by the LCG, we can take

$$u_i = \frac{x_i}{m}$$

Where $u_i$ is a real pseudo-random number from the uniform distribution on $(0, 1)$.

About this Repo

This small project explores a simple implementation of the LCG as a Python generator. All the code is contained in the lcg.py file and is pretty straightforward.

A detailed list of good values for the LCG constants m and a can be found at:

L’ecuyer, Pierre. "Tables of linear congruential generators of different sizes and good lattice structure." Mathematics of Computation 68.225 (1999): 249-260.