LCG Period Length Calculator
Compute the period (cycle length) of a Linear Congruential Generator (LCG) defined by xn+1 = (a·xn + c) mod m. This tool checks full-period conditions (Hull–Dobell) for mixed LCGs and can attempt cycle detection for smaller moduli.
Calculator Inputs
How to Calculate the Period Length of an LCG (Linear Congruential Generator)
A Linear Congruential Generator (LCG) is one of the oldest and most widely taught families of pseudorandom number generators. It’s prized for its simplicity and speed: each new state is computed with a multiply, an add, and a modulus. But that simplicity comes with a non-negotiable reality: an LCG is not “random” in the mathematical sense, and its behavior is strongly constrained by number theory—especially its period.
The period length of an LCG is the number of generated states before the sequence repeats and begins cycling. Since an LCG has finitely many states (exactly m distinct residues modulo m), the sequence must eventually repeat. Once any state repeats, the generator enters a cycle forever. The central question is: how long is that cycle, and under what conditions is it as long as possible?
1) Define the LCG precisely
An LCG is typically defined by four integers: modulus m, multiplier a, increment c, and seed x₀. The recurrence is:
xn+1 = (a·xn + c) mod m
There are two common subtypes:
- Mixed (or affine) LCG: c ≠ 0. This form can achieve a full period of m under specific conditions.
- Multiplicative LCG: c = 0. The state 0 becomes absorbing, and the maximum possible cycle is typically bounded by properties of the multiplicative group modulo m.
2) What “period length” means in practice
The word “period” is sometimes used loosely. In a strict dynamical-systems sense, from a given seed x₀, the generated sequence has:
- a pre-period (also called the “tail”) of length μ, where states are unique and not yet in the cycle, and
- a cycle length of λ, where the sequence repeats every λ steps.
For many well-formed LCG parameter sets (especially full-period mixed LCGs), the tail length is μ = 0, meaning the generator starts in the cycle immediately, and the “period” is simply λ. When people say “the period of the LCG,” they almost always mean the cycle length for typical seeds—or, ideally, the maximum cycle length the parameter set can produce.
The Gold Standard for Mixed LCGs: Hull–Dobell Theorem
If c ≠ 0, there is a clean and powerful test for whether the generator has full period, meaning it cycles through all m residues before repeating (for any starting seed). This is given by the Hull–Dobell theorem.
| Condition | What to compute | Why it matters (intuition) |
|---|---|---|
| 1) c is relatively prime to m | Compute gcd(c, m) and require it equals 1 | If c shares a factor with m, the recurrence gets trapped in a subset of residues and cannot visit all states. |
| 2) a − 1 is divisible by every prime factor of m | Factor m and check (a − 1) mod p = 0 for each prime p | m | This ensures the map advances through residue classes in a way that aligns with the prime-power structure of the modulus. |
| 3) if 4 divides m, then 4 divides a − 1 | Check: if m mod 4 = 0, require (a − 1) mod 4 = 0 | A special constraint arising from powers of 2. Without it, the low-order bits repeat too quickly and the full cycle is impossible. |
If all three conditions hold, the mixed LCG has period length exactly m. This is the best-case scenario because it means the generator enumerates every possible state modulo m before repeating. Notably, for a full-period mixed LCG, the period is independent of the seed: every starting seed lies on the same single cycle.
If your LCG is mixed (c ≠ 0) and you can factor m, the Hull–Dobell theorem is usually the fastest way to compute the period length—because it can certify period = m without simulation.
When Full Period Isn’t Guaranteed: How to Compute the Period Length
If the parameter set fails Hull–Dobell (or you are using c = 0), the period length can be smaller—sometimes dramatically. In that case, you typically compute the period for a specific seed by detecting the cycle in the recurrence. Conceptually, the direct method is:
- Start from x₀.
- Iterate the recurrence, recording states.
- Stop when a state repeats; the cycle length is the distance between the first occurrence and the repeat.
The problem is that “recording states” can require memory proportional to the period, which is not feasible for large moduli. A better technique is a cycle-finding algorithm such as Floyd’s tortoise-and-hare, which uses constant memory and determines the tail length μ and cycle length λ. Even with constant memory, the runtime still scales with the cycle length—meaning you can’t realistically simulate a full-period generator with m = 2³² in a browser and expect an answer quickly. That’s why number-theory conditions matter.
Step-by-step: Floyd cycle detection for an LCG
- Define f(x) = (a·x + c) mod m.
- Initialize two pointers: t = f(x₀) and h = f(f(x₀)).
- Advance t by one step and h by two steps until they meet.
- Reset one pointer to x₀ and advance both by one step to find μ.
- From that meeting point, advance one pointer until it returns to the same state to measure λ.
The value λ is the period length for that seed. For well-chosen mixed LCG parameters, you often get μ = 0 and λ = m. For “accidentally bad” parameters, you can see short cycles (for example, λ = 2, 4, or 8) that make the generator useless for simulation or sampling.
Multiplicative LCGs (c = 0): Understanding Period via Modular Arithmetic
When c = 0, the recurrence becomes xn+1 = (a·xn) mod m. In this case, the period is governed by multiplicative structure:
- If the sequence ever hits 0, it stays at 0 forever (period 1 from that point).
- If gcd(a, m) ≠ 1, then multiplication by a collapses the space and can force short cycles.
- If m is prime and a is a primitive root mod m, then every nonzero seed cycles with period m − 1.
The “primitive root” condition can be tested by factoring m − 1 (when m is prime): write m − 1 = ∏ qᵢ^{eᵢ} and verify that for every prime factor qᵢ, a^{(m−1)/qᵢ} mod m ≠ 1. If all those checks pass, the order of a is m−1, which is the maximum.
Worked Examples: Parameter Choices and Period Outcomes
The following table illustrates how different parameter sets influence period length. Some can be certified by conditions (like Hull–Dobell), while others typically require cycle detection for a specific seed.
| Type | Parameters (m, a, c) | Key condition | Expected period behavior |
|---|---|---|---|
| Mixed | m=16, a=5, c=1 | Hull–Dobell satisfied | Full period: visits all 16 states (period = 16). |
| Mixed | m=16, a=3, c=2 | gcd(2,16)≠1 | Cannot be full period; sequence is trapped in even residues; short cycle likely. |
| Multiplicative | m=17, a=3, c=0 | m prime; test if a primitive root | If a is primitive root, any nonzero seed has period 16; otherwise a divisor of 16. |
| Multiplicative | m=2^k, c=0 | Power-of-two modulus | Period is limited; low bits cycle quickly; careful selection needed and still weaker in many contexts. |
Common Pitfalls When Calculating (and Interpreting) LCG Period
- Confusing “period of the generator” with “period for a seed.” A parameter set may have multiple cycles; your chosen seed may land in a short one.
- Assuming large m implies large period. Without satisfying the right conditions, increasing m does not prevent extremely short cycles.
- Ignoring factorization of m. For mixed LCGs, full-period certification depends on the prime factors of m. If you can’t factor m (or don’t try), you often end up doing slow simulation or making guesses.
- Overvaluing period as the only quality metric. A full-period LCG can still be statistically weak in higher dimensions (e.g., points lying on a small number of hyperplanes). Period is necessary, not sufficient.
Why the Period Matters (but Doesn’t Make It Cryptographically Secure)
A long period is essential for Monte Carlo simulations, shuffling, sampling, and general-purpose randomized algorithms. If your generator repeats too early, you will see repeating patterns, biased estimates, and brittle behavior under stress tests. However, LCGs are not suitable for cryptographic randomness: their linear structure makes them predictable from partial output, especially when parameters are known or can be inferred.
If you’re evaluating randomness quality beyond period, the U.S. National Institute of Standards and Technology provides widely cited guidance on statistical testing approaches (though not endorsing LCGs for crypto). For example, see NIST’s documentation around randomness testing at csrc.nist.gov (random bit generation documentation).
Practical Workflow: How to Compute Period Length Reliably
Here’s a robust workflow you can use when someone asks “how do I calculate the period length of an LCG?” in a real engineering setting:
- Step 1: Identify type. If c ≠ 0, prefer Hull–Dobell checks. If c = 0, think multiplicative order and group structure.
- Step 2: Factor what you can. Factor m (mixed) or m − 1 (prime multiplicative). Even partial factorization can reveal why a period is limited.
- Step 3: Certify full period when possible. For mixed LCGs, if Hull–Dobell holds, you’re done: period = m.
- Step 4: Otherwise, compute cycle length for representative seeds. Use Floyd cycle detection to get λ. If there are multiple cycles, test several seeds.
- Step 5: Validate empirically. Plot traces, check histograms, and run statistical tests if the generator will affect simulations. For academic perspectives on PRNGs and LCG limitations, university lecture notes can be helpful; for instance, Princeton COS 226 random numbers notes (cs.princeton.edu).
References and Further Reading
- NIST (U.S. government): Random Bit Generation documentation & resources (csrc.nist.gov)
- Princeton University (.edu): Random numbers and PRNG notes (cs.princeton.edu)
- UC Davis (.edu): Mathematical background reading (math.ucdavis.edu)