乱数ライブラリー

M系列

線形合同法で生成する乱数列 x 0 underline {x_0} , x 1 underline {x_1} , x 2 underline {x_2} , dotsaxis の欠点は、漸化式が線形・非線形を問わず、多次元疎結晶構造を有することである。これは乱数を生成する一般形である式.線形合同法(1)が一次の漸化式であることによる。そこで高次漸化式による乱数生成法が研究されており、その中で代表的なものがM系列法である。M系列は線形最大周期列または最大長系列とも呼ばれる、次式による1ビットの系列のことである。

x n = a 1 x n - 1 + a 2 x n - 2 + + a i x n - i + + a p x n - p x_n=a_{1}x_{n-1}+a_{2}x_{n-2}+…+a_{i}x_{n-i}+…+a_{p}x_{n-p}
a p = 0 or 1 a_p=0or1


ここで + は排他的論理和を表し、実際には計算を高速化するため

x n + p = x n + q + x n     ( p > q > 0 ) x_{n+p}=x_{n+q}+x_n(p>q>0)


を用いる。式(2)の1回の演算で値が0か1の乱数1個を生成する。ただし式(2)に対して p underline {p} q underline {q}

f ( x ) = 1 + x p + x q f(x)=1+x^p+x^q


が既約多項式となるように選択する。式(3)はガロア体 GF ( 2 ) GF(2) であり、このことは p underline {p} q underline {q} の値の選択に関係があるが、本サイトで扱う想定の範囲を超えるのでここでは割愛する。M系列の最大周期は 2 p - 1 2^{p-1} であり、0と1の出現確率はほぼ同等である。




▲このページのトップに戻る