Azzera filtri
Azzera filtri

Period of a Linear Congruential Random Number Generator

60 visualizzazioni (ultimi 30 giorni)
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)

Risposta accettata

David Goodmanson
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.

Più risposte (1)

Anurag
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.

Categorie

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

Prodotti


Release

R2022a

Community Treasure Hunt

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

Start Hunting!

Translated by