Period of a Linear Congruential Random Number Generator
18 visualizzazioni (ultimi 30 giorni)
William il 24 Set 2022
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.
a=69069; % Multiplier
b=69069; % Constant
m=2^31; % Modulus
x(1)=69069; % Seed value
x(i+1) = mod((a*x(i))+b,m);
p=0; % Period
David Goodmanson il 31 Ago 2023
Modificato: David Goodmanson il 31 Ago 2023
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;
x = mod(a*x+b,m);
count = count+1;
Elapsed time is 160.645672 seconds.
The count is 2^31, so in this case the period is the maximum.
Più risposte (1)
Anurag il 31 Ago 2023
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.