I am looking to implement a simple pseudorandom number generator (PRNG) that has a specified period and guaranteed no collisions for the duration of that period. After doing some research I came across the very famous LCG which is perfect. The problem is, I am having trouble understanding how to properly configure it. Here is my current implementation:
function LCG (state)
{
var a = ?;
var c = ?;
var m = ?;
return (a * state + c) % m;
}
It says that in order to have a full period for all seed values the following conditions must be met:
1 and 3 are simple to understand and test for. However what about 2, I don't quite understand what that means or how to check for it. And what about C, can it be zero? what if it's non-zero?
Overall I need to select A, C and M in such a way that I have a period of 48^5 - 1. M is equal to the period, I am not sure about A and C.
From Wikipedia:
Provided that c is nonzero, the LCG will have a full period for all seed values if and only if:
- c and m are relatively prime,
- a-1 is divisible by all prime factors of m,
- a-1 is a multiple of 4 if m is a multiple of 4.
You said you want a period of 485-1, so you must choose m≥485-1. Let's try choosing m=485-1 and see where that takes us. The conditions from the Wikipedia article prohibit you from choosing c=0 if you want the period to be m.
Note that 11, 47, 541, and 911 are the prime factors of 485-1, since they're all prime and 11*47*541*911 = 485-1.
Let's go through each of those conditions:
In summary:
Here's a smaller test case (in Python) using a period of 482-1 (which has prime factors 7 and 47):
def lcg(state):
x = 1
a = x*7*47 + 1
c = 100
m = 48**2 - 1
return (a * state + c) % m
expected_period = 48**2 - 1
seeds = [5]
for i in range(expected_period):
seeds.append(lcg(seeds[-1]))
print(len(set(seeds)) == expected_period)
It outputs True
, as it should. (If you have any trouble reading Python, let me know and I can translate it to JavaScript.)