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.
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()
9 4 5 8 1 12 13 0 9 4
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.
- c and m must be relatively prime
- a - 1 must be divisible by all prime factors of m
- if m is a multiple of 4, a - 1 must be a multiple of 4