a linear-congruential generator
/ kon-GROO-en-shul /
Here is the oldest and simplest recipe for fake randomness, simple enough to write on a napkin: take the last number, multiply it by something, add something, and keep only the remainder after dividing by a big number. Repeat forever. The remainders bounce around the range so erratically that, at a glance, they look random. This one-line rule is the linear-congruential generator, the workhorse of early computing and still the default in many basic library functions.
The rule is x_{n+1} = (a * x_n + c) mod m, where m is the modulus, a the multiplier, and c the increment, all fixed integers; the output is u_n = x_n / m, a fraction in [0, 1). Everything hinges on choosing a, c, m well. The Hull-Dobell theorem says the period reaches the full m (every value 0..m-1 appearing once before repeating) exactly when c and m are coprime, a - 1 is divisible by every prime factor of m, and a - 1 is a multiple of 4 if m is. Even then the period is at most m, so a 32-bit LCG cycles after only about 4 billion numbers — short by modern standards.
The deeper flaw is structural and famous: if you take consecutive outputs in groups of d and plot them as points in d-dimensional space, an LCG's points do NOT fill the cube uniformly — they fall on a small number of parallel HYPERPLANES (Marsaglia's theorem: 'random numbers fall mainly in the planes'). This lattice correlation silently biases any simulation that looks at tuples of consecutive draws. The historical disaster RANDU (a = 65539, m = 2^31) packed all its triples onto just 15 planes and corrupted years of scientific results. LCGs are fine for casual, low-dimensional use and are fast and tiny, but for serious Monte Carlo work they have been retired in favour of generators like the Mersenne Twister.
A classic 'minimal standard' LCG uses a = 16807, c = 0, m = 2^31 - 1 = 2147483647 (a prime). From seed 1 it emits 16807, 282475249, 1622650073, ... and cycles through all 2^31 - 2 nonzero residues before repeating — about 2 billion values, then the whole stream recurs identically.
Multiply, add, take the remainder — and beware the hidden planes.
Never use the low-order bits of a power-of-two-modulus LCG as if they were random: those bits have tiny periods (the lowest bit may just alternate 0,1,0,1). And a 32-bit LCG's period is far too short for large simulations.