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: Xn+1 = (aXn + c) mod m.
Where X0 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