Period of a Linear Congruential Random Number Generator

I'm trying to determine the period (or cycle) of a linear congruential RNG, assuming my modulus is fixed at 2^31. My problem is that sometimes I need to generate a very large number of random numbers before I can determine the period. Can anyone tell me if there's a more efficient way to determine the period because my computer has crashed on multiple occassions now as I get up into the billions.

clear

clc

a=69069; % Multiplier

b=69069; % Constant

m=2^31; % Modulus

n=2000;

x(1)=69069; % Seed value

for i=1:n

x(i+1) = mod((a*x(i))+b,m);

end

p=0; % Period

for i=1:n

if x(i+1)==x(1)

p=i;

break;

end

end

disp(p)

Answer 1

[David Goodmanson]

HI William.

If you're still listening, then if you are only interested in the period and not all of the values of x along the way, there is no need to save those values. If you do want to save them, then x should be preallocated using x = zeros(2^31,1). Otherwise Matlab has to reset the size of x at every step which is time consuming. And you can do the check as you go, without the need fo a second for loop.

a = 69069; % Multiplier
b = 69069; % Constant
m = 2^31;  % Modulus
x1 = 69069; % Seed value
x = mod(a*x1+b,m);
count = 1;
tic
while x~=x1
    x = mod(a*x+b,m);
    count = count+1;
end
count
toc  
  count = 
     2.147483648000000e+09
  Elapsed time is 160.645672 seconds.

The count is 2^31, so in this case the period is the maximum.

Answer 2

[Anurag]

Hi William,

The brute force method that you appear to be using is indeed very computational and time intensive, there exists better methods one of which I’m sharing below.

A more efficient approach to determining the period of an LCRNG involves using mathematical properties of congruential generators. Linear congruential generators have a maximum possible period equal to their modulus (m) if they are full-period generators. One common method to ensure the maximum period is to select appropriate values for the multiplier (a) and the constant (b). Here are a few suggestions:

• Use a Known Good Pair (a, b): There are well-known combinations of (a, b) that ensure the maximum possible period for specific values of m. For m = 2^31, the pair (a = 48271, b = 0) guarantees the full period.
• Skip Ahead Techniques: If you are interested in skipping ahead in the sequence to avoid generating large numbers of random numbers, you can use skip-ahead techniques. These techniques allow you to directly compute the state after k steps instead of simulating each step. This is particularly useful when you want to determine the period starting from a seed that is far from the beginning of the period.

Hope this helps! Thanks.