随机数生成器的实现

Question

可能是重复问题：
随机数生成器如何工作？

我正在寻找C/C++中随机数生成器的内部实现。基本上我想知道，当rand()被调用时，究竟发生了什么。毕竟机器遵循一定的指令集，它怎么能是随机的！
编辑：想知道如何在C/C++中实现一个随机数生成器。

- MaxSteel

---

这就是为什么它不是“随机的”，而是“伪随机”的原因。 - amit

因为它并不是真正的随机：http://zh.wikipedia.org/wiki/伪随机数生成器 - Averroes

实现？如果我不想使用库函数。 - MaxSteel

C++11让你使用Mersenne twisters等更好的随机数生成器，只需使用<random>即可。线性同余发生器可以在此链接中了解：http://en.wikipedia.org/wiki/Linear_congruential_generator。 - chris

其他密切相关的问题：https://dev59.com/xnRB5IYBdhLWcg3wkH9N，https://dev59.com/PGw05IYBdhLWcg3wpTYV - jogojapan

Answer 1

它们是伪随机数生成器，而不是真正的随机数生成器。这通常是一件好事，因为它使得在涉及“随机”数字的 Bug 中更容易复现。

你可以获得随机数生成器，例如在 Linux 下读取 /dev/random，但通常附带 C 库的普通随机数生成器并非如此。

最简单的一个是线性同余生成器(LCG)，其中:

nx+1 = (nx * A + C) 模 M

具有合适选择的 A, C, 和 M 的值。

维基百科关于 LCG 的页面 给出了各种实现使用的示例值。例如，在那里列出的 glibc 有 A = 1103515245, C = 12345, M = 2^31，所以它的形式很简单:

static unsigned int seed = 1;
void srand (int newseed) {
    seed = (unsigned)newseed & 0x7fffffffU;
}
int rand (void) {
    seed = (seed * 1103515245U + 12345U) & 0x7fffffffU;
    return (int)seed;
}

顺便提一下，glibc 的实现仍然包含这个生成器（称为 Type 0 生成器），但它也有一个更复杂的三项式生成器，这应该会更好。

还有更复杂的生成器（如 Mersenne twister）具有更长的循环时间（即开始重复之前的时间）。

任何真正的随机生成器都必须使用真正的随机输入源，这就是为什么 /dev/random 有时会“等待熵”，而 /dev/urandom 则不会。

“真正”的随机源可能会受到按键之间的时间、用户输入的数据、网络数据包的内容、磁盘 I/O 模式、ICMP 响应在网络上传输的时间以及各种非确定性的奇妙影响。

除非你非常关注加密，否则通常的随机数生成器应该已经足够了。

- paxdiablo

Answer 2

这是一个简单的伪随机算法：

//generates pseudo random series of numbers 0...RAND_MAX - 1 with uniform distribution, starting with 0

static const int A = 15342; // any number in (0, RAND_MAX)
static const int C = 45194; // any number in [0, RAND_MAX)
static const RAND_MAX = 100000;

int rand()
{
    static int prev = 0; //seed. any number in [0, RAND_MAX)
    prev = ( prev * A + C ) % RAND_MAX;
    return prev;
}

你可以在这里阅读更多信息：http://en.wikipedia.org/wiki/Linear_congruential_generator

- Andrew

---

顺便说一句，A、C 和 RAND_MAX 的值选择得非常糟糕，你的所有数字都将是 5000 的倍数 :-) 相对质数往往会给出更好的分布。 - paxdiablo

@paxdiablo：同意，稍微随机一下）但无论如何，它都会给出一个均匀的分布。选择好的数字需要更多的研究。 - Andrew

那个静态变量 prev 似乎从未被更新过。 - jjmontes

@jjmontes：谢谢，已更正。 - Andrew

Answer 3

正如我在评论中所说，RAM机器的随机生成器并不是真正的随机，它们是伪随机。

您可以随时查看java.util.Random的Java源代码。

具体来说，您要找的是next(int bits)方法。

protected int next(int bits) {
      long oldseed, nextseed;
      AtomicLong seed = this.seed;
      do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
      } while (!seed.compareAndSet(oldseed, nextseed));
      return (int)(nextseed >>> (48 - bits));
}

(*) 这个答案适用于之前的问题版本，该版本被标记为Java，并没有明确要求使用C++。

- amit