Pseudorandom number generators

The formula

The linear congruential generator, the oldest workhorse:

x_{n+1} = (a·x_n + c) mod m

Reading: multiply the current state by a, add c, keep the remainder mod m. The whole generator is three constants and one seed; everything after that is arithmetic.

The Park–Miller "minimal standard," a concrete LCG worth knowing:

x_{n+1} = 16807·x_n mod (2³¹ − 1)

Reading: modulus 2,147,483,647 (a Mersenne prime), multiplier 16807, no additive term. Seed it with 1, crank it 10,000 times, and you get 1,043,618,065 — the published check value. If your implementation doesn't reproduce that, your implementation is wrong.

The linear feedback shift register, the hardware answer:

period = 2ⁿ − 1   (n-bit register, primitive feedback polynomial)
PRBS31:  x³¹ + x²⁸ + 1

Reading: shift the register, XOR the tapped bits back into the input. If the tap polynomial is primitive over GF(2), the register walks through every nonzero state exactly once before repeating — 2,147,483,647 bits for PRBS31.

Inverse transform sampling, which turns uniform noise into any distribution you need:

X = F⁻¹(U),   U uniform on (0,1)
exponential:  X = −ln(1 − U)/λ

Reading: push a uniform draw backwards through the target CDF and out comes a draw from that distribution ^[16]. This is the bridge between "generator makes uniform bits" and "my simulation needs exponential failure times."

Where you meet it

The BERT on your bench. Every bit-error-rate tester clocks a PRBS pattern — PRBS7 from the SerDes standards, PRBS15/23/31 per ITU-T O.150 ^[11]^[12] — through the link under test. PRBS31 at 10 Gb/s repeats every 0.21 seconds, long enough to look like live traffic to the receiver's clock recovery, short enough that the analyzer can synchronize and count errors.
Monte Carlo tolerance stacks and trajectory dispersions. Ten thousand runs of a 6-DOF sim, each drawing thousands of samples for wind, thrust misalignment, and sensor bias. The generator's period and dimensional uniformity are silent assumptions under every one of those dispersion ellipses in the review package.
Regression tests that have to replay. A seeded PRNG makes a "random" test deterministic. When the review board asks why run 47 tripped a limit, you re-run with seed 47 and get the identical trajectory. Log the seed with the data or the anomaly is unreproducible.
Built-in self-test and scrambling in your hardware. LFSRs generate test vectors and signatures inside ASICs, whiten data in SerDes links, and spread GPS signals. The same shift register math shows up whether you asked for it or not.

How it works

A PRNG is a finite-state machine: state, transition function, output function. Same seed, same sequence, every time — that determinism is a feature, not a bug, because it buys reproducibility. The costs are a finite period (the state must eventually revisit itself) and structure (the outputs are correlated in ways true noise never is). Engineering judgment is knowing when either one bites.

Period is the first spec. An LCG with modulus 2³¹ can't give you more than about 2×10⁹ draws before it repeats verbatim, and a big Monte Carlo campaign can burn through that in minutes. The Mersenne Twister (MT19937) fixed this with a 624-word state and a period of 2^19937 − 1 — a number with 6,002 decimal digits — plus uniform coverage in every dimension up to 623 ^[8]^[9]. That is why Python, MATLAB, and most scientific libraries adopted it as the default ^[8]^[15].

Structure is the second spec, and the more dangerous one because it hides. Successive LCG outputs, plotted as points in k dimensions, fall on a lattice of parallel hyperplanes. The infamous case is RANDU, IBM's 1960s generator (x_{n+1} = 65539·x_n mod 2³¹): every triple of consecutive outputs satisfies x_{k+2} = 6·x_{k+1} − 9·x_k (mod 2³¹) exactly, so all its 3-D points land on just 15 planes. Any simulation that consumed RANDU triples as 3-D coordinates was sampling 15 sheets of space and calling it a volume. A decade of published results inherited that flaw.

The mistakes that still happen on real programs:

Reseeding constantly. Seeding from the wall clock inside a loop replaces a tested generator with the statistics of your system timer. Seed once, then let it run.
Sequential seeds for parallel runs. Seeds 1, 2, 3, ... on 500 cluster nodes can produce overlapping or correlated streams in some generators. Use a generator with proper stream-splitting or jump-ahead.
Statistical generator in a security role. MT19937 is fully predictable after observing 624 outputs; its own authors say it is not cryptographically secure as-is ^[8]^[9]. Keys, nonces, and challenge vectors need a CSPRNG — NIST SP 800-90A DRBGs ^[14] or the OS entropy source — not the simulation generator.
Trusting "it looks random." Quality is measured, not eyeballed: NIST SP 800-22 and similar batteries exist because human inspection catches none of the failures that matter ^[13].
Forgetting the all-zeros state. An LFSR seeded with zero stays at zero forever. Hardware self-test logic guards against it; hand-rolled FPGA code frequently doesn't.

History

The field starts with a confession. John von Neumann needed random numbers for neutron-transport calculations on ENIAC and proposed the middle-square method — square the number, keep the middle digits — at a 1949 symposium, published by the National Bureau of Standards in 1951 ^[3]^[4]. He knew exactly what he was selling: "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin" ^[3]^[4]. He liked middle-square anyway, on the engineering grounds that when it failed, it failed detectably.

That same year, at Harvard's Second Symposium on Large-Scale Digital Calculating Machinery, Derrick Lehmer proposed the multiplicative congruential generator, published in the proceedings in 1951 ^[1]^[2] — the a·x mod m recurrence that, with an additive constant, became the LCG found in nearly every language runtime since. Solid theory didn't prevent bad constants: IBM's RANDU shipped in the 1960s and George Marsaglia's 1968 paper "Random Numbers Fall Mainly in the Planes" showed its outputs, and those of every multiplicative generator to some degree, confined to lattice planes ^[5]^[6]. Steve Park and Keith Miller answered the resulting mess in 1988 with a "minimal standard" generator and check values, arguing that good ones are hard to find and portable correct ones harder ^[1]^[7].

Meanwhile the hardware lineage ran on shift registers: maximal-length LFSR sequences, formalized in the 1960s, became the pseudorandom binary sequences standardized for telecom testing in ITU-T O.150 ^[10]^[11]^[12]. The software lineage culminated in 1997 when Makoto Matsumoto and Takuji Nishimura built the Mersenne Twister, published in ACM TOMACS in 1998 ^[8]^[9] — the generator that made "ran out of period" a solved problem for Monte Carlo work, while its predictability kept the statistical-versus-cryptographic distinction alive ^[8]^[13].

Related tools

/tools/snr-enob — PRBS-driven BER and converter testing live next door to SNR and effective bits
/tools/thermal-noise-floor — the true randomness your pseudorandom test pattern is standing in for
/tools/link-budget — the margin calculation your PRBS31 BER test exists to verify
/tools/adc-resolution — dither and quantization testing lean on the same uniform-noise machinery

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →