rand() 是如何工作的?它有某些倾向吗?有什么更好用的吗? [英] How does rand() work? Does it have certain tendencies? Is there something better to use?

问题描述

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

I have read that it has something to do with time, also you get from including time.h, so I assumed that much, but how does it work exactly? Also, does it have any tendencies towards odd or even numbers or something like that? And finally is there something with better distribution in the C standard library or the Foundation framework?

推荐答案

简要说明:

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

• You use time.h to get a seed, which is an initial random number. C then does a bunch of operations on this number to get the next random number, then operations on that one to get the next, then... you get the picture.

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

rand() is able to touch on every possible integer. It will not prefer even or odd numbers regardless of the input seed, happily. Still, it has limits - it repeats itself relatively quickly, and in almost every implementation only gives numbers up to 32767.

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

C does not have another built-in random number generator. If you need a real tough one, there are many packages available online, but the Mersenne Twister algorithm is probably the most popular pick.

现在，如果您对为什么上述正确的原因感兴趣，这里是关于rand()如何工作的详细信息:

Now, if you are interested on the reasons why the above is true, here are the gory details on how rand() works:

rand() 是所谓的线性同余生成器."这意味着它采用了以下形式的方程:

rand() is what's called a "linear congruential generator." This means that it employs an equation of the form:

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

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

其中 x_n 是 n^th 个随机数，a和 b 是一些预定的整数.算术以 m 为模进行，m 通常为 2³²，具体取决于机器，因此计算中只保留最低的 32 位x_n+1.

where x_n is the n^th random number, and a and b are some predetermined integers. The arithmetic is performed modulo m, with m usually 2³² depending on the machine, so that only the lowest 32 bits are kept in the calculation of x_n+1.

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

In English, then, the idea is this: To get the next random number, multiply the last random number by something, add a number to it, and then take the last few digits.

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

A few limitations are quickly apparent:

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

• First, you need a starting random number. This is the "seed" of your random number generator, and this is where you've heard of time.h being used. Since we want a really random number, it is common practice to ask the system what time it is (in integer form) and use this as the first "random number." Also, this explains why using the same seed twice will always give exactly the same sequence of random numbers. This sounds bad, but is actually useful, since debugging is a lot easier when you control the inputs to your program

其次，a 和 b 必须非常非常仔细地选择，否则你'会得到一些灾难性的结果.幸运的是，线性同余生成器的方程足够简单，数学已经得到了一些细节.事实证明，选择满足 *a***mod8 = 5 和 ***b* = 1 的 a 将确保所有 m 个整数都是同样可能的，与种子的选择无关.您还需要一个非常大的 a 值，以便每次将其乘以 x_n 时都会触发一个模数并切碎关闭很多数字，否则一行中的许多数字将只是彼此的倍数.因此，根据 Knuth 的说法，a 的两个常见值(例如)是 1566083941 和 1812433253.GNU C 库恰好使用 a=1103515245 和 b=12345.LCG 的维基百科页面上提供了许多实现的值列表.

Second, a and b have to be chosen very, very carefully or you'll get some disastrous results. Fortunately, the equation for a linear congruential generator is simple enough that the math has been worked out in some detail. It turns out that choosing an a which satisfies *a***mod8 = 5 together with ***b* = 1 will insure that all m integers are equally likely, independent of choice of seed. You also want a value of a that is really big, so that every time you multiply it by x_n you trigger a the modulo and chop off a lot of digits, or else many numbers in a row will just be multiples of each other. As a result, two common values of a (for example) are 1566083941 and 1812433253 according to Knuth. The GNU C library happens to use a=1103515245 and b=12345. A list of values for lots of implementations is available at the wikipedia page for LCGs.

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

Third, the linear congruential generator will actually repeat itself because of that modulo. This gets to be some pretty heady math, but the result of it all is happily very simple: The sequence will repeat itself after m numbers of have been generated. In most cases, this means that your random number generator will repeat every 2³² cycles. That sounds like a lot, but it really isn't for many applications. If you are doing serious numerical work with Monte Carlo simulations, this number is hopelessly inadequate.

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

A fourth much less obvious problem is that the numbers are actually not really random. They have a funny sort of correlation. If you take three consecutive integers, (x, y, z), from an LCG with some value of a and m, those three points will always fall on the lattice of points generated by all linear combinations of the three points (1, a, a²), (0, m, 0), (0, 0, m). This is known as Marsaglia's Theorem, and if you don't understand it, that's okay. All it means is this: Triplets of random numbers from an LCG will show correlations at some deep, deep level. Usually it's too deep for you or I to notice, but its there. It's possible to even reconstruct the first number in a "random" sequence of three numbers if you are given the second and third! This is not good for cryptography at all.

好的部分是像 rand() 这样的 LCG 占用空间非常非常小.它通常只需要 32 位来保留状态，这真的很好.它也非常快，只需要很少的操作.这些使其适用于非关键嵌入式系统、视频游戏、休闲应用程序等.

The good part is that LCGs like rand() are very, very low footprint. It typically requires only 32 bits to retain state, which is really nice. It's also very fast, requiring very few operations. These make it good for noncritical embedded systems, video games, casual applications, stuff like that.

PRNG 是一个引人入胜的话题.维基百科 如果您渴望了解更多有关历史或各种今天的实现.

PRNGs are a fascinating topic. Wikipedia is always a good place to go if you are hungry to learn more on the history or the various implementations that are around today.

这篇关于rand() 是如何工作的?它有某些倾向吗?有什么更好用的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！