如何测试 CRC32C 是否为 "good" 随机生成器？
How can I test if CRC32C is a "good" random generator?
我最近发现 _mm_crc32_* intel 内部指令可用于生成（伪）随机 32 位数字。
#include <nmmintrin.h> /* needs CRC32C instruction from SSE4.2 instruction set extension */
uint32_t rnd = 1; /* initialize with seed != 0 */
/* period length is 4,294,967,295 = 2^32-1 */
while (1) {
#if 0 // this was faster but worse than xorshift32 (fails more tests)
// rnd = _mm_crc32_u8(rnd, rnd >> 3);
#else // this is faster and better than xorshift32 (fails fewer tests)
rnd = _mm_crc32_u32(rnd, rnd << 18);
#endif
printf("%08X\n", rnd);
}
此方法与 LCG 一样快，并且比 xorshift32 更快。维基百科说因为 xorshift 生成器 "fail a few statistical tests, they have been accused of being unreliable".
现在我想知道 CRC32C 方法是否通过了对随机数生成器进行的各种测试。我只是通过尝试使用 PAQ8 压缩器（失败）进行压缩来验证每一位，甚至是 LSB，都是 "random"。有人可以帮我做更好的测试吗？
编辑： 使用建议的 TestU01 套件中的测试，结果证明我之前使用的方法比 xorshift32 更糟糕。我已经更新了上面的源代码，以防有人有兴趣使用更好的版本。
这是一个有趣的问题。最终唯一重要的测试是 "does this rng yield correct results for the problem I'm working on"。您希望用 rng 做什么？
为了避免对每个不同的问题都回答那个问题，已经设计了各种测试。例如，参见 George Marsaglia 设计的 "Diehard" 测试。网络搜索 "marsaglia random number generator tests" 会出现几个有趣的链接。
我认为 Marsaglia 的作品此时已经有几十年的历史了。我不知道从那以后是否有更多关于这个主题的工作。我的猜测是，对于非加密目的，通过 Diehard 测试的 rng 可能就足够了。
视频游戏（尤其是单人游戏）与蒙特卡洛模拟对 PRNG 的要求有很大差异。小的偏差对于科学数值计算来说可能是个问题，但对于游戏来说通常不是，尤其是当来自相同 PRNG 的数字以不同方式使用时。
存在具有不同速度/质量权衡的不同 PRNG 是有原因的。
这个 非常 快，特别是如果种子/状态保留在寄存器中，在现代英特尔 CPU 上只需要 2 或 3 微指令。因此，如果它可以内联到循环中，那就太棒了。与相同速度的其他任何东西相比，它的质量可能更好。但与更大状态下只慢一点的东西相比，如果你关心统计质量，它可能是可悲的。
在带有 BMI2 的 x86 上，每个 RNG 步骤只需要 rorx edx, eax, 3 / crc32 eax, dl。在 Haswell/Skylake 上，这是 2 微指令，总延迟 = 1 + 循环携带依赖性的 3 个周期。 (http://agner.org/optimize/). Or 3 uops without BMI2, for mov edx, eax / shr edx,3 / crc32 eax, dl, but still only 4 cycles of latency on .
2 微指令在正常情况下对周围代码的影响可以忽略不计，在这种情况下，您对每个 PRNG 结果做了足够的工作，因此 4 周期依赖链不是瓶颈。 （或者如果你的编译器 stores/reloads 循环内的 PRNG 状态而不是将其保存在寄存器中并在循环后将存储下沉到全局，则为 ~9 循环，这会花费你 2 个额外的 1-uop 指令）。
在 Ryzen 上，crc32 是 3 微指令，总延迟为 3 秒，因此对周围代码的影响更大，但如果您对 PRNG 结果做的太少而导致瓶颈，则每 4 个时钟瓶颈的影响相同那。
我怀疑您可能一直在对循环携带的依赖链瓶颈进行基准测试，而不是对真正的周围代码的影响，这些代码做了足够的工作来隐藏延迟。 （几乎所有相关的 x86 CPUs 都是乱序执行。）使 RNG 比 xorshift128+ 甚至 xorshift128 更便宜，对于大多数用例来说可能可以忽略不计。 xorshift128+ 或 xorshift128* 速度很快，而且速度质量非常好。
如果您想要非常快地获得大量 PRNG 结果，请考虑使用 SIMD xorshift128+ 来运行 两个或四个并行生成器（在 XMM 或 YMM 的不同元素中载体）。特别是如果您可以有用地使用 PRNG 结果的 __m256i 向量。参见 AVX/SSE version of xorshift128+, and also this answer where I used it。
将整个状态作为 RNG 结果返回通常是一件坏事，因为这意味着一个值可以准确地告诉您下一个值是什么。即 3 后面总是跟着 1897987234（假数字），而 3 后面永远不会跟着其他东西。大多数统计质量测试都应该解决这个问题，但这对于任何给定的用例来说可能是也可能不是问题。
请注意，https://en.wikipedia.org/wiki/Xorshift is saying that even xorshift128 fails a few statistical tests. I assume xorshift32 is significantly worse. CRC32c 也是基于 XOR 和移位（但在 Galois Field(2) 中也有位反射和模），因此有理由认为它在质量上可能相似或更好。
你说你选择的 crc32(rnd, rnd>>3) 给出了 2^32 的周期，这是你能用这么小的状态做的最好的。 （当然 rnd++ 达到了同一时期，所以它不是唯一的质量衡量标准。）它可能至少和 an LCG 一样好，但那些是 而不是 被认为是高质量的，特别是如果模数是 2^32（所以你可以从固定宽度的整数数学中免费获得它）。
衡量 PRNG 优劣的一个指标是循环的长度。如果这对您的应用程序很重要，那么您正在使用的 CRC-32 将不是一个好的选择，因为周期只有 232。一个结果是，如果您使用的样本多于此，而这不会花费很长时间，您的结果将会重复。另一个是连续的 CRC-32 值之间存在相关性，其中只有一个可能值会跟随当前值。
更好的 PRNG 具有指数级更长的周期，并且返回的值小于状态中的位，因此连续值没有这种相关性。
您不需要使用 CRC-32C 指令来提高速度。您也不需要设计自己的 PRNG，它充满了隐藏的危险。最好把它留给专业人士。有关高质量、小型和快速随机数生成器的信息，请参阅 this work。
我最近发现 _mm_crc32_* intel 内部指令可用于生成（伪）随机 32 位数字。
#include <nmmintrin.h> /* needs CRC32C instruction from SSE4.2 instruction set extension */
uint32_t rnd = 1; /* initialize with seed != 0 */
/* period length is 4,294,967,295 = 2^32-1 */
while (1) {
#if 0 // this was faster but worse than xorshift32 (fails more tests)
// rnd = _mm_crc32_u8(rnd, rnd >> 3);
#else // this is faster and better than xorshift32 (fails fewer tests)
rnd = _mm_crc32_u32(rnd, rnd << 18);
#endif
printf("%08X\n", rnd);
}
此方法与 LCG 一样快，并且比 xorshift32 更快。维基百科说因为 xorshift 生成器 "fail a few statistical tests, they have been accused of being unreliable".
现在我想知道 CRC32C 方法是否通过了对随机数生成器进行的各种测试。我只是通过尝试使用 PAQ8 压缩器（失败）进行压缩来验证每一位，甚至是 LSB，都是 "random"。有人可以帮我做更好的测试吗？
编辑： 使用建议的 TestU01 套件中的测试，结果证明我之前使用的方法比 xorshift32 更糟糕。我已经更新了上面的源代码，以防有人有兴趣使用更好的版本。
这是一个有趣的问题。最终唯一重要的测试是 "does this rng yield correct results for the problem I'm working on"。您希望用 rng 做什么？
为了避免对每个不同的问题都回答那个问题，已经设计了各种测试。例如，参见 George Marsaglia 设计的 "Diehard" 测试。网络搜索 "marsaglia random number generator tests" 会出现几个有趣的链接。
我认为 Marsaglia 的作品此时已经有几十年的历史了。我不知道从那以后是否有更多关于这个主题的工作。我的猜测是，对于非加密目的，通过 Diehard 测试的 rng 可能就足够了。
视频游戏（尤其是单人游戏）与蒙特卡洛模拟对 PRNG 的要求有很大差异。小的偏差对于科学数值计算来说可能是个问题，但对于游戏来说通常不是，尤其是当来自相同 PRNG 的数字以不同方式使用时。
存在具有不同速度/质量权衡的不同 PRNG 是有原因的。
这个 非常 快，特别是如果种子/状态保留在寄存器中，在现代英特尔 CPU 上只需要 2 或 3 微指令。因此，如果它可以内联到循环中，那就太棒了。与相同速度的其他任何东西相比，它的质量可能更好。但与更大状态下只慢一点的东西相比，如果你关心统计质量，它可能是可悲的。
在带有 BMI2 的 x86 上，每个 RNG 步骤只需要 rorx edx, eax, 3 / crc32 eax, dl。在 Haswell/Skylake 上，这是 2 微指令，总延迟 = 1 + 循环携带依赖性的 3 个周期。 (http://agner.org/optimize/). Or 3 uops without BMI2, for mov edx, eax / shr edx,3 / crc32 eax, dl, but still only 4 cycles of latency on
2 微指令在正常情况下对周围代码的影响可以忽略不计，在这种情况下，您对每个 PRNG 结果做了足够的工作，因此 4 周期依赖链不是瓶颈。 （或者如果你的编译器 stores/reloads 循环内的 PRNG 状态而不是将其保存在寄存器中并在循环后将存储下沉到全局，则为 ~9 循环，这会花费你 2 个额外的 1-uop 指令）。
在 Ryzen 上，crc32 是 3 微指令，总延迟为 3 秒，因此对周围代码的影响更大，但如果您对 PRNG 结果做的太少而导致瓶颈，则每 4 个时钟瓶颈的影响相同那。
我怀疑您可能一直在对循环携带的依赖链瓶颈进行基准测试，而不是对真正的周围代码的影响，这些代码做了足够的工作来隐藏延迟。 （几乎所有相关的 x86 CPUs 都是乱序执行。）使 RNG 比 xorshift128+ 甚至 xorshift128 更便宜，对于大多数用例来说可能可以忽略不计。 xorshift128+ 或 xorshift128* 速度很快，而且速度质量非常好。
如果您想要非常快地获得大量 PRNG 结果，请考虑使用 SIMD xorshift128+ 来运行 两个或四个并行生成器（在 XMM 或 YMM 的不同元素中载体）。特别是如果您可以有用地使用 PRNG 结果的 __m256i 向量。参见 AVX/SSE version of xorshift128+, and also this answer where I used it。
将整个状态作为 RNG 结果返回通常是一件坏事，因为这意味着一个值可以准确地告诉您下一个值是什么。即 3 后面总是跟着 1897987234（假数字），而 3 后面永远不会跟着其他东西。大多数统计质量测试都应该解决这个问题，但这对于任何给定的用例来说可能是也可能不是问题。
请注意，https://en.wikipedia.org/wiki/Xorshift is saying that even xorshift128 fails a few statistical tests. I assume xorshift32 is significantly worse. CRC32c 也是基于 XOR 和移位（但在 Galois Field(2) 中也有位反射和模），因此有理由认为它在质量上可能相似或更好。
你说你选择的 crc32(rnd, rnd>>3) 给出了 2^32 的周期，这是你能用这么小的状态做的最好的。 （当然 rnd++ 达到了同一时期，所以它不是唯一的质量衡量标准。）它可能至少和 an LCG 一样好，但那些是 而不是 被认为是高质量的，特别是如果模数是 2^32（所以你可以从固定宽度的整数数学中免费获得它）。
衡量 PRNG 优劣的一个指标是循环的长度。如果这对您的应用程序很重要，那么您正在使用的 CRC-32 将不是一个好的选择，因为周期只有 232。一个结果是，如果您使用的样本多于此，而这不会花费很长时间，您的结果将会重复。另一个是连续的 CRC-32 值之间存在相关性，其中只有一个可能值会跟随当前值。
更好的 PRNG 具有指数级更长的周期，并且返回的值小于状态中的位，因此连续值没有这种相关性。
您不需要使用 CRC-32C 指令来提高速度。您也不需要设计自己的 PRNG，它充满了隐藏的危险。最好把它留给专业人士。有关高质量、小型和快速随机数生成器的信息，请参阅 this work。