mt19937

概述

被松本先生和西村先生于 1998 年设计出来。

是一个生成高质量，分布均匀的随机数的算法（虽然在 C++11 当中是一个 class）

首先我们可以搞到 rand() 的实现：

static unsigned long next = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    next = next * 1103515245 + 12345;
    return((unsigned)(next/65536) % 32768);
}

void mysrand(unsigned seed) {
    next = seed;
}
// 利用线性同同余法实现

发现这个玩意儿的循环节只有 \(32767\)。

什么意思？

就是在当你需要生成很大的随机数的时候（比如模拟退火），他很容易生成的时候循环出现某个数。

回来看 mt19937。

为啥要叫 mt19937 呢？

因为它的循环节是 \(2^{19937}-1\)，也就是梅森（mt）数。

用它，你可以获得一些很有质量的，分布均匀的随机数。

使用方式

用法如下：

#include<random>
#include<iostream>
using namespace std;

int main(){
    std::random_device seedgen; // 非确定的均匀随机位生成器
                                // 在熵池耗尽之前非常高效
                                // 所以用来当种子生成器
                                // NOIP 考场最好不用？
    // 这个东西似乎在 32bit 上会寄（生成同样的数据），
    // 但是 win下的 msys2 64bit 没有事情，NOI linux 还没有测试。

    std::mt19937 Myrand(seedgen()); // 自定义一个 mt19937 类型的生成器

    std::uniform_int_distribution<long long>RangeInt(0,114514); // 指定整数范围
    std::uniform_real_distribution<long double>RangeReal(0.0,1919810.0); // 指定实数范围

    cout<<Myrand()<<endl; // 没有范围,但是 mt19937 是 32 位的，所以会在 int 以内。
    cout<<RangeInt(Myrand)<<endl; // 有范围的均匀整数
    cout<<RangeReal(Myrand)<<endl; // 有范围的均匀实数
    return 0;
}

还有一个用于 64 位整数版的 mt19937 ：mt19937_64

用法一样，复杂度均摊 \(\text{O}(1)\)。

除了 mt19937，<random> 里面还有很多有意思的东西，可以翻一翻 cpp ref，或者小波的洛谷日报。

---

最后更新: May 9, 2023