Mathematics
Linear Congruential Generators and Pseudo-Random Numbers
Quick fact
A linear congruential generator can produce billions of numbers from just one starting value, yet the entire sequence repeats after at most m steps (its period).
Why this is interesting
Flip a coin thousands of times and you get a pattern — but a simple formula can mimic that randomness with a few arithmetic steps? How can a deterministic recipe appear so random?
Read the full explanation
Understanding Linear Congruential Generators and Pseudo-Random Numbers
A linear congruential generator (LCG) produces a sequence of integers that look random. The formula is: X{n+1} = (a Xn + c) mod m. You start with a seed value X0, then repeatedly multiply, add, and take the remainder when dividing by m. This wraps the numbers into a fixed range, say 0 to m-1. The parameters a, c, and m must be chosen carefully. If they are set well, the sequence appears scattered and unpredictable. For example, with a=7, c=0, m=11 and seed X0=3, you get 3, 10, 4, 6, 9, 8, 1, 7, 5, 2, back to 3. It cycles through every number 1 to 10 before repeating. This element of disguise is why they are called pseudo-random: they are generated by a uniform rule but behave like randomness.
A deeper explanation
The underlying mechanism of an LCG is modular arithmetic, which wraps numbers around after reaching a limit. The sequence is deterministic: if you know the seed and the parameters, you can predict every subsequent number. Yet for a good choice of parameters, the numbers appear spread out and lack obvious patterns. The period of the sequence is at most m, and with optimal parameters (like a-1 divisible by all prime factors of m, and c coprime to m) the period can be exactly m, meaning it cycles through all possible values. However, the quality of randomness is limited. LCGs show clear correlations in higher dimensions and tend to have poor statistical properties. For cryptography or serious simulations, more advanced generators like the Mersenne Twister are used. Still, LCGs are a valuable teaching tool and appear in many simple applications like game random events or procedural generation, where simplicity outweighs the need for perfect randomness.