CoreSource checked

Linear Congruential Generator

Generates pseudorandom numbers with a simple linear recurrence.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Beginner
Family: Pseudorandom Number Generator
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 9
Code example: Ready
Visualization: Ready
Aliases: LCG

Overview

An LCG repeatedly multiplies the current state, adds a constant, and reduces by a modulus.

Core Concepts

random drawstate transitionpseudorandom number generatorrandom sourcedistribution shapesample selection

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(1)

When to Use

Use Linear Congruential Generator when you need to update a numeric state.
Use it for simple simulations with inputs like seed.
Use it when randomization, representative samples, or controlled variation are needed.
Use it when the Pseudorandom Number Generator tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when reproducibility, distribution quality, or sample independence cannot be verified.
Avoid it when the required output is not pseudorandom number sequence.

What It Does

Updates a numeric state
Produces deterministic pseudorandom values from a seed

Use Cases

Simple simulations
Teaching pseudorandomness
Lightweight deterministic tests

Inputs

Seed
Multiplier
Increment
Modulus

Outputs

Pseudorandom number sequence

Key Formulas (1)

State update

x_next = (a · x + c) mod m

x_next = (a * x + c) mod m

Advances the generator's integer state.

Pseudocode

1.Start with a seed state
2.Multiply by the multiplier
3.Add the increment
4.Take the result modulo the modulus
5.Return the new state as the next value

Canonical Example

Input: items = [A, B, C, D], seed = 7
Output: sampled or randomized result
Explanation: Linear Congruential Generator: The algorithm uses controlled randomness to choose or generate values.

Implementation Notes

Keep the input contract explicit: Seed; Multiplier; Increment; Modulus.
Separate the random number source from the algorithm so tests can use fixed seeds.
Separate the random source from the sampler so tests can use fixed seeds and distribution checks.

Common Pitfalls

Poor parameter choices create short cycles or visible patterns.
Using biased random choices or forgetting to store the seed for reproducible runs.
Handle empty, invalid, and boundary inputs before trusting pseudorandom number sequence.
Uncontrolled seeds or biased random choices can make results irreproducible or statistically misleading.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show a single state value cycling through generated outputs.

Step 1 of 5: Start with a seed state

linear-random-state

Notes

Linear Congruential Generator operates in O(1) time and O(1) space within the Pseudorandom Number Generator family. Key governing relation: x_next = (a * x + c) mod m. Often compared with Mersenne Twister and Box-Muller Transform.