DataTerminology.comNEW
Also known as: LCG
A PRNG defined by xn+1 = (a·xn + c) mod m, simple but sensitive to parameter choices.
DESCRIPTION
Linear congruential generators (LCGs) are classic PRNGs using modular arithmetic with multiplier a, increment c, and modulus m. They are fast and easy to implement, but quality heavily depends on well-chosen parameters. Poor choices—like RANDU—create lattice structures and correlations, failing modern tests. Multiplicative variants (c=0) include the Lehmer generator. Today, LCGs mainly serve as pedagogical tools or components in more advanced designs, while modern generators outperform them in quality and period.
ALTERNATIVE DEFINITIONS
Wikipedia
A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation.
Defines the core recurrence relation and characterizes the algorithm class.
Java SE 8 API
An instance of this class is used to generate a stream of pseudorandom numbers; this class uses a 48-bit seed, which is modified using a linear congruential formula.
Links LCG to a widely deployed standard library implementation.
GNU C Library Manual
The random number generator used by rand is a linear congruential generator.
Notes the historical use of LCGs in C libraries.
RELATED TERMS
Pseudorandom Number Generator Lehmer Random Number Generator RANDU Seed Xorshift Modulus Multiplier Increment
COMPETING TERMS
Mersenne Twister Permuted Congruential Generator
RELATIONS
- Broader: Generator
KNOWLEDGE AREAS
Mathematics Data Science Software Engineering Testing & Validation
TARGET AUDIENCE
Data Scientist Software Developer Data Engineer
EXTERNAL SOURCES
- Wikipedia - Linear congruential generator
- GNU - rand and PRNG notes
- Park & Miller (1988) - Minimal standard LCG paper
- Oracle - JDK Random (LCG) details
TOP QUESTIONS
Why are Linear Congruential Generators still discussed?
They’re simple, fast, and illustrate key PRNG design concepts, despite known weaknesses. They remain in legacy systems and teaching materials.
Category: Relevancy
What causes the lattice structure in LCG outputs?
Linearity and modular arithmetic produce points on parallel hyperplanes, especially visible in higher-dimensional tuples.
Category: Concept
How do you choose good LCG parameters?
Follow theoretical results (Hull–Dobell conditions), use vetted parameter sets, and validate with rigorous tests.
Category: BestPractice
What replaced LCGs in most applications?
Mersenne Twister historically, and now PCG, xoshiro/xoroshiro, SplitMix64, and counter-based generators for better quality and parallelism.
Category: Alternatives
Is a Lehmer generator an LCG?
Yes, it’s the multiplicative case (c=0) with carefully chosen modulus and multiplier.
Category: Concept
Can LCGs be used in cryptography?
No; they’re predictable and structurally weak. Use CSPRNGs or DRBGs defined by standards.
Category: Risk
How long can an LCG’s period be?
Up to m when parameters satisfy full-period conditions, but quality over the period can still be poor.
Category: Concept
What is RANDU and why infamous?
RANDU is a notoriously bad LCG used historically; it exhibits severe correlations and poor statistical behavior.
Category: Example
How to parallelize LCG streams?
Use leapfrogging, block-splitting, or parameterization; verify independence with testing.
Category: BestPractice