Understanding Linear Congruential Generator
Introduction: Why Do We Need Random Numbers in Computers?
Computers are completely logical machines - they follow exact instructions and always produce the same output for the same input. But sometimes, we need computers to generate "random" numbers for many purposes:
Simulations: Testing how systems behave under different conditions
Games: Creating unpredictable gameplay
Operating Systems: Making scheduling decisions
Testing: Creating varied test cases for software
The problem is: how can a completely predictable machine create something unpredictable?
The answer is pseudo-random number generators - algorithms that create sequences of numbers that look random, even though they're actually generated by a mathematical formula. One of the oldest and most famous methods is called the Linear Congruential Generator (LCG).
What is a Linear Congruential Generator?
An LCG is one of the simplest ways to generate pseudo-random numbers. Despite being invented in the 1950s, it's still used today because of its simplicity and speed.
The Basic Formula
The entire generator is based on one simple mathematical equation:
X(n+1) = (a × X(n) + c) mod m
Let me break down what each part means:
X(n) - The current random number in our sequence X(n+1) - The next random number we want to generate a - The "multiplier" - a carefully chosen constant number c - The "increment" - another constant we add m - The "modulus" - determines the maximum value
mod - This means "remainder after division"
How Does It Work?
Think of it like a recipe:
Start with an initial number (called the "seed")
Multiply it by 'a'
Add 'c' to the result
Take the remainder when dividing by 'm'
That's your next random number!
Repeat using this new number
A Simple Example
Let's use small numbers to understand:
m = 10 (numbers from 0-9)
a = 3 (our multiplier)
c = 7 (our increment)
Seed = 1 (starting point)
Step 1: X₁ = (3 × 1 + 7) mod 10 = 10 mod 10 = 0 Step 2: X₂ = (3 × 0 + 7) mod 10 = 7 mod 10 = 7 Step 3: X₃ = (3 × 7 + 7) mod 10 = 28 mod 10 = 8 Step 4: X₄ = (3 × 8 + 7) mod 10 = 31 mod 10 = 1
Our sequence: 1 → 0 → 7 → 8 → 1 (and it repeats!)
The Critical Question: Choosing Good Parameters
The quality of an LCG depends entirely on choosing the right values for m, a, and c. Bad choices create terrible random numbers!
The Hull-Dobell Theorem: The Rules for Success
Mathematicians Hull and Dobell discovered the exact conditions needed for an LCG to achieve its maximum "period" (how long before it repeats).
To get the best period of length 'm', you need ALL three conditions:
Rule 1: c and m must be coprime
This means they share no common factors except 1.
Why? If they share factors, your sequence gets trapped in a small subset of numbers. For example, if both are even, you might only get even numbers or only odd numbers - that's not very random!
Rule 2: Every prime factor of m must divide (a-1)
This is more technical, but it ensures the multiplier works properly with the modulus structure.
Rule 3: If m is divisible by 4, then (a-1) must also be divisible by 4
This prevents the sequence from breaking into separate short cycles.
Two Common Approaches
Approach 1: Power-of-Two Modulus (m = 2³²)
Example from C Standard Library:
m = 2³² (4,294,967,296)
a = 1,103,515,245
c = 12,345
Advantages:
Super fast: The "mod m" operation happens automatically due to integer overflow
No extra calculations needed
Perfect for speed-critical applications
Major Disadvantage:
The lower bits are NOT random at all!
Bit 0 alternates: 0,1,0,1,0,1...
Bit 1 has period 4
Bit 2 has period 8
This means if you just use rand() % 2, you're getting a completely predictable pattern!
The C Standard Fix: The C standard library actually discards the lower bits and only returns the upper 15 bits:
return (next / 65536) % 32768; // RAND_MAX = 32767
Approach 2: Prime Modulus (m = 2³¹ - 1)
Example: Park-Miller Generator
m = 2,147,483,647 (which is 2³¹ - 1, a prime number)
a = 16,807
c = 0 (multiplicative generator)
Advantages:
Much better statistical quality
All bits have good randomness properties
Well-studied and proven to work
Disadvantage:
Requires actual division to compute "mod m"
Slower than power-of-two approach
Need special tricks to avoid overflow
The Real-World Problem: C3x vs C6x Processors
The documents you provided tell a fascinating story about how hardware architecture affects random number generation.
The TMS320C3x: Quality First
The C3x processor (1980s):
Designed for scientific calculations
Had strong floating-point hardware
Used for radar, sonar, precise simulations
Their rand() implementation:
Used Park-Miller: m = 2³¹-1, a = 16,807
Output: 31 bits of randomness
Could generate over 2 billion different values
Perfect for high-precision simulations
The TMS320C6x: Speed First
The C6x processor (1990s):
Designed for maximum throughput
VLIW architecture (Very Long Instruction Word)
Optimized for parallel execution
No hardware division unit!
Their rand() implementation:
Switched to: m = 2³², a = 1,103,515,245
But returns only 15 bits!
Only 32,768 different values
RAND_MAX = 32,767
The Catastrophic Consequence
Here's where it gets serious. Many simulations use the Box-Muller transform to convert uniform random numbers into Gaussian (bell curve) distributions:
Z = sqrt(-2 × ln(U))
Where U is a random number between 0 and 1.
The problem: To get large random values (far from average), you need U very close to 0.
C3x capability:
Smallest U = 1 / 2³¹ ≈ 0.0000000005
Can generate up to 6.55σ (sigma) deviations
C6x limitation:
Smallest U = 1 / 32,768 ≈ 0.00003
Can only generate up to 4.56σ deviations
Real impact: If you're simulating communication systems with low error rates (like 10⁻⁷ or one error in 10 million), the C6x generator will NEVER produce the required noise levels. Your simulation will show zero errors and give you completely wrong results!
Engineers migrating code from C3x to C6x saw "improved" performance - not because their system got better, but because their random number generator was broken!
L'Ecuyer's Tables: A Treasure Trove of Good Parameters
The second document provides tables of carefully tested LCG parameters for different modulus sizes.
What Makes a Good Generator?
L'Ecuyer used the spectral test - a way to measure how well random number pairs, triplets, etc., fill space uniformly.
The spectral test reveals: When you plot consecutive random numbers as coordinates (x, y), they don't fill the space randomly - they fall on parallel lines! This is called the "lattice structure."
Good generators have these lines very close together. Bad generators have large gaps where no random points ever appear.
Example Parameters from L'Ecuyer's Tables
For m = 2³¹ - 1 (our chosen modulus):
Best multipliers found:
a = 1,583,458,089 (best for M₈ metric)
a = 784,588,716 (best for M₃₂ metric)
a = 16,807 (the classic Park-Miller, still good!)
For m = 2³² with c odd:
a = 2,891,336,453, c = any odd number
Achieves full period of 2³²
My Implementation: The Design Choices
For this project, I implemented a Park-Miller style LCG with these parameters:
#define PM_A 16807u // Park–Miller multiplier
#define PM_M 2147483647u // 2³¹ - 1 (prime modulus)
c = 0 // Multiplicative generator
Why These Choices?
1. Modulus = 2³¹ - 1 (Prime)
Reasons:
It's a Mersenne prime with excellent mathematical properties
Avoids the low-bit correlation problems of 2³² modulus
Provides a very long period: 2,147,483,646 values
Well-studied for over 40 years
Suitable for OS-level simulations
Trade-off: Requires actual division, which is slower than power-of-two overflow. But for OS work, quality matters more than raw speed.
2. Multiplier = 16,807
Reasons:
This is 7⁵ (7 to the power of 5)
Extensively tested and proven to work well
Appears in academic literature everywhere
Produces full period with our modulus
Avoids experimental or untested values
3. Increment = 0 (Multiplicative)
Reasons:
With a prime modulus, we don't need c ≠ 0
Simplifies the formula: X(n+1) = (a × X(n)) mod m
One less operation to compute
Cleaner mathematical properties
4. Seed Handling
Critical rule: Seed must never be zero!
In a multiplicative LCG:
If X₀ = 0, then X₁ = (a × 0) mod m = 0
And X₂ = 0, X₃ = 0, forever...
My code checks this:
void lcg_srand(LCG* local_rng, uint32_t seed){
if (seed == 0) seed = 1; // Force non-zero
local_rng->state = seed;
}
Implementation Details
The Core Structure
typedef struct {
uint32_t state;
} LCG;
Simple - just holds the current state.
The Random Number Generator
static uint32_t lcg_rand_int(LCG* local_rng){
uint64_t product = (uint64_t)local_rng->state * PM_A;
local_rng->state = (uint32_t)(product % PM_M);
return local_rng->state;
}
Key points:
Use
uint64_tfor multiplication to avoid overflowThe product can be up to 2⁴⁴, which fits in 64 bits
Take mod 2³¹-1 to wrap around
Return the new state
The Seeding Function
int random(int range){
if (!seeded){
uint32_t new_seed = (uint32_t)time(NULL) ^ (uint32_t)clock();
lcg_srand(&global_rng, new_seed);
seeded = 1;
}
return lcg_rand_int(&global_rng) % (range + 1);
}
Features:
Automatic seeding on first call
Combines
time()andclock()using XOR for better uniquenessReturns value in range [0, range]
Maintains global state for convenience
Testing and Validation
What to Test
1. Period Check
Generate many values
Ensure no premature repetition
Verify full range coverage
2. Distribution Check
Values should spread evenly across [0, m-1]
No obvious patterns
Statistical tests (chi-square, etc.)
3. Seed Sensitivity
Different seeds produce different sequences
Similar seeds don't produce similar outputs
4. Edge Cases
Seed = 0 (should be handled)
Seed = m-1 (maximum value)
Many consecutive calls
Example Test Output
Request: 1 ... MISS
Request: 2 ... MISS
Request: 3 ... MISS
...
Request: 20 ... MISS
Request: 1 ... HIT
Request: 10 ... HIT
Request: 15 ... HIT
Request: 21 ... MISS (triggers random eviction)
🎲 Random Eviction! Victim Index: 7 (VPN: 8)
Request: 1 ... MISS (was evicted!)
This shows the random number generator working in a page replacement simulation.
Comparison Table: Different Approaches
| Feature | Power-of-2 (2³²) | Prime (2³¹-1) | Modern (Xorshift) |
| Speed | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| Quality | ⭐⭐ | ⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| Period | 2³² | 2³¹-1 | 2³²-1 |
| Low-bit quality | ❌ Poor | ✅ Good | ✅ Good |
| Implementation | Trivial | Moderate | Simple |
| Use case | Quick & dirty | Simulations | Modern default |
When NOT to Use LCGs
⚠️ WARNING: LCGs are NOT suitable for:
Cryptography - They're completely predictable!
Security tokens - Can be reverse-engineered
Gambling systems - Legally and ethically wrong
Password generation - Use cryptographic RNGs instead
For these, use:
/dev/urandomon LinuxCryptGenRandom()on Windowsstd::random_devicein C++Hardware RNGs (RDRAND instruction)
Modern Alternatives
Xorshift (Recommended for Non-Crypto Use)
uint32_t xorshift32(uint32_t state){
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
return state;
}
Advantages:
Extremely fast (just XOR and shifts)
Excellent statistical properties
Period: 2³²-1
No multiplication or division needed
PCG (Permuted Congruential Generator)
State-of-the-art (2014)
Combines LCG with permutation
Passes all statistical tests
Still very fast
Practical Tips
1. Always Initialize Your Seed
srand(time(NULL)); // Good for basic use
// Better:
srand(time(NULL) ^ clock() ^ getpid());
2. Don't Use Low Bits for Decisions
// ❌ BAD (with 2³² modulus):
if (rand() % 2) { ... }
// ✅ GOOD:
if ((rand() / 65536) % 2) { ... }
3. Scaling to a Range
// ❌ Biased:
value = rand() % max;
// ✅ Better:
value = (int)((double)rand() / RAND_MAX * max);
4. For Floating-Point [0,1)
double u = (double)rand() / ((double)RAND_MAX + 1.0);
Conclusion
The Linear Congruential Generator is a perfect example of how simple mathematics can solve complex problems - but also shows that the devil is in the details.
Key takeaways:
✅ LCGs are simple, fast, and good enough for simulations
✅ Parameter choice is critical - use proven values
✅ Understand the trade-offs: speed vs. quality
❌ Never use LCGs for security
⚠️ Be aware of low-bit problems with power-of-two moduli
📊 Test your generator for your specific use case
The story of C3x vs C6x shows that "faster" isn't always better - sometimes correctness matters more than speed. As a fresh CS graduate, understanding these trade-offs will make you a better engineer.
For modern projects: Consider using Xorshift or PCG instead of classical LCGs, unless you specifically need reproducibility with standard library implementations.
References
Park, S. K., & Miller, K. W. (1988). Random number generators: good ones are hard to find.
L'Ecuyer, P. (1999). Tables of linear congruential generators of different sizes and good lattice structure.
Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms.
Marsaglia, G. (1968). Random numbers fall mainly in the planes.
ISO/IEC 9899:1999 - C Standard Library specification
This document was created as part of an operating systems course project to implement and understand pseudo-random number generation in system-level programming.
