next up previous
Next: 指数乱数列 Up: 疑似乱数の作成法 Previous: 線形合同法

M系列乱数

合同法乱数が多次元疎結晶構造を有するのは、乱数列を生成するのが1次の漸化式であることによる。 数列 tex2html_wrap_inline308 を生成する漸化式が線形であるか非線形であるかを問わず、その次数が1である限り、 tex2html_wrap_inline308 は必ず多次元疎結晶構造を有する。 そこで、高次の漸化式で乱数を生成する方法がいくつか研究されてきている。

そのうちで現在までに理論的性質が比較的よくわかっているのが、いわゆるM系列を用いて乱数列を構成する方法であり、演算としては、合同法の乗算(および加算)に対して、排他的論理和(Exclusive OR)をとる論理演算を用いる。 EORをとる演算は、原理的には乗算よりも速くできるので、次数は高くても項数が少ない漸化式を用いれば、合同法よりも速く乱数を発生することも可能である。

M系列乱数は0と1からなる系列、すなわち1ビットの系列である。 しかし乱数列として普通使われるのは、もっと桁数が大きい系列である。 そこでM系列を基にして、 tex2html_wrap_inline312 ビットの2進数の系列 tex2html_wrap_inline314 を次のように構成する。

equation35

ここに tex2html_wrap_inline316 は互いに異なり、tに無関係な定数である。

tex2html_wrap_inline320tex2html_wrap_inline322 の位相を適当にずらしたものを各ビットに配置して構成される。 つまり、 tex2html_wrap_inline320 の各ビット位置に現れる数列は、同一の漸化式によって生成される。 したがって、次の漸化式を用いることによって、 tex2html_wrap_inline320 を高速に生成することができる。

equation40

ただし、 tex2html_wrap_inline328 はビットごとの繰り上がりなしの足し算を表し、多くの計算機に備わっている排他的論理和(EOR)の演算機能を使うことによって高速に処理できる。 特に特性多項式fが3項式

equation45

の場合には

equation47

となり、1回の排他的論理和の演算によって乱数1個が発生できるので、たいへん高速になる。

M系列による疑似乱数は、線形合同法よりはるかに周期の長い乱数が得られる。 また、初期値を正しく選べば多次元分布もよい。 ただし、一つの原始多項式で生成できるM系列は1通りしかないので、整数の各ビットができるだけ離れた部分を走るように初期設定をしなければならない。 今回のシミュレーションでは、各 tex2html_wrap_inline298 を32ビットの符号なし整数として、初期値 tex2html_wrap_inline334 の選び方は次のようにした。

eqnarray52

のように2進表示し tex2html_wrap_inline336 から tex2html_wrap_inline338 までのビットは任意に選ぶ。 ここでは線形合同法乱数の最上位ビットを使っている。残りのビットは tex2html_wrap_inline340 を使って生成する。



2000年09月07日 (木) 20時25分23秒 JST