キャリー付き乗算について

Words near each other

Dictionary Lists

mini英和辞書

mini和英辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

キャリー付き乗算：ミニ英和和英辞書

キャリー付き乗算[きゃりーつきじょうざん]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

・ー： [ちょうおん]
　(n) long vowel mark (usually only used in katakana)
・付： [ふ]
　 1. (n,vs) giving to　2. submitting to　3. refer to　4. affix　5. append
・付き： [つき, づき]
　 1. (n,n-suf) attached to　2. impression　3. sociality　4. appearance　5. furnished with　6. under　7. to
・乗算： [じょうざん]
　(n) multiplication

キャリー付き乗算：ウィキペディア日本語版

キャリー付き乗算[きゃりーつきじょうざん]
キャリー付き乗算(multiply-with-carry, MWC)は、ジョージ・マーサグリアにより開発された整数疑似乱数生成用の手法である。乱数種には2〜数千の値を必要とする。MWC の主な長所は、単純な整数演算からなっており非常に高速に動作するという点と、2^60〜2000000 という非常に長周期であるという点である。
==基本理論==
MWC 列は ''b'' を法とする剰余からなる。''b'' = 2³² とするのが普通だが、これはコンピュータで扱う整数が通常そのようになっているからである。ただ、''b'' = 2³² − 1とすることもある。これは、2³² − 1 を法とする演算は 2³² を法とする演算を少し変更するだけで済み、さらに、''b'' = 2³² の MWC の理論にはいくつか厄介な問題があるが、''b'' = 2³² − 1 ではそれを回避できるからだ。
その最も一般的な形では、lag-r MWC 生成器は基数 ''b''、乗数 ''a''、そして ''r + 1'' 個の乱数種を必要とする。乱数種は ''r'' 個の ''b'' の剰余
:''x''₀, ''x''₁, ''x''₂,..., ''x''_''r''−1
と最初のキャリー ''c_''r''−1'' < ''a'' である。
そして、lag-''r'' MWC 列は
:

x_n=(ax_+c_)\,\bmod\,b,\ c_n=\left\lfloor\frac\right\rfloor,\ n\ge r

で定義される ''x''_''n'', ''c''_''n'' のペアの数列であり、MWC 生成器の出力は以下の ''x'' の列となる。
:''x''_''r'' , ''x''_''r''+1 , ''x''_''r''+2, ...
lag-''r'' MWC 生成器の周期は ''ab^r'' − 1 を法とする数の乗法群における ''b'' の位数である。通例、''a'' は ''b'' の位数を大きくできるよう、''p = ab^r'' − 1 が素数になるように選ぶ。''b'' = 2³² は ''p = ab^r'' − 1 の原始根とはならないので、''b'' = 2³² を基数とした MWC 生成器の周期は、MWC の最大周期 ''p = ab^r'' − 2 になることはない。これが、''b'' = 2³² − 1 の方が有利になる点の１つである。
Couture と l'Ecuyer (1997) により、MWC 生成器には最上位ビットが少し偏っているという理論的な問題があると指摘された。ただし、この問題は相補的キャリー付き乗算により解決されている。「相補的 MWC を使えば、最上位ビットは均一に出ることが分かるだろう。つまり、全周期中で0と1とが同等の頻度で現れ、その傾向も MWC 生成器間に関連性はない。」彼らはビットの偏り具合についてそれ以上詳しくは語っていないようである。相補的 MWC 生成器は計算時間が若干増えるため、実装の要求によってどちらを使うか決めるといいだろう。

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「キャリー付き乗算」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース