Permuted congruential generator (PCG) は2014年に発表された擬似乱数生成器。線形合同法の出力を加工することで統計的性質を改善したものである。高速、省メモリかつ小さいコードサイズで非常に良い統計的性質を示す[1][2][3][4][5]。

PCGは古典的な線形合同法と3つの点で異なる。

線形合同法で使われる状態が大きい（通常、出力の2倍）。

法として2の冪を使う（これにより偏りがなく最長の周期を効果的に実装できる）。

状態は直接出力されるのではなく、最も周期の長いビットによってビット回転やビットシフトの量が決まり、出力に影響する。

下位ビットの短い周期という線形合同法の弱点は状態に依存するビット回転量により解決する[5]。
PCGの種類

PCGにはいくつかの種類がある。内部で使用する線形合同法は8ビットから128ビットのものが使用される。実用的な用途では64ビットと128ビットのものだけが推奨される。それより小さいものは統計的性質のテストに使用される。

線形合同法で加算される定数は異なる乱数列を生成するために異なる値を使用できる[6]。定数は任意の奇数で、明示的に指定する必要はない。最下位のビットを1にすれば状態を保持する変数のアドレスを使ってもよい。

状態を出力に変換する方法がいくつかある。どの方法もうまく働くが、それぞれ余裕の幅が異なる[5]。変換方法は以下の要素によって構築される。

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の出力の和とすることでそれぞれの周期の積の周期になる。
コード例

ほとんどの場合に推奨される生成器は64ビットの状態を持ち32ビットを出力するPCG-XSH-RRである[5]。具体的な実装の一例を示す。#include <stdint.h>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();}

この実装ではスーパースカラーのプロセッサーで命令レベルの並列性を最大化するために変換を線形合同法の計算後に行っている[5]。

加算を使用せず、XSH-RSを使うことで若干高速化した実装を示す。この実装では周期は 2 62 {\displaystyle 2^{62}} になり、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ビットの乗算が残っているため高速化の効果は小さく、極端な場合を除き最初に挙げた実装のほうが良い。