Pseudo-Random Numbers Explained
In the 1960s, IBM shipped a random number generator called RANDU that became widely used in scientific computing. Its numbers passed simple tests and looked perfectly random. But take them three at a time and plot them as points in a cube, and something alarming appears: every point lies on one of just 15 flat planes.
Research built on RANDU was quietly compromised for years. Understanding why requires looking inside the formulas that generate "random" numbers, which turn out to be surprisingly simple pieces of arithmetic.
Good Randomness Comes From a Formula With No Randomness at All
A pseudorandom number generator (PRNG) is a completely deterministic function. It takes a current state, computes an output, and updates the state. No coin flips, no noise.
What makes it useful is that the output looks statistically random, with no simple patterns, even though every number is fully determined by the starting seed.
The Linear Congruential Generator
The oldest widely used PRNG, proposed by Derrick Henry Lehmer in 1949 and later generalized, is the linear congruential generator (LCG):
Xₙ₊₁ = (a × Xₙ + c) mod m
- m is the modulus
- a is the multiplier
- c is the increment
- X₀ is the seed
A Tiny Example
Let m = 16, a = 5, c = 3, and seed X₀ = 7:
7 → 6 → 1 → 8 → 11 → 10 → 5 → 12 → 15 → 14 → 9 → 0 → 3 → 2 → 13 → 4 → 7 …
It visits all 16 values before repeating. That's the maximum possible period for m = 16. Real generators use huge moduli like 2³² or 2⁶⁴. The arithmetic is modular arithmetic.
When Does an LCG Get the Full Period?
The Hull–Dobell theorem (1962) says an LCG with c ≠ 0 has full period m if and only if:
- c and m share no common factor
- a − 1 is divisible by every prime factor of m
- a − 1 is divisible by 4 if m is divisible by 4
Our example passes: gcd(3, 16) = 1, and a − 1 = 4 is divisible by 2 and by 4. Check common factors with the GCF calculator.
The example implementation of rand() in the C standard uses a = 1103515245, c = 12345, and keeps results modulo 2³¹.
An Insider Reference: "Random Numbers Fall Mainly in the Planes"
In 1968, mathematician George Marsaglia published a paper with that memorable title. He proved that for any LCG, if you plot consecutive outputs as points in n dimensions, they fall on a limited number of parallel hyperplanes.
RANDU was an extreme case. It used a = 65,539 and m = 2³¹, with c = 0. Since 65,539 = 2¹⁶ + 3, a little algebra shows:
Xₙ₊₂ = 6Xₙ₊₁ − 9Xₙ (mod 2³¹)
Every third value is a fixed combination of the previous two, which forces all 3D points onto 15 planes. Donald Knuth later described RANDU as "really horrible." Simulations that relied on it in three or more dimensions were affected.
The Mersenne Twister
In 1997, Makoto Matsumoto and Takuji Nishimura published the Mersenne Twister. Its period is:
2¹⁹⁹³⁷ − 1
That's a Mersenne prime with 6,002 digits. The generator keeps a state of 624 32-bit numbers and mixes them with bit shifts and XOR operations. It produces numbers that are well distributed in up to 623 dimensions.
It became the default in Python, R, Ruby, MATLAB and many other tools. It's excellent for simulations and games, but it's not secure: after observing 624 outputs, an attacker can reconstruct its entire state and predict every future value. Read more in Mersenne Primes and the Search for Huge Numbers.
Modern Generators
- Xorshift (George Marsaglia, 2003): uses only XOR and bit shifts, extremely fast
- PCG (Melissa O'Neill, 2014): a small LCG core with a clever output permutation that hides its patterns
- Cryptographically secure PRNGs (CSPRNGs): based on ciphers such as ChaCha20 or AES, designed so that observing outputs reveals nothing about future ones
Use a regular PRNG for simulations and games; use a CSPRNG for passwords, tokens and keys.
From Raw Bits to Useful Numbers
A Range: Beware Modulo Bias
To get a number from 1 to 6, rand() % 6 + 1 seems natural. But if the generator's range isn't a multiple of 6, some results are slightly more likely. That's modulo bias. Good libraries use rejection sampling: discard values from the incomplete final block and draw again.
A Bell Curve: Box–Muller
To turn uniform random numbers into normally distributed ones, the Box–Muller transform (George Box and Mervin Muller, 1958) takes two uniform numbers U₁ and U₂:
Z = √(−2 ln U₁) × cos(2πU₂)
The result follows a standard normal distribution. Check its probabilities with the standard normal table.
Two Concepts Worth Knowing
Period
A PRNG's period is the number of outputs before the sequence repeats. Since the state is finite, every PRNG eventually repeats. A good one has a period far longer than any program could use.
Equidistribution
A generator is equidistributed in k dimensions if every combination of k consecutive outputs appears equally often over its period. It's a stronger requirement than just producing each single value equally often, and it's exactly where RANDU failed.
Quick Answer: What Is a Pseudo-Random Number?
A pseudo-random number is produced by a deterministic algorithm that generates random-looking sequences from a starting seed. A classic example is the linear congruential generator Xₙ₊₁ = (aXₙ + c) mod m. The same seed always produces the same sequence, so secure applications need cryptographically secure generators.
Try Them Yourself
- Random Number Generator: generate numbers and test them yourself
- GCF Calculator: check Hull–Dobell conditions
- Number Theory Formulas: modular arithmetic behind LCGs
- Standard Normal Table: the target of the Box–Muller transform
- Binary to Hexadecimal Converter: inspect generator state in hex
- Random Numbers Aren't Really Random: true randomness and its sources
Run our tiny LCG (a = 5, c = 3, m = 16) with a different seed, then try a = 3. Does it still visit all 16 values? The Hull–Dobell theorem predicts the answer before you start.