为什么 xorshift 随机数生成器似乎总是使用这些特定的移位？

Question

我正在读一本解释异或移位算法的书（我知道，基本的东西）。然后，在互联网上进行更多搜索时，我发现所有基本示例似乎都将位右移/左移相同的“量”（13、17、5）。

例如：

struct xorshift32_state {
  uint32_t a;
};

uint32_t xorshiftTransform(struct xorshift32_state *state) {
    uint32_t x = state->a;

    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    
    return state->a = x;
}

13他们在所有示例中使用,17和是否有特殊原因5？是的，我也找到了其他例子，但这个例子一直在重复，我不知道数字选择是否微不足道。

Answer 1

这实际上比您想象的要微妙和有趣得多！

\n

xorshift 随机数生成器有一个有趣的理论背景。移位和 XOR 的使用对应于执行矩阵向量乘积，其中矩阵和向量均由 0 和 1 组成。所讨论的具体矩阵是根据班次大小和班次方向的选择得出的。

\n

为了使 RNG 表现良好（具体来说，在生成所有可能的值之前不重复任何输出），由移位导出的矩阵必须是可逆的。大多数移位选择不会给出可逆矩阵，xorshift 的作者进行了计算机搜索以找到所有可能有效的移位大小。在详细介绍 RNG 的 xorshift 系列的论文中，作者详细介绍了您提到的移位的具体选择，并说道：

\n

\n

它使用我最喜欢的选择之一，[a, b, c] = [13, 17, 5]，并且将通过几乎所有随机性测试，除了 Diehard [2] 中的二进制排名测试。（长周期 xorshift RNG 必然使用非奇异矩阵变换，因此每个连续的 n 个向量必须是线性独立的，而真正随机的二进制向量只有大约 30% 的时间是线性独立的。）尽管我只测试了其中的几个，上述 648 个选择中的任何一个都可能提供非常快速、简单、高质量的 RNG。

\n

\n

所以从某种意义上说，这些数字满足了数学计算使其成为一个好的 RNG 所需的理论必要条件，并且作者对其进行了测试并在原始论文中将它们挑出来，这就是为什么 I\xe2\x80\x99m猜测它们\xe2\x80\x99的使用如此广泛。但也许有更好的选择，使用论文中的其他数字，而人们还没有抽出时间来使用？

\n