c - GLIBC 随机数生成器

Question

我明天有一个 PRNG 演示，必须演示 rand() 函数的工作原理。

我找到了一个描述我所需要的内容的网站，但是，由于我是 C 语言的初学者，我有几个问题。

首先，网站是http://www.mscs.dal.ca/~selinger/random/

我的问题是:

• 为什么前三十个数字是 mod (2^31) - 1，其余的是 mod 2^32(从第 34 个开始)(与 sizeof(int) 相关)？
• 为什么第 30 个数字最后变成 mod (2^31) - 1 有什么特别的原因，为什么不用 31 或 29？
• 为什么 r0...r343 被丢弃了？
• 为什么 ri+344 的最低有效位被丢弃？
• 为什么选择 16807 作为乘数？

我知道有很多关于 PRNG 的问题，但我找不到这些问题的答案。

我会在全类同学面前展示这个话题，肯定有人会问其中一个问题，我需要一些支持。谢谢。

Answer 1

给定一个种子，该函数首先使用模数为 (2^31) - 1 的 LCG 填充一个包含 34 个无符号长整数的数组。可以使用任何 LCG。此数组用于 LFSR 生成器，制表符位于 3 和 31，使用加法模 2^32。此 LFSR 的输出通过右移丢弃最低有效位进行后处理。

前 344 个值被丢弃以提高数字的质量，以防数组的原始状态的熵太少(想象一下几乎所有数字都为零的情况)。鉴于 LFSR 的输出满足 r_{i} = r_{i-3} + r_{i-31} mod 2^32 一个关系也适用于最低有效位，该函数通过丢弃最低有效位来掩盖这一点少量。移位还保证了 rand 的输出是标准要求的正整数。