Linear Congruential Generator

Description

The most common (and easiest to implement) Pseudo Random Number Generator is probably the Linear Congruential Generator.
The basic idea is to multiply the last number with a factor a, add a constant c and then modulate it by m. With the right constants, LCGs have a maximal period, that is, if you generate m numbers, the LCG will give you every number in the domain in a pseudo-random order, with no repetitions.
Or as formula: X_n+1 = (aX_n + c) mod m.
Where X₀ is the seed.

Code Example

Python example:

a = 3
c = 9
m = 16
xi = 0

def seed(x):
    global xi
    xi = x

def rng():
    global xi
    xi = (a*xi + c)%m
    return xi

for i in range(10):
    print rng()

Output:

9
4
5
8
1
12
13
0
9
4

Period

Note that with the constants used in the provided example, the generator has a period of 8. With a careful choice of constants, a linear congruential generator will have a full period (a period of m), IE, it will not repeat an output until it has covered every output in the domain. The constants must meet 3 requirements.

1. c and m must be relatively prime
2. a - 1 must be divisible by all prime factors of m
3. if m is a multiple of 4, a - 1 must be a multiple of 4

External Links

Linear congruential generator - Wikipedia article.
z-rand.c - Unangband source code, uses an LCG.

Previous: Linear Congruential Generator

Next: L-System