本文關(guān)鍵詞：線性移位寄存器，由筆耕文化傳播整理發(fā)布。

今天主要是來研究梅森旋轉(zhuǎn)算法，它是用來產(chǎn)生偽隨機數(shù)的，實際上產(chǎn)生偽隨機數(shù)的方法有很多種，比如線性同余法，

平方取中法等等。但是這些方法產(chǎn)生的隨機數(shù)質(zhì)量往往不是很高，而今天介紹的梅森旋轉(zhuǎn)算法可以產(chǎn)生高質(zhì)量的偽隨

機數(shù)，并且效率高效，彌補了傳統(tǒng)偽隨機數(shù)生成器的不足。梅森旋轉(zhuǎn)算法的最長周期取自一個梅森素數(shù)，

由此命名為梅森旋轉(zhuǎn)算法。常見的兩種為基于32位的MT19937-32和基于64位的MT19937-64。

由于梅森旋轉(zhuǎn)算法是利用線性反饋移位寄存器（LFSR）產(chǎn)生隨機數(shù)的，所以我們先來認識線性反饋移位寄存器。

首先，移位寄存器包括兩個部分

    （1）級，每一級包含一個比特，比如11010110是一個8級的移位寄存器產(chǎn)生的

    （2）反饋函數(shù)，線性反饋移位寄存器的反饋函數(shù)是線性的，非線性反饋移位寄存器的反饋函數(shù)是非線性的

一個，當(dāng)然這個最大周期跟反饋函數(shù)有很大關(guān)系，線性反饋函數(shù)實

際上就是這個級的移位寄存器選取“某些位”進行異或后得到的結(jié)果，這里的“某些位”的選取很重要，得到線性反饋

函數(shù)之后，把這個移位寄存器的每次向右移動一位，把最右端的作為輸出，把“某些位”的異或結(jié)果作為輸入放到最左

端的那位，這樣所有的輸出對應(yīng)一個序列，這個序列叫做M序列，是最長線性移位寄存器序列的簡稱。

上面“某些位”的選取問題還沒有解決，那么應(yīng)該選取哪些位來進行異或才能保證最長周期為，這是一個很重要

的問題。選取的“某些位”構(gòu)成的序列叫做抽頭序列，理論表明，要使LFSR得到最長的周期，這個抽頭序列構(gòu)成的多項

式加1必須是一個本原多項式，也就是說這個多項式不可約，比如。

下面以一個4位的線性反饋移位寄存器為例說明它的工作原理。

如果的值分別是1 0 0 0，反饋函數(shù)選取，那么得到如下序列

可以看出周長為15。在這一個周期里面涵蓋了開區(qū)間內(nèi)的所有整數(shù)，并且都是沒有固定順序出現(xiàn)的，有

很好的隨機性。

之前說過，梅森旋轉(zhuǎn)算法的周期為，那么說明它是一個19937級的線性反饋移位寄存器，實際上基于32位

的MT19937-32只需要用到32位，那么為什么要選擇周長為的算法呢？ 那是因為這樣做隨機性很好。

梅森旋轉(zhuǎn)算法是基于線性反饋移位寄存器的一直進行移位旋轉(zhuǎn)，，周期為一個梅森素數(shù)，果然是名副其實。

代碼：

  本文關(guān)鍵詞：線性移位寄存器，由筆耕文化傳播整理發(fā)布。