为线性同余生成器选择A，C和M

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在寻找一种简单的伪随机数生成器（PRNG），该生成器具有指定的周期，并保证在该周期内不会发生冲突。经过研究，我发现了非常著名的LCG，它非常完美。问题是，我在理解如何正确配置它方面遇到困难。这是我当前的实现：

    function LCG (state)
    {
        var a = ?;
        var c = ?;
        var m = ?;
        return (a * state + c) % m;
    }

它说，为了使所有种子值都有完整的时间，必须满足以下条件：

  1. 和 是相对质数

  2. 所有素因子整除 *

  3. 是4的倍数，则 是4 的倍数

和 很容易理解和测试。但是 ，我不太明白这意味着什么或如何检查它。那么C可以为零吗？如果非零怎么办？

总的来说，我需要选择A，C和M，以使我的周期为 。M等于周期，我不确定A和C。

回答：

从维基百科：

如果 c 不为零，则在且仅在以下情况下，LCG将对所有种子值具有完整的周期：

  1. c 和 m 是相对质数，

  2. a -1可被 m的 所有素因子整除，

  3. a -1是4的倍数，如果 m 是4的倍数。

你说你想要一个时期的48 5 -1，所以你必须选择 米 ≥48 5 -1。让我们尝试选择 m = 48 5

-1，看看会把我们带到哪里。如果希望周期为 m， 那么来自Wikipedia文章的条件将禁止您选择 c = 0 。 __

请注意，11、47、541和911是48 5 -1 的素数，因为它们都是素数，所以11 * 47 * 541 * 911 = 48 5 -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 5 -1，

  • c =除11、47、541和911以外的任何质数乘积（同样， c 必须小于 m ），

  • 对于您选择的任何非负 x ，a = x * 11 * 47 * 541 * 911 + 1 （而且 a 必须小于 m ）。 __

这是一个较小的测试用例（在Python中），使用48 2 -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。）

以上是 为线性同余生成器选择A，C和M 的全部内容， 来源链接： utcz.com/qa/417461.html

回到顶部