乱数ライブラリー

混合合同法

混合合同法は、最大周期を長くするために乗算合同法を改良したものである。混合合同法は以下の漸化式によって乱数列を発生させる。

x n + 1 = ax n + c     ( mod M ) x_{n+1}=ax_n+c(mod M)
x 0 = b x_0=b


すなわち、 ab + c     ( mod M ) ab+c(mod M) について x 1 underline {x_1} とし、さらに ax 1 + c     ( mod M ) ax_1+c(mod M) x 2 underline {x_2} とする。順次に式(1)より乱数列 x 0 underline {x_0} , x 1 underline {x_1} , x 2 underline {x_2} , dotsaxis を発生させる。 a a , b b , c c , x n underline {x_n} ( n = 1 n=1 , 2 2 , dotsaxis )は0から M - 1 M-1 までの整数である。混合合同法で生成した乱数列は最大限 M M の周期を持ち、実際は M M よりも小さくなる。そこで乗算合同法と同様にできるだけ周期が長くなるように法 M M 、定数 a a 及び加数 c c を決定する。この混合合同法で生成した乱数列については以下のような周期の性質がある。

まず、

x n + 1 = ax n + c     ( mod 2 p ) x_{n+1}=ax_n+c(mod 2^p)
x 0 = b x_0=b


によって生成される乱数列 x 0 underline {x_0} , x 1 underline {x_1} , x 2 underline {x_2} , dotsaxis の最大周期は、

a = 1     ( mod 4 ) a=1(mod 4)
c = 1     ( mod 2 ) c=1(mod 2)


のとき 2 p underline {2^p} である。これは式(1)で M = 2 p M=2^p のとき周期が M M であることを意味する。すなわち M M 以上の周期の乱数列を生成することはできない。また初期値 b b は最大周期とは無関係である。

次に、

x n + 1 = ax n + c     ( mod 10 p ) x_{n+1}=ax_n+c(mod 10^p)
x 0 = b x_0=b


によって生成される乱数列 x 0 underline {x_0} , x 1 underline {x_1} , x 2 underline {x_2} , dotsaxis の最大周期は、

a = 1     ( mod 20 ) a=1(mod 20)
c = 1,3,5,7,9     ( mod 10 ) c=1,3,5,7,9(mod 10)


のとき 10 p underline {10^p} である。これは式(3)の時と同様、式(1)で M = 10 p M=10^p のとき周期が M M であることを意味する。すなわち M M 以上の周期の乱数列を生成することはできない。また初期値 b b は最大周期とは無関係である。




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