随机数：基于mt19937的随机数

经验分享区
1

std::mersenne_twister_engine

std::mersenne_twister_engine

定义于头文件 <random>
template<class UIntType, std::size_t w, std::size_t n, std::size_t m, std::size_t r,UIntType a, std::size_t u, UIntType d, std::size_t s,UIntType b, std::size_t t, UIntType c, std::size_t l, UIntType f

mersenne_twister_engine 是一个基于梅森旋转算法的随机数引擎。它生成高质量，但非密码学安全的，类型为 UIntType 的无符号整数随机数，范围在 [0, 2w) 区间内。

模板参数

UIntType - 生成器生成的结果类型。如果这不是 unsigned short、 unsigned int、 unsigned long 或 unsigned long long 之一，则效果未定义。
w - 决定引擎生成的值范围的 2 的幂
n - 递推的阶数
m - 中间字，用于定义状态的递推关系中的偏移量
r - 低位掩码的位数，也称为扭曲值
a - 条件异或掩码，即有理标准型扭曲矩阵的系数
u, d, s, b, t, c, l - 位扰乱（tempering）矩阵的第 1 至第 7 个分量
f - 初始化乘数

如果违反以下任何限制，则程序是非良构的

  • m 在 [1,n] 范围内。
  • 以下表达式均为 true
  1. w >= 3
  2. w >= r
  3. w >= u
  4. w >= s
  5. w >= t
  6. w >= l
  7. w <= std::numeric_limits<UIntType>::digits
  • 给定 (1u << w) - 1u 为 w1，以下表达式均为 true
  1. a <= w1
  2. b <= w1
  3. c <= w1
  4. d <= w1
  5. f <= w1

生成器属性

mersenne_twister_engine 的状态的大小为 n，每个状态由类型为 result_type 的 n 个值的序列 X 组成。X_j 代表 X 的第 j mod n 个值（从 0 开始）。

给定以下按位运算符号

mersenne_twister_engine 的转移算法（ TA(xi) ）定义如下

  1. 将 X_i-n 的高 w - r 位与 X_i+1-n 的低 r 位连接，得到一个无符号整数值 Y。
  2. 设 y 为 a·(Y bitand 1)，并将 X_i 设置为 X_i+m−n xor (Y rshift 1) xor y。

mersenne_twister_engine 的生成算法（ GA(xi) ）定义如下

  1. 设 z_1 为 X_i xor ((X_i rshift u) bitand $d_)。
  2. 设 z_2 为 X_i xor (((X_i lshift s) mod 2w) bitand b)。
  3. 设 z_3 为 X_i xor (((X_i lshift t) mod 2w) bitand c)。
  4. 设 z_4 为 z_3 xor (z_3 rshift l)。
  5. 交付 z_4 作为结果（即 GA(x_i)=z_4 ）。

以上内容来自

示例

#include <bits/stdc++.h>
using namespace std;
int main()
{
    auto seed = time(nullptr);
    mt19937 mt(seed);
    cout << mt();
    return 0;
}

:以上代码类似于

#include <bits/stdc++.h>
using namespace std;
int main()
{
    srand(time(nullptr));
    cout << rand();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cout << random_device()();
    return 0;
}

示例2

#include <bits/stdc++.h>
using namespace std;
int main()
{
    auto seed = random_device()();
    mt19937 mt(seed);
    cout << uniform_int_distribution<int>(1, 100)(mt);
    return 0;
}