置换同余生成器

**置換同餘生成器**，簡稱 **PCG**（英語：Permuted congruential generator）是一個用於產生偽隨機數的算法，開發於 2014 年。該算法在線性同餘生成器（LCG）的基礎上增加了輸出置換函數（output permutation function），以此優化 LCG 算法的統計性能。因此，PCG 算法在擁有出色的統計性能的同時，也擁有 LCG 算法代碼小、速度快、狀態小的特性。

置換同餘生成器（PCG）和線性同餘生成器（LCG）的差別有三點，在於：

1. LCG 的模數以及狀態大小比較大，狀態大小一般為輸出大小的二倍。
2. PCG 的核心使用 2 的 N 次冪作為模數，以此實現一個非常高效的全周期、無偏差的偽隨機數生成器。
3. PCG 的狀態不會被直接輸出，而是經過輸出置換函數計算後才輸出。

使用 2 的 N 次冪作為模數的 LCG 算法，普遍出現輸出低位周期短小的問題，而 PCG 通過輸出置換函數解決了這個問題。

## 種類

PCG 算法由兩個部分組成：_狀態轉換函數_以及_輸出置換函數_，其中輸出置換函數可以根據使用場景進行改變。PCG 因此屬於一個算法家族，每個分支的不同之處在於其使用的輸出置換函數。

狀態轉換函數定義為大小介於 8 位至 128 位的 LCG 算法，但是被真正推薦應用的只有 64 位和 128 位的版本，其餘的僅作該 PCG 算法的統計測試使用。LCG 算法中的增量可以更改成任意奇數，以此產生不同的流。又因為增量是任意的，將生成器狀態的地址的最低位設為 1 後（即地址 OR 1），該地址亦可作為增量使用。

PCG 算法亦定義了數種輸出置換函數。這些函數都表現良好，但是一些函數展示的性能更為優秀。:39 這些函數由以下部件合併而成：

* RR（random rotation）：隨機（依賴於輸入）旋轉，輸出大小為輸入大小的一半。給定一個 2b 位的輸入數字，最高的 _b-1_ 位用於循環移位量，將輸入的下半部分位向右循環移位，並將循環後的結果輸出，而最低的 2b-1+_1-b_ 位則被丟棄。
* RS（random shift）：隨機（依賴於輸入）移位，適用於循環移位成本更高的場景。同上，輸出是輸入大小的一半。從 2b 位輸入開始，前 _b-3_ 位用於移位量，該移位量應用於接下來的 2b-1+2b-3-1 位，並將最終結果的下半部分輸出，而最低的 2b-1-2b-3-b+4 位則被丟棄。
* XSH（xorshift）：相當於 `x ^= x >> 常数`。選擇的常數為下一個操作沒有丟棄的位的一半（向下取整）。
* XSL：XSH 的簡化版本，將輸入的上半部分與下半部分進行異或操作。產生的值將會用於後續的循環移位操作。
* RXS（random xorshift）：類似於 XSH，但使用一個隨機（依賴於輸入）的移位量。
* M（multiply）：將輸入乘以一個固定常數。

這些部件被組合成以下（受推薦的）置換輸出函數，此處以這些組合最常見的輸入與輸出大小進行說明：

* XSH-RR：

　
: _(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 >> (29 - count));`
* XSL-RR：XSH-RR 的簡化版，屬於提供給使用 2 個 64 位數字模擬 128 位運算的 64 位計算機的優化。

　
: _(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：同上，這個輸出函數的輸入與輸出大小一致，以提供 128 位的偽隨機數。

　
: _(128 位→128 位)_ `count = (int)(x >> 122); low64 = rotr64((uint64_t)(x ^ (x >> 64)), count); high64 = rotr64((uint64_t)(x >> 64), low64 & 63); return (uint128_t)high64 << 64 | low64;`

由於以上這些輸出轉換的每一個步驟都是可逆的，又或者是截尾性質的，所以它們可以確保皆是一一對應的雙射函數。因此，它們的複合函數能夠將一定數量的輸入值，映射到不同的輸出值上，以此保留了 LCG 算法的均衡分布特性。

最後，如果所需要的循環周期超過 2128，實現者可以使用子生成器陣列來擴展生成器。每次從這個陣列中輪流抽選一個子生成器，將其輸出與主生成器輸出相加，形成最終輸出。每當主生成器的狀態達到零時，子生成器陣列會被進行循環，使循環周期相對總狀態大小呈指數級增長。

## 代碼範例

推薦並且適用於大多數用戶的生成器，是具有 64 位狀態和 32 位輸出的 PCG-XSH-RR 生成器。:43 它可以通過以下方式實現：

範例中的生成器為了促進處理器的指令級並行，以提高該生成器在現代超純量處理器上的性能，選擇了將初始狀態作為輸出函數的輸入，而非其最終狀態（即狀態轉換函數執行後的狀態）。

此外，還有一個稍微更快的版本，剔除了 LCG 算法中的增量，使其狀態轉換函數成為萊默生成器的一種變體，並且使用了性能更弱的 XSH-RS 輸出函數。其循環周期僅為上述範例的四分之一：

儘管如此，由於這個算法依舊保留了性能開銷最大的 64 位 ×64 位乘法，其增加的性能並不多，因此第二個範例內的生成器只應在極端場景下使用。

在 32 位處理器上執行時，以上所有代碼範例都必然會使用三個 32×32→64 位的乘法運算來實現 64×64 位乘法。 為了將這個運算減少到兩個，可以使用一些性能幾乎與 64 位乘數一樣好的 32 位乘數，例如 0xf13283ad、0xffffffff0e703b65 或 0xf2fc5985。

## 對比其它偽隨機數生成器

BigCrush 測試通過獲取足夠的數據，來發現 235 或以下的循環周期。即便是理論最佳的偽隨機數生成器，也至少需要 36 位的狀態才能通過該測試。有些非常差的偽隨機數生成方法可以依賴使用極大的狀態大小來通過該測試，但是這項測試可以側面反映出這些算法的質量，生成器通過測試所需要的狀態越小越好。

PCG-RXS-M-XS 算法（32 位輸出）最低使用 36 位的狀態大小便能通過 BigCrush 測試，而 PCG-XSH-RR （以上範例中的 `pcg32()`）需要 39 位，PCG-XSH-RS （範例中的 `pcg32_fast()`）需要 49 位才能通過該測試。作為對比，PCG 算法的常見另類選擇 xorshift\* 算法需要 40 位的狀態，而梅森旋轉算法即便狀態為 19937 位亦無法通過該測試。

## 預測性與種子可恢復性

有研究已經表明，在給定 512 個連續輸出字節的情況下，通過大量計算恢復偽隨機生成器的種子是實際可行的。這意味著攻擊者實際上可以通過 512 位元組的偽隨機流，預測該流接下來會生成的隨機數。

## 參考

## 外部連結

* PCG, A Family of Better Random Number Generators （頁面存檔備份，存於網際網路檔案館） （英文）