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

**and then modulate it by**

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

*m*Or as formula: X

_{n+1}= (aX

_{n}+ c) mod m.

Where X

_{0}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.

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

### External Links

Linear congruential generator - Wikipedia article.

z-rand.c - Unangband source code, uses an LCG.