I wanted a pseudo-random number generator that didn't lean on math/rand something small enough to read in one sitting and understand completely. A linear congruential generator (LCG) is about as simple as PRNGs get, so that's what I built.
An LCG produces its next number from its previous one with a single recurrence:
state = (a * state + c) mod m
Three constants control everything: a is the multiplier, c is the increment, and m is the modulus. Pick good constants and you get a sequence that looks random and has a long period before it repeats. Pick bad ones and you get short cycles or visible patterns. glibc's rand() uses a = 1103515245, c = 12345, and m = 2^31 the same constants I used here, mostly so the output is comparable to something well-known.
Because m is a power of two (2^31), taking the modulus is the same as masking off the low 31 bits:
mask = 2147483647 // 2^31 - 1
state = (a*state + c) & mask
& is a single bitwise instruction, while % on most architectures involves an actual division. For an LCG that might get called in a tight loop, this is a small but free win and it's a standard trick specifically because m was chosen to be a power of two in the first place.
A well-known weakness of power-of-two LCGs is that the low bits have a short period and poor randomness the very lowest bit can alternate in an obvious pattern. The high bits are much better behaved. So instead of returning state directly, I shift right and mask down to 15 bits:
return (state >> 16) & 0x7FFF
This discards the low 16 bits entirely and keeps a 15-bit slice from the healthier upper range which also happens to match the [0, 32767] range of POSIX rand(), so the output is directly comparable to the C standard library version.
type LCG struct {
a int64
c int64
mask int64
state int64
}
func newLCG(seed int64) *LCG {
return &LCG{
a: 1103515245,
c: 12345,
mask: 2147483647,
state: seed,
}
}
func (l *LCG) rand_next() int64 {
l.state = (l.a * l.state + l.c) & l.mask
return (l.state >> 16) & 0x7FFF
}
func (l *LCG) rand_range(min, max int64) int64 {
if min > max {
min, max = max, min
}
r := l.rand_next()
return (r % (max - min + 1)) + min
}
A couple of small Go-specific notes:
newLCG, not new Go's built-in new() is a reserved allocation function, so shadowing it would work but reads badly and confuses anyone skimming the file.
rand_range swaps min and max if they're passed in backwards, so the function is forgiving of caller mistakes rather than silently returning garbage.
The seed is just the current time in milliseconds fine for non-cryptographic use like tests, games, or simulations, but worth saying plainly: this is not a cryptographically secure generator. The state is fully predictable once you know two consecutive outputs and the constants, which is true of every LCG. Don't use this for tokens, keys, or anything security-sensitive for that, Go's crypto/rand is the right tool.
seed := time.Now().UnixMilli()
rng := newLCG(seed)
for i := 0; i < 5; i++ {
fmt.Println(rng.rand_next())
}
for i := 0; i < 5; i++ {
fmt.Println(rng.rand_range(1, 10))
}
Each call to rand_next() mutates l.state and returns the next value in the sequence, so calling it repeatedly on the same *LCG walks forward through the generator exactly like a C program calling rand() in a loop would.
rand_range(1, 10) and confirm the buckets come out roughly even.
rand_next() on the same *LCG would race on l.state.