rossilor95/lcg-python

A simple implementation of the Linear Congruential Generator (LCG) algorithm in Python

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.