Period of a Linear Congruential Random Number Generator

25 次查看（过去 30 天）
William
William 2022-9-24
编辑： David Goodmanson 2023-8-31
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)

请先登录，再回答此问题。

采纳的回答

David Goodmanson
David Goodmanson 2023-8-31
编辑：David Goodmanson 2023-8-31
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.

更多回答（1 个）

Anurag
Anurag 2023-8-31
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.

类别

在 Help Center 和 File Exchange 中查找有关 Random Number Generation 的更多信息

标签

产品


版本

R2022a

Community Treasure Hunt

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

Start Hunting!

Translated by