c++ 随机数生成器的实现[副本]

kuuvgm7e  于 2022-12-05  发布在  其他
关注(0)|答案(3)|浏览(228)

此问题在此处已有答案

10年前就关门了。

可能重复:

How does a random number generator work?
我正在寻找一个随机数生成器的C/C内部实现。基本上我有兴趣知道,究竟发生了什么,当rand()被调用。毕竟机器遵循明确的指令集,它怎么可能是随机的!
编辑:想知道我如何在C/C
中实现一个。

kyvafyod

kyvafyod1#

它们是伪随机数生成器,而不是真正的随机数生成器。这通常是一件好事,因为它可以让你更容易地复制涉及“随机”数的bug。
你可以得到随机数生成器,比如在Linux下阅读/dev/random,但是C库附带的普通随机数生成器通常没有。
最简单的一种是线性同余生成器,其中:
nx+1 = (nx * A + C) modulo M
其中适当选择的值为x1M2 N1 x、x1M3 N1 x和x1M4 N1 x。
Wikipedia's page on LCGs给出了一些不同实现使用的示例值。例如,这里列出的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生成器),但它也有一个更漂亮的三项式生成器,(大概)更好。
也有更复杂的(如梅森龙卷风),有一个更大的循环时间(时间之前开始重复)。
任何真正的随机发生器必须使用真正的随机输入源,这就是为什么/dev/random有时会阻止“等待熵”,而/dev/urandom不会。
“真正的”随机源可能会受到击键之间的时间、用户输入的数据、网络数据包的内容、磁盘I/O模式、ICMP响应通过网络返回所需的时间以及其他各种奇妙的、大多数是不确定性的因素的影响。
除非你非常喜欢加密,否则普通的随机数生成器就可以了。

k2arahey

k2arahey2#

下面是一个简单的伪随机算法:

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

6l7fqoea

6l7fqoea3#

正如我在评论中所说的,RAM机器的随机生成器不是真正的随机,它们是pseudo-random
您可以随时查看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++提出问题。

相关问题