在C语言中的随机数生成

Question

最近我开始开发一款简单的游戏。这是我先前开发的版本的改进版。游戏的成功在于其不同模式下的随机数生成：

模式1 - 真正随机模式

myRand(min, max, mode=1);

• 应返回一个介于min和max之间的随机整数。

模式2 - 伪随机：从袋中取出令牌模式

myRand(min, max, mode=2);

• 应返回一个介于min和max之间的随机整数。还应在内部跟踪返回的值，并且直到所有其他值都至少返回一次，才能再返回相同的值。

模式3 - 伪随机：人类模式

myRand(min, max, mode=3);

• 应返回一个介于min和max之间的随机整数。随机化不应该是纯粹数学上的随机，而是用户感知的随机。 人类如何看待“随机”。

* 假设代码对时间非常敏感（即欢迎任何性能优化）

* 伪代码可以，但我需要的是C语言实现。

* 请保持简单。单个函数应该足够（这就是我要找的）

谢谢您

- TheCodeArtist

---

你不能在计算机上生成真正的随机数！嗯，你可以通过这个设备来生成，http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf。 - Svisstack

对于模式2，如果说数字不能重复直到所有数字都被给出，那就不是随机的。随机意味着你无法预测一个数字是否会重复。如果说数字不能重复，你就透露了一些关于后续数字可能性的信息。因此并不真正随机。这也许是你想要的，但它不能被称为随机。 - Tesserex

@Tesserex 这是一种伪随机模式。它在像“谁想成为百万富翁”这样的问答游戏中使用，其中同一问题不应在单个会话中被问两次。我猜现在我已经透露了我的游戏的一部分...;-) - TheCodeArtist

“真随机”和“伪随机”在这个上下文中有明确定义。真的意思是，即使您知道系统的状态，例如使用硬件设备的噪声，您也无法预测下一个数字。 PRNG是伪随机数生成器，下一个数字是通过给定的公式计算的，因此当您知道系统的状态时，可以预测它们。 Mode 2是一个排列或洗牌问题。 Mode 3则混合了这些。 - Secure

@secure 如果我在使用伪随机数方面有所错误，请原谅我。但是，我所说的“伪随机”是指“不真正随机”。希望您能理解... - TheCodeArtist

Answer 1

首先，研究Mersenne Twister是一个很好的解决方案。

模式1：直接使用值。由于这些值是32位的，根据最小值和最大值的范围，模(max-min+1)可能已经足够了，但如果该区间不是2的幂，则存在一定偏差。否则，您可以将该值视为介于0和1之间的浮点值，并需要进行一些额外的操作。可能有其他解决方案来获得相等的整数分布，但我尚未研究过这个特定的问题。Wikipedia在这里可能会有所帮助。

模式2：使用填充min..max数组并随机排序的方法。按顺序返回洗牌后的值。当您完成数组时，请重新填充并重新洗牌。

模式3是最复杂的。少量的随机值会显示出聚类现象，即如果您计算不同值的出现次数，则会有一个平均值，并且计数通常高于或低于此平均值。就我理解的您的链接而言，人们希望随机性的所有计数都恰好在平均值上。因此，计算发生的次数并给予不同的值更高的概率，具体取决于它们与平均计数的距离。只需使用多重数组再次重复模式2即可，例如使用10倍于(max-min+1)大小的数组，用10x min、10x min+1等填充它，然后对其进行洗牌。每满10轮，您就可以确保计数完全相等。

关于模式3的编辑：

假设min=1且max=5。您计算出现次数。如果它们都具有相同的概率（使用良好的随机生成器应该是如此），则每个值发生的概率为0.2，因为概率加起来为1.0：

Value Occur Probability
1     7x    0.2
2     7x    0.2
3     7x    0.2
4     7x    0.2
5     7x    0.2
Average: 7x

但是现在假设数字3只出现了5次，数字5出现了9次。如果你想保持均等分布，那么数字3必须成为更高的概率来赶上平均出现次数，数字5必须成为更低的概率，以免增长过快，直到所有其他值都赶上。尽管如此，所有单个概率的总和必须为1.0：

Value Occur Probability
1     7x    0.2
2     7x    0.2
3     5x    0.3
4     7x    0.2
5     9x    0.1
Average: Still 7x

不同的事件发生概率也应该不同，这取决于它们与平均值的距离:

Value Occur Probability
1     10x   0.05
2     4x    0.35
3     5x    0.3
4     7x    0.2
5     9x    0.1
Average: Still 7x

实现并不那么琐碎，但很可能非常缓慢，因为随机生成器仍然提供相等的概率，因此修改后的模式2可能是一个足够好的选择。

- Secure

---

@ 安全。谢谢。您能否详细解释一下Mode3，特别是"count the occurrences and give the different values a higher probability"部分？ - TheCodeArtist

Answer 2

作为第一步，请去阅读 Knuth。

- Chris Card

---

实际上，只需浏览他的伪随机数生成方法和算法，您就可以轻松解决这些问题。 - Ricardo Ferreira

@chris 我确实看了KNUTH的代码（http://www-cs-faculty.stanford.edu/~uno/programs/rng.c），但我现在特别寻求任何实现myrand()函数的指针，使其可以在所有三种模式下运行。 - TheCodeArtist

Answer 3

如果max-min = 2^N-1，您可以使用线性反馈移位寄存器来进行模式2。这种随机生成器产生一个由N位内部存储的2^N-1个数字的重复序列。请参见http://en.wikipedia.org/wiki/LFSR以获取更详细的说明和代码。

- Rudi

---

该序列不应重复。即名称数字不应连续返回两次；这不是随机的。此外，传递给myrand()的最大值和最小值有时可能在对该函数的连续调用之间发生更改，因此LFSR不是可行的解决方案... - TheCodeArtist

Answer 4

人类可感知的模式与第一种模式相同，但是结果为2、5、10的倍数时可以任意拒绝。

如果我要求一个随机数，却得到了5或10，我会认为它不够随机。

- Joseph Le Brech