# Period of a Linear Congruential Random Number Generator

60 visualizzazioni (ultimi 30 giorni)
William il 24 Set 2022
Modificato: David Goodmanson il 31 Ago 2023
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)
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

### Risposta accettata

David Goodmanson il 31 Ago 2023
Modificato: David Goodmanson il 31 Ago 2023
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.
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

### Più risposte (1)

Anurag il 31 Ago 2023
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.
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

### Categorie

Scopri di più su Creating and Concatenating Matrices in Help Center e File Exchange

R2022a

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by