Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 38 · Random Numbers

Linear Congruential Generators

Build a linear congruential random number generator from scratch, see its period and its flaws, and learn why modern generators replaced it.

The simplest useful pseudorandom generator is a linear congruential generator (LCG). It fits in one line of code, it was the standard for decades, and building one teaches you exactly what "pseudorandom" means. It also shows why you should not use a hand-made generator for serious work.

The recurrence

An LCG keeps one integer X, the state. To get the next state it computes

Text
X(next) = (a × X + c) mod m

where a is the multiplier, c the increment and m the modulus. The notation mod m means "the remainder after dividing by m", so every state lies in 0, 1, …, m−1. The seed is the starting X. To get a uniform number in [0, 1), output X / m.

A tiny example with m = 16, a = 5, c = 3 and seed X = 7:

Step Calculation State
0 seed 7
1 (5×7 + 3) mod 16 = 38 mod 16 6
2 (5×6 + 3) mod 16 = 33 mod 16 1
3 (5×1 + 3) mod 16 = 8 mod 16 8

Code it

Python A tiny LCG and its output

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see the sequence cycle through 16 different values and then repeat. With m = 16 there are only 16 possible states, so the period (the length before repeating) cannot exceed 16. For tiny moduli the output is obviously not random.

The period

The Hull–Dobell theorem says an LCG with c ≠ 0 reaches the full period m exactly when:

  1. c and m share no common factor other than 1,
  2. a − 1 is divisible by every prime factor of m,
  3. a − 1 is divisible by 4 if m is divisible by 4.

The example above (a = 5, c = 3, m = 16) satisfies all three: 3 and 16 are coprime, a − 1 = 4 is divisible by 2 (the only prime factor of 16) and by 4. So the period is the full 16.

Python Measure the period

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing bad constants shortens the period dramatically. Good constants such as the ones used by classic C libraries (a = 1103515245, c = 12345, m = 2³¹) give a period of 2³¹, about two billion values. That sounds large, but it is small by today's standards, and other flaws appear first.

Flaws: patterns in the output

LCGs have a notorious defect: if you plot consecutive pairs (Uₙ, Uₙ₊₁) as points in the unit square, they fall on a small number of straight lines instead of filling the square. In three dimensions they lie on a modest number of planes. This lattice structure can bias simulations that use several consecutive numbers at once, such as a 3D random point.

The low-order bits are worse: with a modulus that is a power of 2, the lowest bit of an LCG alternates 0, 1, 0, 1, … so "even or odd?" is perfectly predictable.

Python See the lines in pairs of outputs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The points group onto parallel lines. A good generator would fill the square evenly. (This plot uses a short, weak generator on purpose to make the effect visible. Real LCGs with big moduli show the same lattice at a finer scale.)

The low bit problem

Python Predictable low bits

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The lowest bit alternates strictly. This is why library implementations that use an LCG discard the low bits and return only high ones.

What replaced LCGs?

Modern generators have far larger states and better statistical quality:

  • Mersenne Twister (MT19937), Python's random module: period 2¹⁹⁹³⁷−1.
  • PCG64, NumPy's default default_rng(): small, fast, passes strict statistical test batteries.
  • Xoshiro / Philox / SFC families: used when speed, jumping ahead or parallel streams matter.

The lesson on NumPy generators explains how to use them. For now remember: LCGs teach the idea, but you should use a vetted library in real simulations.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In the LCG X(next) = (a·X + c) mod m, what is the largest possible period?

    The state is a remainder mod m, so there are only m possible states; the period cannot exceed m.
  2. 2. For m = 16, a = 5, c = 3 and seed 7, what is the first generated state?

    (5 × 7 + 3) mod 16 = 38 mod 16 = 6.
  3. 3. What visible flaw do LCGs show when consecutive pairs of outputs are plotted?

    LCG outputs have lattice structure: tuples of consecutive values lie on parallel lines or planes.
  4. 4. Why are the low bits of an LCG with a power-of-two modulus a problem?

    The lowest bit has period 2 and the next bit period 4, and so on, so low bits are far from random.

Summary

  • An LCG updates its state with X = (a·X + c) mod m and outputs X/m.
  • The period is at most m; the Hull–Dobell conditions decide when the full period is reached.
  • Outputs lie on a lattice, and low bits are highly regular, so LCGs are poor for serious simulation.
  • Modern generators (Mersenne Twister, PCG64) have huge states and better statistical quality.
  • Never write your own generator for real work; use a trusted library.

Next: Testing Randomness