GLIBC随机数发生器

给定一个种子,函数首先使用模数为(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的输出是标准要求的正整数。

你可能会在构建伪随机生成器时读到这篇文章,里面有所有答案。

选择LCG的周期、乘数等:

http://en.wikipedia.org/wiki/Linear_congruential_generator

http://en.wikipedia.org/wiki/Pseudo-random_number_generator

经过一些研究,我发现这个特定的数字(16807和2^31-1)是用来创建一个完整的周期的,也就是说,在这些数字再次出现之前生成0和2^31-1之间的所有数字。注意,2^31-1是梅森素数,16807是本原根模(p);参见费马-欧拉定理-这远远超出了我的范围