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.
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

Note that with the constants used in this example the generator has a period of 8.

External Links

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

Previous: Iterated Function System

Next: L-System