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

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

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

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

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

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

首先，移位寄存器包括兩個(gè)部分

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

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

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

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

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

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

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

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

式加1必須是一個(gè)本原多項(xiàng)式，也就是說這個(gè)多項(xiàng)式不可約，比如。

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

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

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

很好的隨機(jī)性。

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

的MT19937-32只需要用到32位，那么為什么要選擇周長為的算法呢？ 那是因?yàn)檫@樣做隨機(jī)性很好。

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

代碼：

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