C++ 之 伪随机数生成 ＜random＞

C++ 标准库提供了生成随机和伪随机数的类。这些类包括：

• 随机数生成类：生成均匀分布整数序列的伪随机数生成器，包括随机数引擎、随机数引擎适配器以及预定义随机数生成器。
• 随机数分布类：将生成器生成的数字序列转换为遵循特定随机变量分布（如均匀分布、正态或泊松分布）的数字序列的对象。

随机数引擎

随机数引擎可以以种子数据为熵源生成伪随机数。

随机种子：初始化随机数生成器，然后利用算法不停迭代产生随机数。最简单的使用方式便是将其作为第一个随机数产生下一个随机数。

其中线性同余引擎一般地快，并对状态的存储要求非常小。延迟斐波那契生成器在无先进算术指令集的处理器上非常快，但状态存储较为庞大，有时有不太想要的谱特性。梅森缠绕器较慢且拥有较大的状态存储要求，但只要有正确的参数，就会有最长的的不可重复序列，且拥有最想要的谱特性

这里介绍一下线性同余引擎和梅森缠绕器的详细实现过程。

线性同余算法

线性同余算法的实现较为简单，数学表达如下：

但是其参数 a,b,c 需要满足一定条件，这里给出网上的一种C++代码实现如下：

static uint32 prngState = 0;
​
uint32 init_rand(uint32 seed)
{
    //Seed the pseudo-random number generator
    prngState += seed;
​
    //Successful processing
    return SUCCESS;
}
​
uint32 _rand(void)
{
    uint32 value;
​
    //Use a linear congruential generator (LCG) to update the state of the PRNG
    prngState *= 1103515245;
    prngState += 12345;
    value = (prngState >> 16) & 0x07FF;
​
    prngState *= 1103515245;
    prngState += 12345;
    value <<= 10;
    value |= (prngState >> 16) & 0x03FF;
​
    prngState *= 1103515245;
    prngState += 12345;
    value <<= 10;
    value |= (prngState >> 16) & 0x03FF;
​
    //Return the random value
    return value;
}

int32 rand_range(int32 min, int32 max)
{
    int32 value;
​
    //Valid parameters?
    if (max > min)
    {
        //Pick up a random value in the given range
        value = min + (_rand() % (max - min + 1));
    }
    else
    {
        //Use default value
        value = min;
    }
​
    //Return the random value
    return value;
}

该代码摘自知乎博文

梅森缠绕器

梅森缠绕器的实现过程较为复杂

• 第一阶段：初始化，根据随机种子获得初始的梅森旋转链；
• 第二阶段：根据已有梅森旋转链进行旋转算法获取下一次循环的旋转链；
• 第三阶段：根据梅森旋转链计算随机数；

其C++代码实现如下：

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <time.h>

using namespace std;

bool isInit;
int index;
int MT[624];  //624 * 32 - 31 = 19937

void srand(int seed)
{
    index = 0;
    isInit = 1;
    MT[0] = seed;
    for(int i=1; i<624; i++)
    {
        int t = 1812433253 * (MT[i-1] ^ (MT[i-1] >> 30)) + i;
        MT[i] = t & 0xffffffff;   //取最后的32位
    }
}

void generate()
{
    for(int i=0; i<624; i++)
    {
        // 2^31 = 0x80000000
        // 2^31-1 = 0x7fffffff
        int y = (MT[i] & 0x80000000) + (MT[(i+1) % 624] & 0x7fffffff);
        MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
        if (y & 1)
            MT[i] ^= 2567483615;
    }
}
int rand()
{
    if(!isInit)
        srand((int)time(NULL));
    if(index == 0)
        generate();
    int y = MT[index];
    y = y ^ (y >> 11);
    y = y ^ ((y << 7) & 2636928640);
    y = y ^ ((y << 15) & 4022730752);
    y = y ^ (y >> 18);
    index = (index + 1) % 624;
	return y;  //y即为产生的随机数 
}

int main()
{
    srand(0);  //设置随机种子
    int cnt = 0;
    for(int i=0; i<1000000; i++)  //下面的循环是用来判断随机数的奇偶概率的 
    {
        if(rand() & 1)
            cnt++;
    }
    cout<<cnt / 10000.0<<"%"<<endl;
    return 0;
}

该代码摘自it610网，该博文包含原理解析。

随机数引擎适配器

随机数引擎适配器生成以另一随机数引擎为熵源的伪随机数，以随机数引擎为基础产生过更为多样性的随机序列。

预定义随机数生成器

如果有需要可以根据上述的随机数引擎和随机数引擎适配器构建属于自己的随机数生成器。同时C++的标准库也提供了需要经典的随机数生成器如下：

随机数分布

处理随机数生成器的输出，以使得输出结果按照定义的统计概率密度函数进行分布。

其他工具

std::uniform_random_bit_generator ：均匀随机位生成器是函数对象，它返回无符号整数值，并使得每个值在可能结果的范围中拥有（理想上）相等的被返回概率。

std::random_device ：使用硬件熵源的非确定随机数生成器

std::generate_canonical ： 使通过随机数生成器获得的数据均匀分布在 [0, 1) 上

seed_seq ：通用的偏差消除的混淆种子序列生成器，通过提高种子的多样性降低随机序列的重复出现