mt19937
这是 c++11 的新的随机数生成器，是rand（）远远不能相比的
rand（）
这个随机数本身有一定限制，生成的随机数范围貌似在 （$0,32767$）（dev-c++）中，这有时根本不够用，有时还要手动 $\times 10000……$ 但这样也会有局限性，因为数据的随机性被破坏了
所以聪明的人类发明了新的随机数生成器：：
mt19937
（密集恐惧症者自动跳过。。。）
Mersenne Twister 算法译为马特赛特旋转演算法，是伪随机数发生器之一，其主要作用是生成伪随机数。此算法是 Makoto Matsumoto （松本）和 Takuji Nishimura （西村）于 $1997$ 年开发的，基于有限二进制字段上的矩阵线性再生。可以快速产生高质量的伪随机数，修正了古老随机数产生算法的很多缺陷。Mersenne Twister 这个名字来自周期长度通常取 Mersenne 质数这样一个事实。常见的有两个变种 Mersenne Twister MT19937 和 Mersenne Twister MT19937-64。
Mersenne Twister 算法的原理：Mersenne Twister 算法是利用线性反馈移位寄存器 ( LFSR ) 产生随机数的，LFSR 的反馈函数是寄存器中某些位的简单异或，这些位也称之为抽头序列。一个 $n$ 位的 LFSR 能够在重复之前产生 $2^n-1$ 位长的伪随机序列。只有具有一定抽头序列的LFSR才能通过所有 $2^n-1$ 个内部状态，产生 $2^n - 1$ 位长的伪随机序列，这个输出的序列就称之为 $m$ 序列。为了使 LFSR 成为最大周期的 LFSR，由抽头序列加上常数 $1$ 形成的多项式必须是本原多项式。一个 $n$ 阶本原多项式是不可约多项式，它能整除 $x^{(2\times n-1)}+1$ 而不能整除 $x^d+1$，其中 $d$ 能整除$2^n-1$。例如 $(32,7,5,3,2,1,0)$ 是指本原多项式 $x^{32}+x^7+x^5+x^3+x^2+x+1$，把它转化为最大周期LFSR就是在LFSR的第 $32,7,5,2,1$ 位抽头。利用上述两种方法产生周期为 $m$ 的伪随机序列后，只需要将产生的伪随机序列除以序列的周期，就可以得到 $(0,1)$ 上均匀分布的伪随机序列了。
Mersenne Twister 有以下优点：随机性好，在计算机上容易实现，占用内存较少 ( mt19937 的 C 程式码执行仅需 $624$ 个字的工作区域 )，与其它已使用的伪随机数发生器相比，产生随机数的速度快、周期长，可达到 $2^{19937}-1$，且具有 $623$ 维均匀分布的性质，对于一般的应用来说，足够大了，序列关联比较小，能通过很多随机性测试。
$2^{19937}-1$
实战检测
mt19937模板
#include<iostream>
#include<random>
#include<cstdio>
using namespace std;
int main(){
mt19937 mt_rand(time(0));
cout<<mt_rand()<<endl;
return 0;
}//数据生成
#include<iostream>
#include<random>
#include<cstdio>
using namespace std;
const int mo=31331;//由于rand（）的区间过小但又要保证公平的数据范围所以模数较小
int main(){
freopen("11.txt","w",stdout);
mt19937 mt_rand(time(0));
srand(time(0));
for(int i=0;i<100100;i++){
cout<<mt_rand()%mo<<" "<<rand()%mo<<endl;
}
return 0;
}//检验
#include<iostream>
#include<random>
#include<cstdio>
using namespace std;
int a,b;
const int u=33332;
bool a_a[u],b_b[u];
long long s_a=0,s_b=0;//比对两种随机数生成中有多少次重复生成
int main(){
freopen("11.txt","r",stdin);
freopen("22.txt","w",stdout);
int c=100000;
while(c--){
scanf("%d %d",&a,&b);
if(a_a[a])s_a++;
if(b_b[b])s_b++;
a_a[a]=1;
b_b[b]=1;
}
cout<<s_a<<" "<<s_b<<endl;
return 0;
}下面放几组实测数据
69950 70100
69960 70039
69989 70149
69928 70102
70010 70134
可以看到即使 mt19937 的大区间优势没了，生成的随机数重复次数也比 rand（） 少，由此可见mt19937 的强大性能
值得一提的是如果数据生成很多例如10000000，他们的输出会相同或非常接近
mt19937 在 c++11 后才能使用，他的种种性能还需尝试
