text: 置換同餘生成器，簡稱PCG，以此最佳化LCG演算法的統計效能。因此，PCG演算法在擁有出色的統計效能的同時，也擁有LCG演算法程式碼小、速度快、狀態小的特性。置換同餘生成器的差別有三點，在於：使用2的N次冪作為模數的LCG演算法，普遍出現輸出低位週期短小的問題，而PCG透過輸出置換函式解決了這個問題。種類.PCG演算法由兩個部分組成："狀態轉換函式"以及"輸出置換函式"，其中輸出置換函式可以根據使用場景進行改變。PCG因此屬於一個演算法家族，每個分支的不同之處在於其使用的輸出置換函式。狀態轉換函式定義為大小介於8位至128位的LCG演算法，但是被真正推薦應用的只有64位和128位的版本，其餘的僅作該PCG演算法的統計測試使用。LCG演算法中的增量可以更改成任意奇數，以此產生不同的流。又因為增量是任意的，將生成器狀態的地址的最低位設為1後，該地址亦可作為增量使用。PCG演算法亦定義了數種輸出置換函式。這些函式都表現良好，但是一些函式展示的效能更為優秀。:39這些函式由以下部件合併而成：這些部件被組合成以下置換輸出函式，此處以這些組合最常見的輸入與輸出大小進行說明：由於以上這些輸出轉換的每一個步驟都是可逆的，又或者是截尾性質的，所以它們可以確保皆是一一對應的雙射函式。因此，它們的複合函式能夠將一定數量的輸入值，對映到不同的輸出值上，以此保留了LCG演算法的均衡分佈特性。最後，如果所需要的迴圈週期超過 2128，實現者可以使用子生成器陣列來擴充套件生成器。每次從這個陣列中輪流抽選一個子生成器，將其輸出與主生成器輸出相加，形成最終輸出。每當主生成器的狀態達到零時，子生成器陣列會被進行迴圈，使迴圈週期相對總狀態大小呈指數級增長。程式碼範例.推薦並且適用於大多數使用者的生成器，是具有64位狀態和32位輸出的 PCG-XSH-RR 生成器。:43它可以透過以下方式實現：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 &amp; 31);// 使用PCG生成器生成偽隨機數uint32_t pcg32(void)uint64_t x = state;unsigned count = (unsigned)(x » 59); // 59 = 64 - 5state = x * multiplier + increment;x ^= x » 18; // 18 = (64 - 27)/2return rotr32((uint32_t)(x » 27), count); // 27 = 32 - 5// 使用提供的種子值初始化生成器void pcg32_init(uint64_t seed)state = seed + increment;(void)pcg32();範例中的生成器為了促進處理器的指令級並行，以提高該生成器在現代超標量處理器上的效能，選擇了將初始狀態作為輸出函式的輸入，而非其最終狀態。此外，還有一個稍微更快的版本，剔除了LCG演算法中的增量，使其狀態轉換函式成為萊默生成器的一種變體，並且使用了效能更弱的XSH-RS輸出函式。其迴圈週期僅為上述範例的四分之一：static uint64_t mcg_state = 0xcafef00dd15ea5e5u; // 必須是奇數uint32_t pcg32_fast(void)uint64_t x = mcg_state;unsigned count = (unsigned)(x » 61); // 61 = 64 - 3mcg_state = x * multiplier;x ^= x » 22;return (uint32_t)(x » (22 + count)); // 22 = 32 - 3 - 7void pcg32_fast_init(uint64_t seed)mcg_state = 2*seed + 1;(void)pcg32_fast();儘管如此，由於這個演算法依舊保留了效能開銷最大的64位×64位乘法，其增加的效能並不多，因此第二個範例內的生成器只應在極端場景下使用。在 32 位處理器上執行時，以上所有程式碼範例都必然會使用三個 32×32→64 位的乘法運算來實現 64×64 位乘法。 為了將這個運算減少到兩個，可以使用一些效能幾乎與 64 位乘數一樣好的 32 位乘數，例如 0xf13283ad、0xffffffff0e703b65 或 0xf2fc5985。對比其它偽隨機數生成器.BigCrush測試透過獲取足夠的資料，來發現235或以下的迴圈週期。即便是理論最佳的偽隨機數生成器，也至少需要36位的狀態才能透過該測試。有些非常差的偽隨機數生成方法可以依賴使用極大的狀態大小來透過該測試，但是這項測試可以側面反映出這些演算法的質量，生成器透過測試所需要的狀態越小越好。PCG-RXS-M-XS演算法需要49位才能透過該測試。作為對比，PCG演算法的常見另類選擇xorshift*演算法需要40位的狀態，而梅森旋轉演算法即便狀態為19937位亦無法透過該測試。預測性與種子可恢復性.有研究已經表明，在給定 512 個連續輸出位元組的情況下，透過大量計算恢復偽隨機生成器的種子是實際可行的。這意味著攻擊者實際上可以透過512位元組的偽隨機流，預測該流接下來會生成的隨機數。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 置換同餘生成器
metadata: https://zh.wikipedia.org/wiki?curid=7627230