5

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

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

4

3 回答 3

12

它们是伪随机数生成器，而不是真正的随机数生成器。这通常是一件好事，因为它允许您在涉及“随机”数字的情况下更轻松地重现错误。

您可以获得随机数生成器，例如/dev/random在 Linux 下阅读，但 C 库附带的普通生成器通常不是。

最简单的是线性同余生成器，其中：

n(x+1) = n(x) * A + C modulo M

with suitably chosen values of A, Cand M.

Wikipedia 的 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 实现中仍然有这个生成器（称为 0 型生成器），但它也有一个更高级的三项式生成器，它（可能）更好。

还有更复杂的（例如梅森捻线机）具有更长的循环时间（开始重复之前的时间）。

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

“真正的”随机源可能会受到击键之间的时间、用户输入的数据、网络数据包的内容、磁盘 I/O 模式、ICMP 响应通过网络返回所需的时间以及各种其他奇妙的影响，主要是非确定性的东西。

除非您对加密非常感兴趣，否则普通的随机数生成器就可以了。

于 2012-08-14T06:10:15.593 回答
1

正如我在评论中所说，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++。

于 2012-08-14T06:14:38.217 回答
1

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

//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

于 2012-08-14T06:16:39.573 回答