第 4 章 整数ロジスティック写像と撹拌演算による乱数生成 48
4.3 提案法の効果
第4章 整数ロジスティック写像と撹拌演算による乱数生成
4.3. 提案法の効果
表 4.1: 提案法とMTの連検定と組み合わせ検定の結果 Run test Combination test c .30 .40 .50 .60 .70 .30 .40 .50 .60 .70 ν 19 14 12 14 19 12 13 13 13 12
χν χ0
MT .47 .84 .77 .63 .55 .53 .41 .56 .63 .48 提案法 .58 .42 .92 .34 .55 .19 .36 .30 .30 .36
の結果χν/χ0である．νはχ二乗検定における自由度である．提案法はMTと 同様，多重化することがなくても，検定に合格する良好な擬似乱数を生成でき ることを示している．
4.3.2 生成速度
計算速度は，プロセッサーの種類とプログラミング方法やコンパイラの種類 によるが，ここにノートPCと8ビットマイクロコントローラでの計算例を表 4.2 に示す．ここに，N は計算精度(bit)，Sは乱数の生成速度であり，PCは Genuine Intel(R) 1.50GHzを，MCはATmega168V 8MHzを用いた．
表 4.2: 計算精度と乱数生成速度
N 32 64 96 128 160 192 224 256
S
PC(Gbps) 1.9 1.0 .71 .56 .51 .43 .36 .31 MC(Kbps) 262 166 125 101 80 67 60 54
提案法の乱数生成は式(4.1)の計算以外に数回のXOR演算だけである．従っ て，2値系列生成法に比べ，ほぼ計算精度（N）倍の乱数生成速度が得られた．
また，計算能力の低い8ビットのマイクロコントローラでの乱数生成が可能で あることを確認できた．
4.3.3 初期状態の微小な差に対する敏感な反応
第3章で議論したように，整数ロジスティック写像から生成される軌道はあ る初期値制約を満たせば，初期値敏感性を有している．当然，カオスから生成
第4章 整数ロジスティック写像と撹拌演算による乱数生成
された擬似乱数も，初期状態に敏感に反応すると思われる．ここでは，提案法 とMTに対し，微小の差を持つ2つの初期状態から生成した系列の間のハミン グ距離を計測して，初期状態の微小な差に対する反応の強さを測る実験を行う．
方法
2つの系列の間が無関係であればそのハミング距離hを計測に使われるビッ ト数nで割った値H（H =h/n）がnの数が大きくなると，0.5に近づく．従っ て，2つの微小の差しか持たない初期状態から生成した系列の間から得られた Hの値が0.5の近傍に収束されるまでのnの値を観測することにより，初期状 態の微小な差に対する反応の強さを見ることができる．
MTは624ワードの内部状態を有し，内部状態の更新はワード（32ビット）
単位で行われている[10]．ランダムに決まった内部状態①の任意のワードにあ る1ビットを反転した内部状態②と，乱数を生成しながら，ハミング距離hを 計算し，nとHを出力する．
非周期状態長が十分に長く得られるように，ここでは，N = 128ビットで式
(4.1)を計算する（L128）．ランダムに決まった初期状態①と，1ビット反転さ
れた内部状態②と，MTと同じように，（式(4.18)のd0 ∼d127の128ビット）ハ ミング距離hを計算し，nとHを出力する．同時に，提案法（式(4.12)）によ り，①と②から生成した擬似乱数Rtについても，ハミング距離hを計算し，n とHを出力する．
以上の実験を100回行い，Hの推移状態などを比較する．
手順
S1．ランダムに初期状態①を決め．
S2．状態①の任意の位置にある1ビットを反転して状態②に．
S3．初期状態①と②からそれぞれ乱数を出力して，hを計算し，適当なとこ ろにnとHを出力する．
S4．Hが0.5の近傍に収束したら，終了する（本実験はn = 3.2×109まで）．
S5．S1∼S4を100回行う．
4.3. 提案法の効果 結果
図4.2(a),(b),(d)にそれぞれL128とMTと提案法の計測結果を示す．横軸は nに底10の対数をとった値で，縦軸はHの値である．
図 4.2: ハミング距離の推移の比較
図4.2(a)のhの計測に使われる系列は計算精度128ビットで計算した整数ロ
ジスティック写像のXt，即ち，式(4.18)のd0 ∼d127である．図4.2(a)から，初 期状態によって，Hが0.5に近づくにつれnの値が大きく異なっていることを
第4章 整数ロジスティック写像と撹拌演算による乱数生成
観測できる．初期状態に異なるビットの位置が上位であるほど，Hが0.5に近 づくにつれnの値が小さくなる．この特徴を成す原因は式(4.19)から観測でき る．Atのより上位ビットほど，d0 ∼d127の中のより多くのビットに関与してい ることである．
一方，図4.2(b)のMTのそれは，どんな初期状態でも106ビットほど，2つの 状態から近い系列が続いて生成されていることが観測される．Hが0.5に近づ くにnの値は108ビットほど必要である．
そして，提案法である図4.2(d)からは，nに対するHがランダムな振る舞い を見せている．初期状態の異なる位置に関係せず，その違いを敏感に反応し，n の値は104ビットほどで，MTよりも速くHの値を0.5に収束させていること が観測できる．このことは，式(4.12)で提案法の出力であるRtの全てのビット がAtの全てのビットに影響されていることと一致している．
なお，MTに生成速度と初期値依存性を改良したSFMT[20]が知られている．
本研究はSFMT19937に対し，MTと同様な実験を行った．その結果を図4.2(c) に示す．そのHの推移が図4.2(b)のMTと同じ形であるが，MTよりも速く，n の値が107ほどで，Hが0.5に収束していることを確認できる．それは，SFMT がMTよりも速く内部状態の微小の違いを拡散していることを意味する．
また，任意の2つの初期状態で生成したMTの系列からは図4.2(d)と同等な 計測結果が得られることを確認した．
以上の結果から，整数ロジスティック写像式(4.1)から得たＵ字型の分布をも つXtの系列に対し，従来切り捨てられているDtの下位ビットを有効に利用し
た式(4.12)による撹拌が，一様分布のRtの系列を出力すると考えられる．ま
た，提案法は初期状態の微小な違いにもっとも敏感に反応していることがわか る．なお，より厳しい8項目の統計的検定による擬似乱数列の一様性に対する 検証を4節で行う．