重塑轮子:随机数发生器

Question

所以我是C++的新手,我正在尝试学习一些东西.因此,我试图制作一个随机数发生器(如果你愿意,可以使用RNG或PRNG).我有RNG的基本知识,就像你必须从种子开始,然后通过算法发送种子.我坚持的是人们如何提出所述算法.

这是我得到种子的代码.

int getSeed()
{
    time_t randSeed;
    randSeed = time(NULL);
    return randSeed;
}

现在我知道C++中有预先构建的RNG,但我希望学习的不仅仅是复制其他人的工作并尝试解决它.

因此,如果有人能带我到我能阅读的地方或向我展示如何为此提出算法的例子,我将非常感激.

Answer 1

首先,为了澄清,您提出的任何算法都将是伪随机数生成器而不是真正的随机数生成器.由于您将制作算法(即编写函数,即制作一组规则),随机数生成器必须最终重复自身或执行类似的非随机操作.

真正的随机数生成器的例子是从自然中捕获随机噪声并将其数字化的实例.这些包括:

http://www.fourmilab.ch/hotbits/

http://www.random.org/

您还可以购买产生白噪声的物理设备(或其他随机方式)并以数字方式捕获它:

http://www.lavarnd.org/

http://www.idquantique.com/true-random-number-generator/products-overview.html

http://www.araneus.fi/products-alea-eng.html

就伪随机数生成器而言,最容易学习的(和普通人可能自己做的那些)是线性同余生成器.不幸的是,这些也是一些最糟糕的PRNG.

确定什么是优质PRNG的一些指导原则包括:

1. 周期性(可用数字的范围是多少？)
2. 连续数字(相同数字连续两次重复的概率是多少)
3. 均匀性(是否可能从某个子范围中选择数字作为另一个子范围)
4. 逆向工程的难度(如果它接近真正随机,那么有人不应该根据它生成的最后几个数字找出它生成的下一个数字)
5. 速度(我可以多快生成一个新数字？需要5或500次算术运算)
6. 我确信还有其他我想念的人

Mersenne Twister是目前比较流行的一种在大多数应用中被认为是好的(即非密码学).正如您从链接中看到的,它是一个简单的算法,可能只有30行代码.然而,试图从头开始提出这些20或30行代码需要大量的智力和PRNG的研究.通常,最着名的算法是由教授或行业专业人士设计的,他们已经研究过几十年的PRNG.

我希望你研究PRNG并尝试自己动手(尝试Knuth的计算机编程艺术或数字食谱作为起点),但我只是想把这一切都放在一天结束时(除非PRNG将是你的生活的工作)只是使用别人提出的东西要好得多.另外,按照这些思路,我想指出历史编译器,电子表格等不使用大多数数学家认为好的PRNG,所以如果你需要高质量的PRNG,请不要使用标准库在C++,Excel,.NET,Java等等,直到你研究他们正在实现它.