乱数ライブラリー

線形合同法

線形合同法とは、疑似乱数列(以下は乱数列と表記)を生成するアルゴリズムの1つであり、その一般形は次式で表される。

x n + 1 = a 0 x n + a 1 x n - 1 + + a i x n - i + + a j x n - j + b     ( mod M ) x_{n+1}=a_{0}x_{n}+a_{1}x_{n-1}+dotsaxis +a_{i}x_{n-i}+dotsaxis +a_{j}x_{n-j}+b(mod M)

ただし i = 1 underline {i=1} , 2 2 , dotsaxis であり、 a i underline {a_i} , b b , M M はいずれも非負の整数で a i < M a_i<M かつ b < M b<M である。ここで M M は法と呼ばれる整数値であり、 ( mod M ) (mod M) M M の剰余である。当該漸化式で得られる乱数列は常に M M より小さい非負の整数値となり、乱数の周期や統計的性質は定数 x i underline {x_i} , a i underline {a_i} , b b , に依存する。

式(1)から生成される非負整数列 x n underline {x_n} の周期は M M より小さくなるため、 M M は出来るだけ大きい数がよい。また線形合同法では周期が M M に出来るだけ等しくなることが望ましい。実際の M M の選択では、計算機の能力と使用するプログラム言語に合わせる必要がある。 d d 進法 p underline {p} 桁であれば

M = d p M=d^{p}

である。しかし式(2)を使用した場合には、 x n underline {x_n} の下位の桁についてはランダム性が低いため、下位の桁は乱数列として使用しないようにする。

定数 a a 0 < a < M 0<a<M であり、非負整数列 x n underline {x_n} の周期が出来るだけ長く、かつランダムになるように選択する。定数 a a により乱数の精度が決定される。法 M M 、定数 a a 及び加数 b b それぞれの値と、数列の初期値に使用する値はバランスが取れていないと、ランダム性が低い乱数列が発生する。そのため線形合同法で発生させた乱数列は、乱数の検定を行う必要がある。



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