随机数生成算法

这里介绍了一些随机数生成算法

为何要自己编写随机数算法

显然，无论是哪个语言，都会有随机数生成器，差一点的像C语言这样只有一个rand()，好一点的像C++这样有一整套的random解决方案。那为何我们还要自己编写随机数算法呢？

事情还得从SpaceWar说起。这个游戏中使用了大量的随机数，比如星星的绘制，友军对敌机的选择等。实现的方式就是使用的C++17 STL中的random。但是当我将此游戏移植到Windows下后，发现随机数和在我电脑上的表现不一致。

这使得我的游戏在Windows上会造成一些bug（像是许多友军攻击一个敌机），而在我的电脑上（MacOS），友军对敌军的选择是平均的（因为我当时用的是std::random_device生成随机数，然后将随机数放入std::uniform_int_distribution中产生均匀分布的随机数，但是random_device的实现在不同平台下不一样，可能对结果造成很大的差异）。

这种bug不是因为随机数种子导致的。我和我的朋友尝试了很多次，就是存在上述差异。这时我才知道，上次面试的时候面试官问我随机数生成算法的意义：自己编写的随机数生成算法是可控的，并且可以在各个平台造成一样的结果。

自己实现随机数算法还有一个好处：在一些需要随机生成地图的游戏中（比如Minecraft），同一个种子会生成同一份地图。这个时候不得不使用自己编写的随机数算法来避免不同编译器实现的随机数算法的差异。

线性同余方法（LCG)

这是很常见的一种算法，就一个公式：

$$ X_{n+1} = (aX_{n} + b) \mod{m} $$

这个算法有三个参数a,b,m。LCG的最大周期为m，但是往往达不到。

这个算法严重依赖参数的取值，取得好可以产生很好的结果。而且这个算法算起来也快。

参考博客的第一条中列举了不同编译器对参数的选择，这里只给出C++11minstd_rand()的参数：

a = 48271
b = 0
m = $2^{31}-1$

混合同余法

混合同余法可以看做LCG的加强版：

$$ \begin{cases} x_{n+1} & = (\lambda x_{n} + c) \mod{m} \ result & = \frac{x_{n+1}}{m} ,\ \ result \in [0, 1]) \ \end{cases} $$

这里$\lambda$, $c$和$m$都是参数，$x_0$是种子，$result$是返回的结果，在0~1之间。

这几个参数选择也有要求的，如果随机选的话很容易得到重复序列。

$\lambda$应当是$2^k +1(k > 2)$
$m$应当是$2^n(2 \le n \le 34)$
$c$可以是任何整数

k和n越接近，就会得到越重复的序列。经过我的实验，k=2,n=18和这附近的值表现得都还可以。

这里给了个在线例子，可以进去看一看。这里$x_0$是time(nullptr)的返回值。这里每个点的x坐标是其在数组中的下标（生成了720个数），y坐标则是处理后的随机数（我将随机数乘以480以让其铺满整个屏幕）。

和混合同余法有关的有两个算法，分别是他的低配和高配版：

乘同余法：

$$ \begin{cases} x_{n+1} & = \lambda x \mod{m} \ result &= \frac{x_{n+1}}{m} \ \end{cases} $$

高配版

$$ \begin{cases} x_{n+1} & = (\lambda_1 x_{n} + \lambda_2 x_{n-1} \cdots \lambda_k x_{n+1-k} + c)\mod{m} \ result & = \frac{x_{n+1}}{m} \end{cases} $$

xorshift算法

这个算法是和代码相关的，所以我直接贴代码了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


std::uint32_t x = time(nullptr), y = time(nullptr), z = time(nullptr), w = time(nullptr);

std::uint32_t xorshf32(void) {          // period 2^128 - 1
    std::uint32_t tmp = (x ^ (x << 15));
    x = y;
    y = z;
    z = w;

    w = (w^(w >> 21) ^ (tmp ^(tmp >> 4)));
    return w;
}

这个算法需要四个参数x,y,z,w，并且他的周期很长（这里是$2^{128} -1$），并且只需要异或和位移运算就能得到不同的随机数，具体我也不知道为什么，不过我可以给你这个算法的论文以及wiki上的文献🐶。

这个算法很快，而且也表现出了很好的随机性。

实例网页在这里

1
2
3
4
5
6


std::random_device rd;  // 随机数生成器
std::mt19937 gen(rd()); // 使用梅森素数缠绕算法给其一个初值
std::uniform_int_distribution<> dis(1, 6);  // 均匀分布发生器

for (int n=0; n<10; ++n)
    std::cout << dis(gen) << ' ';   // 使用发生器产生[1, 6]之间服从均匀分布的随机数

这其中的原理如下：

对于我们想要的分布$D(x)$，从概率分布函数的定义来看：

$$ D(x) = \int_{-\inf}^x f(x) \text{d} x $$

其中$f(x)$是其概率密度函数。

我们可以通过解反函数，来得到X到D(x)的映射：

$$ X = D(X)^{-1} $$

比如对于均匀分布，其概率密度函数为：

$$ \begin{cases} \frac{1}{b - a}, & x \in [a, b] \ 0, & 其他 \end{cases} $$

使用概率分布函数的定义公式，可积分得到：

$$ \begin{cases} 0, & x < a \ D(x) = \frac{x - a}{b - a}, & x \in [a, b] \ 1, & x > b \end{cases} $$

那么我们可以反解出x：

$$ x = D(x)^{-1} = (b-a)D(x)+a $$

这时，使用上面说的随机数生成算法生成出随机数d，然后将d替换$D(x)$就可以得到服从分布的x了。

参考博客

LCG(linear congruential generator): 一种简单的随机数生成算法

随机数生成算法【详解，归纳】 - Angel_Kitty - 博客园 (cnblogs.com)

xorshift算法生成随机数的原理是什么？ - 知乎 (zhihu.com)

随机数生成算法

为何要自己编写随机数算法

线性同余方法（LCG)

混合同余法

xorshift算法

其他算法

真正的随机数

得到遵从概率分布的随机数

参考博客

随机数生成算法

相关文章：