4

我正在整理一个内部的“每个开发人员都应该知道”的 wiki 页面。

我看到了很多关于 的讨论rand() % N，但没有一个网页可以解释这一切。

例如，我很好奇这个问题是否仅针对 C 和 Linux，或者它是否也适用于 Windows、C++。Java、.Net、Python、Perl。

请帮助我深入了解这一点。此外，数字的非随机性如何？谢谢！

4

2 回答 2

2

我没有可供您参考的网页，但我可能有一个“信封背面”的解释会有所帮助。简单随机数生成器的工作方式是按照以下步骤操作

  1. 使用最后生成n的号码或种子号码。
  2. 将该数字乘以一个特殊的大数
  3. 添加另一个特殊的大数
  4. 将其除以第三个特殊大数并丢弃余数
  5. 返回结果

现在，如果您考虑除了第 4 步之外的所有操作，您正在执行的操作只有低位可以改变结果的低位。加上 1001 和 100...00001 将以 ...02 结尾（哈，虽然我说的是基数 2，但实际上这些数字是基数 12 的咯咯笑声。）无论计算的高端是什么。同样，当你乘以它时，无论如何它都会以 1 结尾。

高端也有类似的问题，十亿乘以十亿，必然会主导百位凋零的贡献。这表明中间是好事发生的地方。许多位在这里相互作用——高、中、低。

这就是除法步骤的目的，它切断了结果中没有太多交互的底部块。顶部块通常不会被切掉，因为当乘法不再适合机器字时，计算机会丢弃高位。

最后，尽管截止点有些随意，但您可能比设计算法的人更挑剔，但仍然会砍掉更多位。

对于您的问题，它们可能有多糟糕，它们可能非常糟糕。看到这一点的最简单方法是将单个数字分组为元组并绘制它们。因此，如果您有随机数a, b, c, d, ...图表(a,b), (c,d), ...并查看结果。这被称为光谱测试，兰德完美地失败了。这个我有一个尝试链接http://random.mat.sbg.ac.at/results/karl/spectraltest/

于 2010-04-23T16:08:54.113 回答
2

查看http://en.wikipedia.org/wiki/Linear_congruential_generator，这可能是大多数内置随机数生成器使用的算法。

向下滚动，查找以“LCG 的另一个问题是生成序列的低阶位的周期要短得多..”开头的段落，以了解rand() % N.

于 2010-04-04T20:02:18.300 回答