周期の特定
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/02 16:40 UTC 版)
シード値を128bitの二元横ベクトル β {\displaystyle \beta } 、現在の状態から次状態への二元遷移行列を T {\displaystyle T} と置くと、Xorshiftアルゴリズムにより生成される乱数列は β , β T , β T 2 , … {\displaystyle \beta ,\beta T,\beta T^{2},\dots } と表される。詳しい証明は省略するが、行列 T {\displaystyle T} のOrderが k = 2 n − 1 {\displaystyle k=2^{n}-1} で表される時、かつその時に限り、任意の0でない β {\displaystyle \beta } に対し β , β T , β T 2 , … , β T k − 1 {\displaystyle \beta ,\beta T,\beta T^{2},\dots ,\beta T^{k-1}} は全て異なる値となる。 予備的なテストとしては、今周期 k {\displaystyle k} について k = 2 n − 1 {\displaystyle k=2^{n}-1} となることを期待しているため、期待する n {\displaystyle n} が T 2 n = T {\displaystyle T^{2^{n}}=T} を満たす最小の n {\displaystyle n} であるかを調べる、というものがある。これは T {\displaystyle T} を n {\displaystyle n} 回二乗すれば良いため、乱数列を調べるのと比較すると十分に速く調べられる。 完全なテストとしては、期待する周期 k {\displaystyle k} の約数 d {\displaystyle d} について T d ≠ I ⟺ k ≠ d {\displaystyle T^{d}\neq I\iff k\neq d} を示せば良い。例えば、 n {\displaystyle n} bitのビット列 x {\displaystyle x} に対する操作が x ^= x << a;x ^= x>> b;x ^= x << c;return x; である場合、 T = ( I + L a ) ( I + R b ) ( I + L c ) {\displaystyle T=(I+L^{a})(I+R^{b})(I+L^{c})} である。但し、 L i , j a = { 1 i = j + a 0 otherwise {\displaystyle L_{i,j}^{a}={\begin{cases}1&i=j+a\\0&{\text{otherwise}}\end{cases}}} 及び R i , j a = { 1 i = j − a 0 otherwise {\displaystyle R_{i,j}^{a}={\begin{cases}1&i=j-a\\0&{\text{otherwise}}\end{cases}}} である。 n = 32 {\displaystyle n=32} の場合、 T d ≠ I ⟸ d = { 65535 16711935 252645135 858993459 1431655765 {\displaystyle T^{d}\neq I\Longleftarrow d={\begin{cases}65535\\16711935\\252645135\\858993459\\1431655765\end{cases}}} 及び T 2 32 = T {\displaystyle T^{2^{32}}=T} を調べれば十分である。 n = 64 {\displaystyle n=64} の場合、 2 64 − 1 {\displaystyle 2^{64}-1} が 641 {\displaystyle 641} の倍数であるということに注意すると、 T d ≠ I ⟸ d = { 2753074036095 281470681808895 28778071877862015 71777214294589695 1085102592571150095 3689348814741910323 6148914691236517205 {\displaystyle T^{d}\neq I\Longleftarrow d={\begin{cases}2753074036095\\281470681808895\\28778071877862015\\71777214294589695\\1085102592571150095\\3689348814741910323\\6148914691236517205\end{cases}}} 及び T 2 64 = T {\displaystyle T^{2^{64}}=T} を調べれば十分である。 別の例としては t = x ^ (x << 11);x = y; y=z; z=w;return w=(w ^ (w>> 19)) ^ (t ^ (t >> 8)); に対しては ( x n + 1 y n + 1 z n + 1 w n + 1 ) = ( x n y n z n w n ) ⋅ T {\displaystyle ({\begin{smallmatrix}x_{n+1}&y_{n+1}&z_{n+1}&w_{n+1}\end{smallmatrix}})=({\begin{smallmatrix}x_{n}&y_{n}&z_{n}&w_{n}\end{smallmatrix}})\cdot T} のように立式し、 T = ( O O O ( I + L 11 ) ( I + R 8 ) I O O O O I O O O O I ( I + R 19 ) ) {\displaystyle T=\left({\begin{smallmatrix}O&O&O&(I+L^{11})(I+R^{8})\\I&O&O&O\\O&I&O&O\\O&O&I&(I+R^{19})\\\end{smallmatrix}}\right)} について同様に解く。各変数が32 bitだとすれば n = 128 {\displaystyle n=128} , 64 bitだとすれば n = 256 {\displaystyle n=256} であり、対応する d {\displaystyle d} は以下の表のようになる。 n {\displaystyle n} 32 {\displaystyle 32} 64 {\displaystyle 64} 128 {\displaystyle 128} 256 {\displaystyle 256} d {\displaystyle d} 0x0000ffff 0x00000280fffffd7f 0x0000000000042f00fffffffffffbd0ff 0x000000000000000000d3eafc3af14600ffffffffffffffffff2c1503c50eb9ff 0x00ff00ff 0x0000ffff0000ffff 0x00000280fffffd7f00000280fffffd7f 0x000000000000013540775b48cc32ba00fffffffffffffecabf88a4b733cd45ff 0x0f0f0f0f 0x00663d80ff99c27f 0x00003d30f19cd100ffffc2cf0e632eff 0x0000000000042f00fffffffffffbd0ff0000000000042f00fffffffffffbd0ff 0x33333333 0x00ff00ff00ff00ff 0x0000ffff0000ffff0000ffff0000ffff 0x00000280fffffd7f00000280fffffd7f00000280fffffd7f00000280fffffd7f 0x55555555 0x0f0f0f0f0f0f0f0f 0x00663d80ff99c27f00663d80ff99c27f 0x00003d30f19cd100ffffc2cf0e632eff00003d30f19cd100ffffc2cf0e632eff 0x3333333333333333 0x00ff00ff00ff00ff00ff00ff00ff00ff 0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff 0x5555555555555555 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f 0x00663d80ff99c27f00663d80ff99c27f00663d80ff99c27f00663d80ff99c27f 0x33333333333333333333333333333333 0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff 0x55555555555555555555555555555555 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f 0x3333333333333333333333333333333333333333333333333333333333333333 0x5555555555555555555555555555555555555555555555555555555555555555
※この「周期の特定」の解説は、「Xorshift」の解説の一部です。
「周期の特定」を含む「Xorshift」の記事については、「Xorshift」の概要を参照ください。
- 周期の特定のページへのリンク
