乱数ライブラリー

乗算合同法

乗算合同法とは、非負の整数 a a , b b を与え、以下の合同式によって乱数列を発生させる方法である。

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


すなわち乗算合同法は2数の積をある数で除して、その剰余を採る方法である。式(1)により乱数列 x 0 underline {x_0} , x 1 underline {x_1} , x 2 underline {x_2} , dotsaxis を発生させる。 a a は定数、 M M は係数を示し、いずれも整数である。乗算合同法の周期は M M に等しくすることはできない。したがって a a の値をどのように選んでも、最大周期は M M よりも小さくなる。この乗算合同法で生成した乱数列については以下のような周期の性質がある。なお、具体的な数値は林知己夫監修の『初等情報処理講座(5)乱数の知識』(森北出版)を引用した。

乱数列の最大周期は M M 2 p ( p > 3 ) 2^p(p>3) のとき

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


によって生成される乱数列の最大周期は

a = 3.5     ( mod 8 ) a=3.5(mod 8)
b = odd number b=odd number


に対して 2 p - 2 2^{p-2} となる。

乱数列の最大周期は M M 10 p ( p > 3 ) 10^p(p>3) のとき

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


によって生成される乱数列の最大周期は

a = 3,13,27,37,53,67,77,83,117,123,133,147,163,173,187,199     ( mod 200 ) a=3,13,27,37,53,67,77,83,117,123,133,147,163,173,187,199(mod 200)
b = 1,3,7,9     ( mod 10 ) b=1,3,7,9(mod 10)


に対して 10 p - 2 5!underline {_} 10^{p-2} となる。




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