置换同余生成器

置换同余生成器，简称PCG（英语：Permuted congruential generator）是一个用于产生伪随机数的算法，开发于2014年。该算法在线性同余生成器（LCG）的基础上增加了输出置换函数（output permutation function），以此优化LCG算法的统计性能。因此，PCG算法在拥有出色的统计性能的同时[1][2]，也拥有LCG算法代码小、速度快、状态小的特性。[3]

置换同余生成器（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），该地址亦可作为增量使用。[4]

PCG算法亦定义了数种输出置换函数。这些函数都表现良好，但是一些函数展示的性能更为优秀。[3]: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 生成器。[3]:43它可以通过以下方式实现： 

#include <stdint.h>
static uint64_t       state      = 0x4d595df4d0f33173;		// 生成器的状态，初始值可以根据种子进行改变
static uint64_t const multiplier = 6364136223846793005u;    // 状态转换函数——线性同余方法（LCG）的乘数
static uint64_t const increment  = 1442695040888963407u;	// 线性同余方法（LCG）的增量，可以是任意奇数

// 循环移位函数
static uint32_t rotr32(uint32_t x, unsigned r)
{
	return x >> r | x << (-r & 31);
}

// 使用PCG生成器生成伪随机数
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();
}

范例中的生成器为了促进处理器的指令层级平行，以提高该生成器在现代超标量处理器上的性能，选择了将初始状态作为输出函数的输入，而非其最终状态（即状态转换函数执行后的状态）。

此外，还有一个稍微更快的版本，剔除了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 - 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位×64位乘法，其增加的性能并不多，因此第二个范例内的生成器只应在极端场景下使用。

在 32 位处理器上执行时，以上所有代码范例都必然会使用三个 32×32→64 位的乘法运算来实现 64×64 位乘法。 为了将这个运算减少到两个，可以使用一些性能几乎与 64 位乘数一样好的 32 位乘数，例如 0xf13283ad[4]、0xffffffff0e703b65 或 0xf2fc5985。

对比其它伪随机数生成器

BigCrush测试通过获取足够的数据，来发现235或以下的循环周期。即便是理论最佳的伪随机数生成器，也至少需要36位的状态才能通过该测试。有些非常差的伪随机数生成方法可以依赖使用极大的状态大小来通过该测试，但是这项测试可以侧面反映出这些算法的质量，生成器通过测试所需要的状态越小越好。[5]

PCG-RXS-M-XS算法（32位输出）最低使用36位的状态大小便能通过BigCrush测试，而PCG-XSH-RR （以上范例中的pcg32()）需要39位，PCG-XSH-RS （范例中的pcg32_fast()）需要49位才能通过该测试。作为对比，PCG算法的常见另类选择xorshift*算法需要40位的状态，而梅森旋转算法即便状态为19937位亦无法通过该测试。[6]

预测性与种子获取性

有研究已经表明，在给定 512 个连续输出字节的情况下，通过大量计算获取复伪随机生成器的种子是实际可行的。这意味着实际上可以通过512字节的伪随机流，预测该流的其余部分。[7]

参考

  1. ^ Lemire, Daniel. Testing non-cryptographic random number generators: my results. 22 August 2017 [2017-10-03]. （原始内容存档于2021-08-29）. 
  2. ^ Cook, John D. Testing the PCG random number generator. 7 July 2017 [2017-10-03]. （原始内容存档于2021-08-29）. 
  3. ^ 3.0 3.1 3.2 O'Neill, Melissa E. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. 5 September 2014 [2021-08-29]. HMC-CS-2014-0905. （原始内容存档 (PDF)于2021-12-20）. 
  4. ^ 4.0 4.1 O'Neill, M.E. Critiquing PCG's streams (and SplitMix's too). 10 August 2017 [2017-11-03]. （原始内容存档于2021-09-16）. 
  5. ^ O'Neill, M.E. Too Big to Fail. 20 August 2017 [2017-11-03]. （原始内容存档于2022-01-10）. 
  6. ^ L'Ecuyer, Pierre; Simard, Richard. TestU01: A C library for empirical testing of random number generators (PDF). ACM Transactions on Mathematical Software. August 2007, 33 (4): 22-1–22-40 [2021-08-29]. CiteSeerX 10.1.1.499.2830  . doi:10.1145/1268776.1268777. （原始内容存档 (PDF)于2021-04-28）. 
  7. ^ Bouillaguet, Charles; Martinez, Florette; Sauvage, Julia. Practical seed-recovery for the PCG Pseudo-Random Number Generator. IACR Transactions on Symmetric Cryptology. 28 September 2020, 2020 (3): 175–196. doi:10.13154/tosc.v2020.i3.175-196. 

外部链接