真假随机数

绪言：随机数和伪随机数

随机数

真正的随机数是使用物理现象产生的：比如掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等等，这样的随机数发生器叫做物理性随机数发生器，它们的缺点是技术要求比较高。

根据的定义可以看到，真随机数是依赖于物理随机数生成器的。使用较多的就是电子元件中的噪音等较为高级、复杂的物理过程来生成。使用物理性随机数发生器生成的真随机数，可以说是完美再现了生活中的真正的“随机”，也可以称为绝对的公平。

伪随机数

真正意义上的随机数（或者随机事件）在某次产生过程中是按照实验过程中表现的分布概率随机产生的，其结果是不可预测的，是不可见的。而计算机中的随机函数是按照一定算法模拟产生的，其结果是确定的，是可见的。我们可以这样认为这个可预见的结果其出现的概率是100%。所以用计算机随机函数所产生的“随机数”并不随机，是伪随机数。

从定义我们可以了解到，伪随机数其实是有规律的。只不过这个规律周期比较长，但还是可以预测的。主要原因就是伪随机数是计算机使用算法模拟出来的，这个过程并不涉及到物理过程，所以自然不可能具有真随机数的特性。

for (int i = 0; i < 10; ++i)
    cout << rand() << " ";

连续两次运行这个过程，结果是一样的。（程序简单，自行试验）这就是伪随机数！ 就好像是在系统中已经有了一个0~RAND_MAX的一个乱序序列，我们调用rand()的时候都是参照这个序列和随机种子的，这里没有设置随机种子，因此随机种子为 $1$ ，当随机种子为 $x$ 的时候，我们可以根据这个随机种子 $x$ 来计算出一个随机数 $f(x, m)$ ，其中$m$为这个序列中的伪随机数。如果随机种子是固定的，那么每次调用rand()依然可以计算出来了。

随机种子

由上面我们就知道了，所谓随机数其实是伪随机数，所谓的‘伪’，意思是这些数其实是有规律的，只不过因为算法规律太复杂，很难看出来而已。

但是，再厉害的算法，如果没有一个初始值，它也不可能凭空造出一系列随机数来，我们说的种子就是这个初始值。

Random 随机数是这样生成的：我们将这套复杂的算法（是叫随机数生成器吧）看成一个黑盒，把我们准备好的种子扔进去，它会返给你两个东西，一个是你想要的随机数，另一个是保证能生成下一个随机数的新的种子，把新的种子放进黑盒，又得到一个新的随机数和一个新的种子，从此在生成随机数的路上越走越远。

标程缺陷

标程

查阅VB官方文档 https://docs.microsoft.com/zh-cn/office/vba/language/reference/user-interface-help/rnd-function

后我们知道：

函数： Rnd [ (Number) ]

返回值

如果 Number 为	则 Rnd 生成
小于 0	每次使用相同的数字，将 Number 用作种子。
大于 0	伪随机序列中的下一个数字。
等于 0	最近生成的数字。
未提供	伪随机序列中的下一个数字。

Number 的值确定 Rnd 如何生成伪随机数：

对于任何给定的原始种子，由于对 Rnd 函数的每个后续调用会将之前的数字用作序列中的下一个数字的种子，因此，将生成相同的数字序列。
在调用 Rnd 之前，请使用不带参数的 Randomize 语句来通过基于系统计时器的种子初始化随机数字生成器。

分析程序后，我们可以发现作者并未给Rnd传入任何种子参数。Visual Basic 编译器会且只会从伪随机序列中输出元素，造成结果的偏差和重复，使分布结果严重偏离理想的随机分布。

远比VB的Rnd随机数先进的线性同余方法、平方取中法，甚至是双椭圆曲线确定性随机比特生成器都远远不能生成范围内可接受的随机数。导致其被密码学与计算机深度学习界弃用。

该怎么做？

什么是伪随机数生成器？——数学定义

给定

$P$ - $\left(\mathbb{R},\mathfrak{B}\right)$上的概率分布，其中$\mathfrak{B}$ 是实数集上的 Borel set
$\mathfrak{F}$ - 非空子集$\mathfrak{F}\subseteq\mathfrak{B}$，例如 $\mathfrak{F}=\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}$
$A\subseteq\mathbb{R}$
- 非空集合

称一个函数 $f:\mathbb{N}_1\rightarrow\mathbb{R}$（$\mathbb{N}_1=\left\{1,2,3,\dots\right\}$ 是正整数的一个子集）为一个伪随机生成器，当且仅当： - $f\left(\mathbb{N}_1\right)\subseteq A$ - $\forall E\in\mathfrak{F} \quad \forall 0<\varepsilon\in\mathbb{R} \quad \exists N\in\mathbb{N}_1 \quad \forall N\leq n\in\mathbb{N}_1, \quad \left|\frac{\left\{\#i\in\left\{1,2,\dots, n\right\} : f(i)\in E\right\}}{n}-P(E)\right|< \varepsilon$

如何正确地生成一个随机数

在最近的一场CF的题解中，提到了这篇Blog:Don't use rand(): a guide to random number generators in C++

大概概述一下这篇神仙Blog说了啥：

CF评测机上（以及我们会遭遇的许多Windows评测机上）RAND_MAX很小，只有$32767$
不幸的是，random_shuffle用的也是这个自带的rand()，元素在数组里移动的距离也很小。
rand()使用的伪随机算法是 Linear Congruential Generator (线性同余发生器），在低位循环节很低。

那么如何正确地生成一个随机数呢？神仙blog提供了这样一个东西：库里的mt19937。

这个奇葩的名字来自于它使用的算法——Mersenne Twister算法，以及它用到的质数$2^{19937}−1$。

怎么用呢？

mt19937 rng(seed);
printf("%u\n", rng());

上面那句相当于srand(seed)，然后调用你定义的rng()可以获得一个unsigned int类型的随机数。

如果你要生成 unsigned long long 类型的话，使用mt19937_64即可。

那么怎么替代random_shuffle()呢？使用shuffle()函数，把你的mt19937传进去，像这样：

shuffle(a, a + n, rng);

这样就能让数组内的元素移动足够大的距离——让shuffle更随机了。

附：完整生成随机数代码

#include <cstdio>
#include <chrono>
#include <random>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
    printf("%u\n", rng());
    return 0;
}

## 参考

RabbitHu
Barker E., Kelsey J., Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST SP800-90A, January 2012
Brent R.P., "Some long-period random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, Springer-Verlag.
Knuth D.E.. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3.
Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. ISBN 9780691025469
von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
Peterson, Ivars. The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. 1997. ISBN 0-471-16449-6.
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
Viega J., "Practical Random Number Generation in Software", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.