Permuted congruential generator

Permuted congruential generator (PCG) は2014年に発表された擬似乱数生成器。線形合同法の出力を加工することで統計的性質を改善したものである。高速、省メモリかつ小さいコードサイズで非常に良い統計的性質を示す。
PCGは古典的な線形合同法と3つの点で異なる。
下位ビットの短い周期という線形合同法の弱点は状態に依存するビット回転量により解決する。
PCGの種類.
PCGにはいくつかの種類がある。内部で使用する線形合同法は8ビットから128ビットのものが使用される。実用的な用途では64ビットと128ビットのものだけが推奨される。それより小さいものは統計的性質のテストに使用される。
線形合同法で加算される定数は異なる乱数列を生成するために異なる値を使用できる。定数は任意の奇数で、明示的に指定する必要はない。最下位のビットを1にすれば状態を保持する変数のアドレスを使ってもよい。
状態を出力に変換する方法がいくつかある。どの方法もうまく働くが、それぞれ余裕の幅が異なる。変換方法は以下の要素によって構築される。
以下に挙げるものは推奨される組み合わせである。擬似コードも示す。
それぞれの変換は元に戻すことができる（つまり全単射）か切り捨てである。したがってそれらを合成したものはある出力が得られる入力の個数は常に同じである。
もしformula_10より長い周期が必要になった場合は複数の生成器を使って拡張することができる。例えば生成器を2つ使う場合、生成器1の出力が0になるごとに生成器2の出力を1つ進めて、最終的な出力は生成器1の出力と生成器2の出力の和とすることでそれぞれの周期の積の周期になる。
コード例.
ほとんどの場合に推奨される生成器は64ビットの状態を持ち32ビットを出力するPCG-XSH-RRである。具体的な実装の一例を示す。
static uint64_t state = 0x4d595df4d0f33173; // 何らかの初期状態
static uint64_t const multiplier = 6364136223846793005u;
static uint64_t const increment = 1442695040888963407u; // 任意の奇数
static uint32_t rotr32(uint32_t x, unsigned r)
 return x » r | x « (-r & 31);
uint32_t pcg32(void)
 uint64_t x = state;
 unsigned count = (unsigned)(x » 59); // 59 = 64 - 5
 state = x * multiplier + increment;
 x ^= x » 18; // 18 = (64 - 27)/2
 return rotr32((uint32_t)(x » 27), count); // 27 = 32 - 5
void pcg32_init(uint64_t seed)
 state = seed + increment;
 (void)pcg32();
この実装ではスーパースカラーのプロセッサーで命令レベルの並列性を最大化するために変換を線形合同法の計算後に行っている。
加算を使用せず、XSH-RSを使うことで若干高速化した実装を示す。この実装では周期はformula_11になり、XSH-RRより弱くなる。
static uint64_t mcg_state = 0xcafef00dd15ea5e5u; // 奇数でなければならない
uint32_t pcg32_fast(void)
 uint64_t x = mcg_state;
 unsigned count = (unsigned)(x » 61); // 61 = 64 - 3
 mcg_state = x * multiplier;
 x ^= x » 22;
 return (uint32_t)(x » (22 + count)); // 22 = 32 - 3 - 7
void pcg32_fast_init(uint64_t seed)
 mcg_state = 2*seed + 1;
 (void)pcg32_fast();
時間のかかる64ビットの乗算が残っているため高速化の効果は小さく、極端な場合を除き最初に挙げた実装のほうが良い。ただし、この高速化した実装も統計的検定を満足する。
32ビットプロセッサーで実行する場合、64ビット同士の乗算は32ビット同士の乗算3回が必要になる。これを2回に減らすには、32ビットの範囲に収まる乗数（0xf13283adなど）を使用する。
他の生成器との比較.
PCGはTestU01のBigCrushに合格するのに必要な最小限の状態のビット数を決定する過程で開発された。BigCrushは周期2^35の列を検出するのに十分なデータをテストするため、理想的な乱数生成器でも36ビットが必要である。十分に大きい状態の場合、平方採中法のような非常に悪い生成器でもBigCrushに合格することがある。小さい状態で合格することはそのアルゴリズムの質を示し、余裕の幅がどれだけあるかも示す。
PCG-RXS-M-XSはBigCrushに36ビット（理論上最小）で合格し、PCG-XSH-RRは39ビット、PCG-XSH-RSは49ビット必要である。ちなみに、xorshift*は40ビット、そしてメルセンヌ・ツイスタは19937ビットもの状態を持つのにもかかわらずBigCrushに合格できない。