相補的なキャリー付き乗算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/12 01:33 UTC 版)
「キャリー付き乗算」の記事における「相補的なキャリー付き乗算」の解説
lag-r MWC の周期を決めるのは、通常 p=abr − 1 が素数となる乗数 a の選び方である。もし p が安全素数なら、b の位数は p − 1 か (p − 1)/2 となる。ただ、b mod p の位数を求めるには p − 1 を因数分解する必要があるだろうが、これを因数分解するのは難しいだろう。 しかし、p = abr + 1 の形の素数であれば、p − 1 = abr は簡単に因数分解できる。そのため、p = abr + 1 を素数とする場合の b によって規定される MWC を使えば、MWC の周期を求めるのに必要な計算数論は著しく簡単になるだろう。 幸いな事に、MWC を少し変更するだけで、abr + 1 の形の素数を作る事ができる。これを相補的なキャリー付き乗算(CMWC)と呼ぶ。 必要な入力は lag-r MWC と同じで、乗数 a と 基数 b、そして r + 1 個の乱数種 x0, x1, x2, ..., xr−1, cr − 1 である。新しいペア x, c を生成する方法は、以下のように少し変更される。 x n = ( b − 1 ) − ( a x n − r + c n − 1 ) mod b , c n = ⌊ a x n − r + c n − 1 b ⌋ {\displaystyle x_{n}=(b-1)-(ax_{n-r}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor } つまり、新しい x を作る際に、補数 (b − 1) − x を使うのである。 CMWC 生成器により作られる数列 x の周期は abr + 1 を法とする剰余の乗法群における b の位数になり、x を逆順にしたものは、ある 0 < j < abr において j/(abr + 1) の基数 b での小数部と一致する。 lag-r CMWC を使うと、r が 512, 1024, 2048 と大きくなっても、簡単に周期を求める事ができる。（r を 2 の累乗にすると、r 個の最新の x を保持する配列内の要素へのアクセスが若干簡単に（そして速く）なる。） 以下に、いくつかの例を示す。 b=232 の時、lag-1024 CMWC x n = ( b − 1 ) − ( a x n − 1024 + c n − 1 ) mod b , c n = ⌊ a x n − 1024 + c n − 1 b ⌋ {\displaystyle x_{n}=(b-1)-(ax_{n-1024}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-1024}+c_{n-1}}{b}}\right\rfloor } の周期は a ⋅ {\displaystyle \cdot } 2327652 となり、109111 or 108798 or 108517 の a に対して約 109867 となる。 b=232 で a = 3636507990 の時、p = ab1359 − 1 は安全素数となるので、MWC 列の周期は 3636507990 ⋅ {\displaystyle \cdot } 243487 ≈ {\displaystyle \approx } 1013101 となる。 b = 232 の時、CMWC 生成器で現在見つかっている中で最大に近い周期を持つものに、素数 p = 15455296b42658 + 1 を元にしたものがあり、b の位数は 241489*21365056 すなわち約 10410928 である。
※この「相補的なキャリー付き乗算」の解説は、「キャリー付き乗算」の解説の一部です。
「相補的なキャリー付き乗算」を含む「キャリー付き乗算」の記事については、「キャリー付き乗算」の概要を参照ください。
- 相補的なキャリー付き乗算のページへのリンク
