c++随机数引擎全解

看这个的默认了解基础的随机数生成。

        使用经典线性同余算法（linear congruential method），大部分随机数的生成使用这种方法，经典代码如下：

#include 
#include 
#include 
#include 
using namespace std;

int main(){
    srand(time(0));
    cout< 
        其中srand()传入种子为 unsigned int 类型，随机数种子的最小单位为秒，注意如果使用时间作为种子时，要让不同的随机数生成间隔超过一秒，或者自己生成随机数。
 
        本方法现在通常作为随机数种子生成器。
 
 
 
生成范围：0~32767(2^15)
 
 
C++(random) 
mt19937（c11） 
        使用梅森旋转生成器，属于"mersenne_twister_engine"内容，由于是最为常用的随机数生成器，因此首先介绍。
 
        梅森旋转生成器19937来自于周期预估长度高达19937位，理论足够包含整个宇宙粒子数，因此发明者骄傲的命名为19937，mt为Mersenne Twister的简写。用于生成32位大小的随机数，c++同时提供了64位的生成方法mt19937_64。其中19937为梅森素数，恰好位于第24位，也即2^19937 - 1 为梅森素数。这项成果被发表在1971年的一篇文章中。
 
        简单例子：
 
#include 
#include 
#include 
#include 
using namespace std;

int main(){
    random_device rd;  //Will be used to obtain a seed for the random number engine
    mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
    uniform_int_distribution distrib(1, 27);
    for (int n = 0; n <= 7; ++n)
        std::cout << distrib(gen) << ' ';
    cout << endl;
    return 0;
}
 
 
 
 这里random_device同样可以作为随机数生成来使用，但他是一种面向随机过程的随机生成器，部分设备并不支持这些功能，有些使用伪随机数进行实现，有些干脆返回空白或者异常，因此通常推荐作为种子使用或者处理这种异常。他将生成一个均匀分布的随机数。笔者对随机过程了解不深，推荐读者自己查询学习本科内容。
 
 
注意：除c11外其他版本很可能不支持这种功能。
 
 
这里distrib前半部分用于指定分布类型，这里指定为整型中的int类型。
 
梅森随机引擎提供了多项参数接口如下：
 
 
 
member constant
definition
notes
word_size
32
The number of bits of each word in the state sequence.
state_size
624
The number of elements in the state sequence (degree of recurrence).
shift_size
397
The shift size used on twists to transform the values.
mask_bits
31
The number of bits that mark the separation point of words on each twist.
xor_mask
0x9908b0df
The XOR mask applied as the linear function on each twist.
tempering_u
11
The shift size of parameter u used in the tempering process of the generation algorithm.
tempering_d
0xffffffff
The XOR mask used as parameter d in the tempering process of the generation algorithm.
tempering_s
7
The shift size of parameter s used in the tempering process of the generation algorithm.
tempering_b
0x9d2c5680
The XOR mask used as parameter b in the tempering process of the generation algorithm.
tempering_t
15
The shift size of parameter t used in the tempering process of the generation algorithm.
tempering_c
0xefc60000
The XOR mask used as parameter c in the tempering process of the generation algorithm.
tempering_l
18
The shift size of parameter l used in the tempering process of the generation algorithm.
initialization_multiplier
1812433253
The initialization multiplier used to seed the state sequence when a single value is used as seed.
default_seed
5489u
The default seed used on construction or seeding.
 
 这里提到一种XOR技术，推测是指Xor-shift随机数生成法。具体数论含义暂且不表，简单叙述为一种通过移位取异或的方式获得一个随机值的方式，代码如下(wiki)：
 
#include 

struct xorshift32_state {
  uint32_t a;
};


uint32_t xorshift32(struct xorshift32_state *state)
{
	
	uint32_t x = state->a;
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return state->a = x;
}

struct xorshift64_state {
  uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return state->a = x;
}

struct xorshift128_state {
  uint32_t x[4];
};


uint32_t xorshift128(struct xorshift128_state *state)
{
	
	uint32_t t  = state->x[3];
    
    uint32_t s  = state->x[0];  
	state->x[3] = state->x[2];
	state->x[2] = state->x[1];
	state->x[1] = s;

	t ^= t << 11;
	t ^= t >> 8;
	return state->x[0] = t ^ s ^ (s >> 19);
}

 
以一种通xuan俗huan的方式来解释，一个数字的首部和尾部是不可预测的，通过将其取异或值更改其中的一部分留下另一部分产生的值应当是更加不可预测的（周期长）。当然这是胡扯，建议看原论文或wiki。
 
了解了上面这些，我们可以小小的拓展一下，介绍所有的c11随机数分布与引擎：
 
随机数引擎 
default_random_engine                根据编译器设置的默认引擎类型的类型别名
 
linear_congruential_engine           LCG线性同余法随机数生成器
 
下属类：
 
minstd_rand0                                乘数为16807，模为2147483647，偏移量为0
 
minstd_rand                                  乘数为48271，模为2147483647，偏移量为0
 
这些数字都不是质数
 
mersenne_twister_engine             梅森旋转随机数生成器
 
下属类：
 
mt19937                                         使用的是梅森素数
 
mt19937_64                                   64位版本
 
subtract_with_carry_engine           带进位减法随机数生成器，后面我们会介绍
 
下属类：
 
ranlux24_base                                32位无符号借位减法生成器
 
ranlux48_base                                64位
 
是最后一个随机数生成器，总计3种随机数生成器。
 
以下包含引擎的内存处理与参数传递机制，笔者不甚了解。
 
discard_block_engine                     引擎适配器，丢弃引擎底层结果。用引擎类型、块大小和旧块大小来参数化。
 
independent_bits_engine                引擎适配器，用于指定位数的随机数，进行参数化。
 
shuffle_order_engine                       引擎适配器，返回底层引擎的参数。
 
如果有懂这三块内容伙伴欢迎分享。
 
随机数分布 
        可以参考这里
 
 - C++ Reference"> - C++ Referencehttps://www.cplusplus.com/reference/random/
 
带进位减法(Subtract with carry) 
        众所周知，LCG线性同余法有个缺陷是会形成ρ，于是我们通常会拼命扩大这个ρ的环大小。同时我们知道一种判环方法为Floyd法。带进位减法就是从这个思想中出现的，通过快慢机来扩大ρ的大小。公式如下：
 
= 0) end{aligned} right."  src="https://latex.codecogs.com/gif.latex?x%28i+1%29%20%3D%202*x%28i%29%20-%20x%28R%29%20-%20x%28S%29%20-%20cy%28i-1%29%20%5C%5C%20cy%28i%29%20%3D%20%5Cleft%5C%7B%20%5Cbegin%7Baligned%7D%201%20%2C%20if%28f%28x%29%20%3C%200%29%20%5C%5C%200%20%2C%20if%28f%28x%29%20%3E%3D%200%29%20%5Cend%7Baligned%7D%20%5Cright." />
 
        这里0