如何测试CRC32C是否是"好"的随机发生器？

Question

我最近发现_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发电机"失败了一些统计测试,他们被指责为不可靠".

现在我想知道CRC32C方法是否通过了对随机数生成器进行的各种测试.我只是通过尝试使用PAQ8压缩器(失败)进行压缩来验证每个位,甚至LSB都是"随机的".有人可以帮我做更好的测试吗？

编辑:使用建议的TestU01套件中的测试,我之前使用的方法比xorshift32更差.我已更新上面的源代码,以防任何人有兴趣使用更好的版本.

Answer 1

这是个有趣的问题.最重要的是,唯一重要的考验是"这对我正在研究的问题产生了正确的结果".你想用rng做什么？

为了避免针对每个不同的问题回答该问题,已经设计了各种测试.例如,参见George Marsaglia设计的"Diehard"测试.对"marsaglia随机数生成器测试"的网络搜索发现了几个有趣的链接.

我认为Marsaglia的工作已经有几十年了.从那时起,我不知道这个话题是否有更多的工作要做.我的猜测是,对于非加密目的,通过Diehard测试的rng可能就足够了.