这个PRNG背后的理论是什么？

Question

__forceinline static int Random()
{
    int x = 214013, y = 2531011;
    seed = (x * seed + y);
    return ((seed >> 16) & 0x7FFF) - 0x3FFF; 
}

上面的代码返回具有良好均匀分布的PRNG。

现在将x更改为x + 1-结果序列不能再称为PRNG。

那么这个PRNG背后的理论是什么？“x和y被精心选择”，但它们是如何被选择的？

- Vadim

---

正态分布？你确定你是指的这个吗？ - Fred Larson

Fred Larson：我编辑了我的帖子，抱歉我的“typo”。我写了正态分布，因为（如果我想正确的话）正态分布是从现实世界中观察到的，所以一个好的PRNG应该复制正态分布的行为，以生成一个良好的随机序列？我对此正确吗？顺便说一下，生成器来自这里http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/。 - Vadim

一些自然现象可以很好地建模为正态分布。而其他一些现象，例如掷骰子，则不能。 - André Caron

André Caron，Fred Larson：好的，谢谢。我刚刚从维基百科上读到了关于均匀分布的内容，现在我明白了！ - Vadim

Answer 1

这看起来像是一个线性同余生成器。当乘数x可以被模数减一的所有质因数整除时（这里的模数是0x3FFFFFFFF，由于返回语句中的数学运算有点隐晦，因此有些隐藏），LCG会更好。

- MSalters

---

这里的模数实际上是0x80000000。而且，x-1可被m的质因数整除，而不是x可被m-1（这里是质数）的质因数整除。 - Alexandre C.

Answer 2

这是一个32位的LCG，它会舍弃最低16位。我怀疑这个生成器对于有趣的目的来说并不好。对于简单的游戏，这应该已经足够了。

你的具体问题可以通过我发布的链接得到答案：当且仅当x - 1是4的倍数（在维基百科的符号表示中，a是x，c是y，m是2 ^ 31），该生成器才能实现完整周期。

因此，当x为偶数时，该生成器并不是最佳选择。

- Alexandre C.

Answer 3

这是一个线性同余生成器。还应该有一个模数；经典公式如下:

seed = (a * seed + b) % m;

在这种情况下，m 简单地是 2^n，其中 n 是 seed 的位数（假设它具有无符号类型，因为需要模算术）。有大量文献介绍如何选择 a、b 和 m；一般来说，根据参考文献（《随机数生成器：好的生成器很难找到》，Park 和 Miller，CACM，1988 年 10 月），m 应该是一个质数，而 b 通常可以为 0；这个生成器违反了这两个规则。（违反第一个规则倾向于使低位非常不随机，这就解释了为什么结果会被移位。）

据我所知，确保选择良好的a和m的唯一方法是进行广泛的统计测试，尽管有一些方法可以识别出一些不好的选择。首先，a和m不应该有任何公共因子。（在最佳生成器中，两者通常都是质数。）在这里，m是2的幂，并且将1添加到x使其能够被2整除，因此您可以更或多少保证生成器的结果不会很好。

如需更多信息，建议您阅读本文。

- James Kanze

---

没有办法选择a和m，使得LCG通过例如Diehard测试。应该尽量避免使用LCG。 - Alexandre C.

James Kanze：感谢提供链接和文章。Alexandre C.：现在我特别使用这个伪随机数生成器来为我的音频应用程序生成白噪声。我真的需要一个非常快速的解决方案，而这个伪随机数生成器正好符合要求，而且我对它生成的噪声没有任何抱怨 - 对我来说看起来很好。 - Vadim

@Vadim：这取决于您如何处理噪声。 LCG的统计特性很差，现代存在更好的统计替代方案，它们至少具有同样好的性能（例如XOR-shift，参见Marsaglia的工作）。对于数值应用程序，我像避开瘟疫一样避免使用LCG，因为从LCG中绘制的随机向量往往是完全不随机的。 - Alexandre C.

Alexandre C.：我想要过滤噪声，得到一堆具有宽度的谐波 - 因此是噪声。然后我将从这些谐波中重构波形。这个伪随机数生成器是否足够？我现在还没有尝试过，所以我不知道这个伪随机数生成器是否有效。我现在也会检查XOR-shift。如果您有任何建议或您知道的表现更好和更快的源代码，我会很高兴如果您发布它。 - Vadim

挑刺的话，无论种子是int还是unsigned int，在大多数机器上结果都是相同的。在二进制补码算术中，有符号32 * 有符号32总是会产生与无符号32 * 无符号32相同的结果（在低32位中）。 - greggo