線形合同法との比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/12 01:33 UTC 版)
「キャリー付き乗算」の記事における「線形合同法との比較」の解説
線形合同法は通常以下で定義される。 x n = a x n − 1 + c mod 2 32 {\displaystyle x_{n}=ax_{n-1}+c\ {\bmod {\,}}2^{32}} ほとんどの演算プロセッサでは乗数 a と現在の x は32ビットレジスタに置け、積は64ビットの連結レジスタ上に求められる。積の下位32ビット、すなわち a × x mod 2 32 {\displaystyle a\times x\ {\bmod {\,}}2^{32}} は、右側のレジスタを参照するだけで得られる。同様に、これに32ビットの c を足してやれば自然に ax+c mod 232 が求まる。もし a mod 8 が 1 か 5 で c が奇数なら、232 を法とする合同数列の周期は 232 となる。 一方 lag-1 MWC は、線形合同法とほぼ同じ演算を使うだけで約 262 の周期を実現する。違うのは、MWC では64ビット積の上半分も利用している点である。これは 次の キャリー c として使われる。一方、線形合同法では c は固定値である。ax+c を64ビット値として求め、上半分を次の c として使い、下半分を x として使う訳である。 乗数 a が与えられれば、x, c のペアを入力として、新たなペアが作成される。 x ← ( a x + c ) mod 2 32 , c ← ⌊ a x + c 2 32 ⌋ {\displaystyle x\leftarrow (ax+c)\,{\bmod {\,}}2^{32},\ \ c\leftarrow \left\lfloor {\frac {ax+c}{2^{32}}}\right\rfloor } もし x と c が両方とも 0 でなければ、MWC 列の周期は ab − 1 を法とする剰余の乗法群における b = 232 の位数、すなわち、b32n = 1 mod (ab − 1) となる最小の n になる。もし 28〜31ビットの a を ab − 1 が安全素数となるよう選ぶと、ab − 1 と ab/2 − 1 は両方とも素数になり、周期は ab/2 − 1 となり、262 に近づく。実際にはとりうる32ビット値のペア x, c の数となるだろう。 以下は、上記の安全素数の条件を満たす a の最大値の例である。 a のビット数bab-1 が安全素数となる a の最大値周期15 216 31,743 1,040,154,623 16 216 64,545 2,115,010,559 31 232 2,147,483,085 4,611,684,809,394,094,079 32 232 4,294,966,893 * 次に、10で割った余りという単純な例を使って線形合同法と MWC の比較を行う。ここではレジスタは10進数1桁のサイズであるとし、連結レジスタは10進数2桁であるとする。 x 0 = 1 {\displaystyle x_{0}=1} から始めると、合同数列 x n = 7 x n − 1 + 3 mod 10 {\displaystyle x_{n}=7x_{n-1}+3\,{\bmod {\,}}10} は連結レジスタ上で 10 , 03 , 24 , 31 , 10 , 03 , 24 , 31 , 10 , … {\displaystyle 10,03,24,31,10,03,24,31,10,\ldots } の数列を持ち、x の出力列（右のレジスタ）の周期は4となる。 0 , 3 , 4 , 1 , 0 , 3 , 4 , 1 , 0 , 3 , 4 , 1 , … {\displaystyle 0,3,4,1,0,3,4,1,0,3,4,1,\ldots } x 0 = 1 {\displaystyle x_{0}=1} , c 0 = 3 {\displaystyle c_{0}=3} から始めると、MWC 列 x n = ( 7 x n − 1 + c n − 1 ) mod 10 , c n = ⌊ 7 x n − 1 + c n − 1 10 ⌋ , {\displaystyle x_{n}=(7x_{n-1}+c_{n-1})\,{\bmod {\,}}10,\ c_{n}=\left\lfloor {\frac {7x_{n-1}+c_{n-1}}{10}}\right\rfloor ,} は連結レジスタ上で 31 , 10 , 01 , 07 , 49 , 67 , 55 , 40 , 04 , 28 , 58 , 61 , 13 , 22 , 16 , 43 , 25 , 37 , 52 , 19 , 64 , 34 , 31 , 10 , 01 , 07 , . . . {\displaystyle 31,10,01,07,49,67,55,40,04,28,58,61,13,22,16,43,25,37,52,19,64,34,\,31,10,01,07,...} の数列を持ち、x の出力列（右のレジスタ）の周期は22となる。 1 , 0 , 1 , 7 , 9 , 7 , 5 , 0 , 4 , 8 , 8 , 1 , 3 , 2 , 6 , 3 , 5 , 7 , 2 , 9 , 4 , 4 , 1 , 0 , 1 , 7 , 9 , 7 , 5 , 0 , . . . {\displaystyle 1,0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4,\,1,0,1,7,9,7,5,0,...} x の繰り返し部分を逆順にすると 449275 ⋯ 97101 449275 ⋯ 9710144 ⋯ {\displaystyle 449275\cdots 97101\,449275\cdots 9710144\cdots } となり、これは a=7, b=10, j=31 とした時の j/(ab−1) の値 31 69 = .4492753623188405797101 4492753623 … {\displaystyle {\frac {31}{69}}=.4492753623188405797101\,4492753623\ldots } の小数部と一致する点に注目したい。 これは一般的にもなりたち、lag-r MWC により生成された x の列 x n = ( a x n − r + c n − 1 ) mod b , c n = ⌊ a x n − r + c n − 1 b ⌋ , {\displaystyle x_{n}=(ax_{n-r}+c_{n-1}){\bmod {\,}}b\,,\ \ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor ,} は、逆順にすると、ある 0 < j < abr において j/(abr − 1) の基数 b での小数部と一致する。 さらに、合同数列を x n = 7 x n − 1 mod 69 {\displaystyle x_{n}=7x_{n-1}\,{\bmod {\,}}69} で定義した場合、 x 0 = 34 {\displaystyle x_{0}=34} から始めると以下の周期22の数列を得るが、 31 , 10 , 1 , 7 , 49 , 67 , 55 , 40 , 4 , 28 , 58 , 61 , 13 , 22 , 16 , 43 , 25 , 37 , 52 , 19 , 64 , 34 , 31 , 10 , 1 , 7 , … {\displaystyle 31,10,1,7,49,67,55,40,4,28,58,61,13,22,16,43,25,37,52,19,64,34,\,31,10,1,7,\ldots } これを10で割った余りを求めると 1 , 0 , 1 , 7 , 9 , 7 , 5 , 0 , 4 , 8 , 8 , 1 , 3 , 2 , 6 , 3 , 5 , 7 , 2 , 9 , 4 , 4 , 1 , 0 , 1 , 7 , 9 , 7 , 5 , 0 , … {\displaystyle 1,0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4,\,1,0,1,7,9,7,5,0,\ldots } となり、上記の MWC 列に一致する。 これは一般的にも成り立ち（ただし、これは lag-1 MWC でしか成り立たないが）、初期値が x 0 {\displaystyle x_{0}} , c 0 {\displaystyle c_{0}} の lag-1 MWC 列 x n = ( a x n − 1 + c n − 1 ) mod b , c n = ⌊ a x n − 1 + c n − 1 b ⌋ {\displaystyle x_{n}=(ax_{n-1}+c_{n-1})\,{\bmod {b}}\,,\ \ c_{n}=\left\lfloor {\frac {ax_{n-1}+c_{n-1}}{b}}\right\rfloor } により得られる数列 x 1 , x 2 , … {\displaystyle x_{1},x_{2},\ldots } は、合同数列 yn = ayn − 1 mod(ab − 1) を b で割った余りに一致する。 初期値 y0 の選び方は、単に x のサイクルをずらすだけにすぎない。
※この「線形合同法との比較」の解説は、「キャリー付き乗算」の解説の一部です。
「線形合同法との比較」を含む「キャリー付き乗算」の記事については、「キャリー付き乗算」の概要を参照ください。
- 線形合同法との比較のページへのリンク
