为线性同余发生器挑选A,C和M.

Question

我希望实现一个具有指定周期的简单伪随机数发生器(PRNG),并确保在该周期的持续时间内没有冲突.经过一番研究后,我发现了非常着名的LCG,这是完美的.问题是,我无法理解如何正确配置它.这是我目前的实施:

    function LCG (state)
    {
        var a = ?;
        var c = ?;
        var m = ?;

        return (a * state + c) % m;
    }

它表示,为了使所有种子值都有一个完整的时间段,必须满足以下条件:

1. c和m是相对素数
2. a-1可被m的所有素因子整除
3. 如果m是4的倍数,则a-1是4 的倍数

1和3很容易理解和测试.然而,2,我不太明白这意味着什么或如何检查它.那么C,它可以为零吗？如果它不是零怎么办？

总的来说,我需要选择A,C和M,使得我的周期为48 ^ 5 - 1.M等于期间,我不确定A和C.

Answer 1

来自维基百科:

如果c非零,则当且仅当以下情况时,LCG将具有所有种子值的完整周期:

1. c和m是相对素数,
2. a -1可被m的所有素因子整除,
3. 如果m是4的倍数,则a -1是4 的倍数.

你说你想要一个时期的48 ⁵ -1,所以你必须选择米 ≥48 ⁵ -1.让我们尝试选择m = 48 ⁵ -1,看看我们在哪里.如果您希望周期为m,则Wikipedia文章中的条件禁止您选择c = 0 .

注意,11,47,541和911是48 ⁵ -1 的主要因子,因为它们都是素数且11*47*541*911 = 48 ⁵ -1.

让我们来看看每个条件:

1. 因为c和m是相对素数,c和m必须没有共同的素因子.因此,选择11,47,541和911 以外的任何素数,然后将它们相乘以选择你的c.
2. 你需要选择一个这样一个 -1是所有的质因数整除米,即一 = X*11*47*541*911 + 1对于任何X你选择的.
3. 你的m不是4的倍数,所以你可以忽略第三个条件.

综上所述:

• m = 48 ⁵ -1,
• C = 911比11,47,541其他素数的任何产品,和(也ç必须小于米),
• a = x*11*47*541*911 + 1,对于您选择的任何非负x(同样,a必须小于m).

这是一个较小的测试用例(在Python中),使用48 ² -1(具有素数因子7和47)的周期:

def lcg(state):
    x = 1
    a = x*7*47 + 1
    c = 100
    m = 48**2 - 1
    return (a * state + c) % m

expected_period = 48**2 - 1
seeds = [5]
for i in range(expected_period):
    seeds.append(lcg(seeds[-1]))
print(len(set(seeds)) == expected_period)

它True应该输出.(如果您在阅读Python时遇到任何问题,请告诉我,我可以将其翻译为JavaScript.)