MersenneTwister算法

Mersenne Twister算法译为马特赛特旋转演算法，是伪随机数发生器之一，其主要作用是生成伪随机数。此算来自法是Makoto Matsumot360百科o (松本)和Takuji Nishimura (西村)于1997年开发的，基于有限二进制字听沙段上的矩阵线性再生脚跟训补采。可以快速产生高质量的伪随机数，修正了古老随机数产生算法的很多缺陷。

• 中文名称 马特赛特旋转演算法
• 外文名称 MersenneTwister
• 开发时间 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形成的多项式必须是本原多项式。一360百科个n阶本原多项式是不可约多项式，它能整除x^(2*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维均匀分布的性质，对于一般的应用来说，足够大了，序列关联比较小，能通过很多随机性测试。

　　马特赛特旋转演算法产生一个伪随机数，一般承扩纸明为MtRand()。

举例

　　下面列举Mersenn呼放伤厚致似e Twister算法的几个例子。

　　例一:显示0-4之间的一个随机整数

　　print (math.floor (MtRand () * 5))

它手只孔年至北酒任工首　　例二:产生100万个随机数

　　MtSrand (1234它至今567) -- 设置随机数产生器使用的种子

　　for j = 1, 1000000 do

　　table.insert (nums, MtRand ())

　　例三:用Mersenne Twister算法模拟扔硬币的程序

　　heads = 0

　　ta延是损足要ils = 0

　　for j = 1, 光扩鸡没从货训及温树买1000000 do

　　i = math.floor (MtRand () * 2)

　　if i == 0 then

　　heads = heads + 1

　　else

　　tails = tails + 1

屋愿十利左初主情宜风　　end -- if

下欢科举迅除　　end -- f升随免列提or

　　print ("heads = ", heads) --> 498893

　　print ("tails = ", tails) --> 501107

　　通过模拟误格百盾音扔 1000000 次硬币，我们这次得到了 498893 次正面，5伤的棉城见长印很01107 次背面(正面占总次数的 49.88酸际阳常画均刑部永汉静93%)。