objective-c - rand() 是如何工作的？它有某些倾向吗？有什么更好用的吗？

Question

我读过它与时间有关，你也可以从包含 time.h 中得到，所以我假设了这么多，但它究竟是如何工作的？此外，它是否有奇数或偶数之类的倾向？最后，在 C 标准库或 Foundation 框架中是否有更好的分布？

Answer 1

简要地:

您使用 time.h得到一个种子，它是一个初始随机数。然后 C 对该数字进行一系列操作以获得下一个随机数，然后对该数字进行操作以获得下一个，然后......你得到了图片。

rand()能够触及每一个可能的整数。无论输入种子如何，它都不会喜欢偶数或奇数，很高兴。尽管如此，它还是有限制的——它会相对较快地重复自己，并且几乎在每个实现中只给出最多 32767 的数字。

C 没有另一个内置的随机数生成器。如果你需要一个真正的硬包，网上有很多包，但 Mersenne Twister算法可能是最受欢迎的选择。

现在，如果您对上述正确的原因感兴趣，这里是有关如何rand() 的详细信息。作品:
rand()就是所谓的“linear congruential generator”。这意味着它采用了以下形式的方程:

xn+1 = ( *a****xn + ***b* ) mod m

其中 xn 是第 n 个随机数， 和 b 是一些预定的整数。算术以 m 为模进行，m 通常为 232，具体取决于机器，因此在 xn+1 的计算中只保留最低的 32 位。

那么，在英语中，想法是这样的:要得到下一个随机数，将最后一个随机数乘以某物，再加上一个数字，然后取最后几位数字。

一些限制很快就会显现出来:

首先，您需要一个起始随机数。这是您的随机数生成器的“种子”，这就是您听说过 time.h 的地方。正在使用。由于我们想要一个真正的随机数，通常的做法是询问系统现在几点了(以整数形式)并将其用作第一个“随机数”。此外，这也解释了为什么使用相同的种子两次总是会给出完全相同的随机数序列。这听起来很糟糕，但实际上很有用，因为当您控制程序的输入时，调试会容易得多

二、 和 b 必须非常非常小心地选择，否则你会得到一些灾难性的结果。幸运的是，线性同余生成器的方程很简单，数学已经得到了一些细节。事实证明，选择 满足 *a***mod8 = 5 和 ***b* = 1 将确保所有 m 个整数的可能性相等，与种子的选择无关。您还需要 的值这真的很大，所以每次你将它乘以 xn 时，你都会触发一个模数并砍掉很多数字，否则一行中的许多数字将只是彼此的倍数。结果，的两个常见值 (例如)根据 Knuth 的说法是 1566083941 和 1812433253。 GNU C 库恰好使用 =1103515245 和 b =12345。在 wikipedia page for LCGs 中提供了许多实现的值列表。 .

第三，由于该模数，线性同余生成器实际上会重复自己。这将是一些非常令人兴奋的数学运算，但结果很高兴非常简单:在生成 m 个数字后，序列将自我重复。在大多数情况下，这意味着您的随机数生成器将每 232 个周期重复一次。这听起来很多，但实际上并不适用于许多应用程序。如果您正在使用 Monte Carlo 模拟进行严肃的数值工作，那么这个数字绝对是不够的。

第四个不太明显的问题是这些数字实际上并不是真正随机的。他们有一种有趣的相关性。如果从 LCG 中取三个连续的整数 (x, y, z)，其中某个值为 和 m，这三个点将始终落在由三个点 (1, a, a2), (0, m, 0), (0, 0, m) 的所有线性组合生成的点阵上。这就是众所周知的 Marsaglia 定理，如果你不明白，没关系。这意味着:来自 LCG 的随机数三元组将在某个深层次上显示相关性。通常它对你或我来说太深了，但它就在那里。如果给定第二个和第三个数字，甚至可以在三个数字的“随机”序列中重建第一个数字!这对密码学根本没有好处。

好的部分是 LCG 喜欢 rand()是非常非常低的足迹。它通常只需要 32 位来保持状态，这真的很好。它也非常快，只需要很少的操作。这些使其适用于非关键嵌入式系统、视频游戏、休闲应用程序等。

PRNG 是一个引人入胜的话题。 Wikipedia如果您渴望了解有关历史或当今各种实现的更多信息，它始终是一个不错的去处。