Picking A, C and M for Linear congruential generator
algorithm, javascript, math, number-theory, prng
Solution
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:
- For c and m to be relatively prime, c and m must have no common prime factors. So, pick any prime numbers other than 11, 47, 541, and 911, then multiply them together to choose your c.
- You'll need to choose a such that a-1 is divisible by all the prime factors of m, i.e., a = x*11*47*541*911 + 1 for any x of your choosing.
- Your m is not a multiple of 4, so you can ignore the third condition.
In summary:
- m = 485-1,
- c = any product of primes other than 11, 47, 541, and 911 (also, c must be less than m),
- a = x*11*47*541*911 + 1, for any nonnegative x of your choice (also, a must be less than m).
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.)
Problem
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: - 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 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.