|
キャリー付き乗算(multiply-with-carry, MWC)は、ジョージ・マーサグリアにより開発された整数疑似乱数生成用の手法である。乱数種には2〜数千の値を必要とする。MWC の主な長所は、単純な整数演算からなっており非常に高速に動作するという点と、260〜2000000 という非常に長周期であるという点である。 ==基本理論== MWC 列は ''b'' を法とする剰余からなる。''b'' = 232 とするのが普通だが、これはコンピュータで扱う整数が通常そのようになっているからである。ただ、''b'' = 232 − 1とすることもある。これは、232 − 1 を法とする演算は 232 を法とする演算を少し変更するだけで済み、さらに、''b'' = 232 の MWC の理論にはいくつか厄介な問題があるが、''b'' = 232 − 1 ではそれを回避できるからだ。 その最も一般的な形では、lag-r MWC 生成器は基数 ''b''、乗数 ''a''、そして ''r + 1'' 個の乱数種を必要とする。乱数種は ''r'' 個の ''b'' の剰余 :''x''0, ''x''1, ''x''2 ,..., ''x''''r''−1 と最初のキャリー ''c''r''−1'' < ''a'' である。 そして、lag-''r'' MWC 列は : で定義される ''x''''n'', ''c''''n'' のペアの数列であり、MWC 生成器の出力は以下の ''x'' の列となる。 :''x''''r'' , ''x''''r''+1 , ''x''''r''+2, ... lag-''r'' MWC 生成器の周期は ''abr'' − 1 を法とする数の乗法群における ''b'' の位数である。通例、''a'' は ''b'' の位数を大きくできるよう、''p = abr'' − 1 が素数になるように選ぶ。''b'' = 232 は ''p = abr'' − 1 の原始根とはならないので、''b'' = 232 を基数とした MWC 生成器の周期は、MWC の最大周期 ''p = abr'' − 2 になることはない。これが、''b'' = 232 − 1 の方が有利になる点の１つである。 Couture と l'Ecuyer (1997) により、MWC 生成器には最上位ビットが少し偏っているという理論的な問題があると指摘された。ただし、この問題は相補的キャリー付き乗算により解決されている。「相補的 MWC を使えば、最上位ビットは均一に出ることが分かるだろう。つまり、全周期中で0と1とが同等の頻度で現れ、その傾向も MWC 生成器間に関連性はない。」彼らはビットの偏り具合についてそれ以上詳しくは語っていないようである。相補的 MWC 生成器は計算時間が若干増えるため、実装の要求によってどちらを使うか決めるといいだろう。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「キャリー付き乗算」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Multiply-with-carry 」があります。 スポンサード リンク
|