rand() 函数有多随机？

Question

更具体地说，我的问题是，如果时间无限，int(rand()*1000)最终会命中0到999之间的每个数字吗？对于10^4、10^5等呢？我猜一旦你达到内存大小，就肯定会出现错误，也就是说，如果rand()返回一个浮点数，它在内存中占据n个位，你不可能命中超过n个不同的整数，因此一旦你达到rand()*(2^n+1)，就肯定会错过一些数。

- Joe

---

没有唯一的 rand() 函数；它可能因语言而异，对于某些语言可能因实现而异。请更精确地说明您所询问的语言和平台。 - Stephen Canon

你能指出你所说的 rand() 设施是什么吗？编程语言、库等等... 一般来说，你是对的，可能的输出数量不能超过可能的输入数量。 - rlibby

大多数编程语言使用LCG作为它们的标准rand()，因为它具有轻量级的特性，尽管有些语言有更多的选项。 - Hazok

Answer 1

是的，如果有无限的时间并且具有无限周期，它将命中您范围内的每个数字；一旦再次到达种子值，序列就会重复。当然，正如您提到的那样，您将受到rand()返回值精度的限制，并且最终您将遇到一个破坏点，无法映射到足够大的整数范围内的每个整数。但是，如果考虑具有无限精度和周期（您提到了无限）的理论计算机，则在无限时间内，您将命中指定范围内的每个数字。

但是，rand()使用的是LCG，它不会给您提供均匀分布的数字。也就是说，您会得到一些数字比其他数字更频繁地出现（尽管在无限时间内，您会命中所有数字，因为无限很酷）。如果需要均匀分布，则使用类似Mersenne Twister算法的东西。Boost库中有一个随机生成器，其中包含Mersenne Twister，并且易于实现。

- Hazok

---

可能不是每种语言都使用LCG，但LCG非常普遍。 - Hazok

@Zach，我的观点是这个问题没有足够的细节来回答。例如：Python目前使用Mersenne Twister而不是线性同余生成器。而这个rand()调用有多少种可能的结果？是单精度、双精度还是小数？如果不知道这些细节，你只是在猜测。 - rlibby

这个问题更多地是关于随机生成器的理论性讨论，否则就不会提到无限时间，并且您可以概括您的答案以考虑不同的生成器，并给出一些更常见的例子，例如LCG和MT。此外，您也可以以一般化的方式处理精度，因为这些算法是为精度而设计的（最终寄存器的大小将比现在更大）。根据性能或随机性质量的优先级，您需要相应地选择算法，而且除了LCG和MT之外还有更多的选项。 - Hazok

此外，任何人都可以轻易地设计出像那个漫画中的低质量生成器。这样的算法有无数个... - Hazok