PCGの種類
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/08/14 04:22 UTC 版)
「Permuted congruential generator」の記事における「PCGの種類」の解説
PCGにはいくつかの種類がある。内部で使用する線形合同法は8ビットから128ビットのものが使用される。実用的な用途では64ビットと128ビットのものだけが推奨される。それより小さいものは統計的性質のテストに使用される。 線形合同法で加算される定数は異なる乱数列を生成するために異なる値を使用できる。定数は任意の奇数で、明示的に指定する必要はない。最下位のビットを1にすれば状態を保持する変数のアドレスを使ってもよい。 状態を出力に変換する方法がいくつかある。どの方法もうまく働くが、それぞれ余裕の幅が異なる。変換方法は以下の要素によって構築される。 RR: ランダムな（入力に依存する）ビット回転で、入力の半分の長さの出力になる。 2 b {\displaystyle 2^{b}} ビットの入力の最上位の b − 1 {\displaystyle b-1} ビットが回転量を決めるのに使われ、そのすぐ下の 2 b − 1 {\displaystyle 2^{b-1}} ビットが右に回転され出力され、残りの下位 2 b − 1 − ( b − 1 ) {\displaystyle 2^{b-1}-(b-1)} ビットは捨てられる。 RS: ランダムな（入力に依存する）ビットシフト。ビット回転の計算時間が長いときに使用する。これも入力の半分の長さの出力になる。 2 b {\displaystyle 2^{b}} ビットの入力の最上位の b − 3 {\displaystyle b-3} ビットによりシフト量が決定され、すぐ下の 2 b − 1 + 2 b − 3 − 1 {\displaystyle 2^{b-1}+2^{b-3}-1} ビットに適用され、その中の下位 2 b − 1 {\displaystyle 2^{b-1}} ビットが出力される。残りの下位 2 b − 1 − 2 b − 3 − ( b − 4 ) {\displaystyle 2^{b-1}-2^{b-3}-(b-4)} ビットは捨てられる。 XSH: Xorshiftの操作 (x ^= x >> (定数))。定数は次の操作で捨てられないビットの半分（端数切り捨て）となるようにする。 XSL: XSHの (定数) の部分を全体の長さの半分にしたもの。 RXS: XSHの (定数) の部分をランダムな（入力に依存する）量にしたもの。 M: 定数の乗算。 以下に挙げるものは推奨される組み合わせである。擬似コードも示す。 XSH-RR: xorshiftで上位のビットを下位のビットに混ぜ、ビット 63-59 で回転量を決定しビット 27-58 に適用する。（64→32ビット）count = (int)(x >> 59); x ^= x >> 18; return rotr32((uint32_t)(x >> 27), count); XSH-RS: 上の方法よりシフト量を決めるのに使われるビットが少ない。（64→32ビット）count = (int)(x >> 61); x ^= x >> 22; return (uint32_t)(x >> (22 + count)); XSL-RR: XSH-RRを単純化したもので、これは64ビットマシンで128ビットの状態を持つ実装に最適化されている。（128→64ビット）count = (int)(x >> 122); x64 = (uint64_t)(x ^ (x >> 64)); return rotr64(x64, count); RXS-M-XS: 状態の半分を出力する場合、この方法は最も遅いが最も強い方法である。以下に示すように状態の全体を出力する場合は最も弱い方法になる。これを使う場合は状態のサイズが32ビットまたは64ビットに制限される。（32→32ビット）count = (int)(x >> 28); x ^= x >> (4 + count); x *= 277803737u; return x ^ (x >> 22); （64→64ビット）count = (int)(x >> 59); x ^= x >> (5 + count); x *= 12605985483714917081u; return x ^ (x >> 43); XSL-RR-RR: RXS-M-XSと同様に128ビットの状態から128ビットの状態に変換する。（128→128ビット）count = (int)(x >> 122); low64 = rotr64((uint64_t)(x ^ (x >> 64)), count); high64 = rotr((uint64_t)(x >> 64), low64 & 63); return (uint128_t)high64 << 64 | low64; それぞれの変換は元に戻すことができる（つまり全単射）か切り捨てである。したがってそれらを合成したものはある出力が得られる入力の個数は常に同じである。 もし 2 128 {\displaystyle 2^{128}} より長い周期が必要になった場合は複数の生成器を使って拡張することができる。例えば生成器を2つ使う場合、生成器1の出力が0になるごとに生成器2の出力を1つ進めて、最終的な出力は生成器1の出力と生成器2の出力の和とすることでそれぞれの周期の積の周期になる。
※この「PCGの種類」の解説は、「Permuted congruential generator」の解説の一部です。
「PCGの種類」を含む「Permuted congruential generator」の記事については、「Permuted congruential generator」の概要を参照ください。
- PCGの種類のページへのリンク
