Random Number Generator and Linear Congruential Generator(LCG) using Python

Random number generated by Python are called pseudo random number. The pseudo random number generator (PRNG) algorithm by Python uses a starting point ( aka seed ) to determine the random number hence not truely random. But is good enough for any coding project. The algorithm used in Python PRNG is called Mersenne Twister. But this post we will talk about Linear Congruential Generator(LCG).

The random method in Python uses the current system time as a seed. Therefore no seeding is required. This does not apply to C++ as the default seed is 1, seeding is required if you want a different number everytime you run your C++ code.

If you need to get the same random number everytime you run your code, then its simple:

Import random
# the argument for seed can be any integer. 
random.seed (10)
# generate random int 1 to 101 inclusive
# yes, includes 101

When you need a different integer, everytime code is run:

import random

print (random.randint(1,101))

Linear Congruential Generator(LCG)

A few things about LCG:

  • Formula is Xn+1 = ((a*Xn) + c ) mod m.
  • It produces random integers from 0 to m-1 inclusive.
  • the seed, multiplier, increment and modulus will affect the output of the LCG.
  • the seed X0 >= 0 , the multiplier ‘a’ >= 0 , the increment ‘c’ >= 0 , the modulus ‘m’ > X0 , ‘a’ , ‘c’
  • Once any integer in the sequence gets repeated, a pattern or cycle will emerge. This is so because Xn+1 is dependent on Xn.
  • The number of possible values is m (0 included) hence the max cycle time is m and the max runs before the algo repeats is also m.
  • When c = 0, the random number generator is refer as multiplicative congruential method.

The LCG is one of the most common random integer generator. Here the seed is 2, multiplier is 3, increment is 1 and the modulus is 19.

import random

seedInt = 2
x = seedInt
a = 3
c = 1
m = 19
for i in range(1,11):
	LCG = ((a*x)+c) % m 
	#print (x)
	x = x +1

And the results of 10 random numbers by LCG:

To show the importance of choosing the right values for the 4 variables. Below, X0, ‘a’, ‘c’ = 7 and m = 10.

import random

seedInt = 7
x = seedInt
a = 7
c = 7
m = 10
print(seedInt, end=' ')
for i in range(1,11):
	LCG = ((a*x)+c) % m 
	print(LCG, end= ' ')
	x = LCG

The output result as below. The 10 integers do not seem very random and the pattern is quite obvious.