为什么 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

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

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

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

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

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

Answer 2

原论文中的13、17、5是作者示例中使用的值。 275 个候选集中只有极少数经过实际测试，但在其中 13 个、17 个和 5 个被认为是他的“最爱”，也许是因为它们在某些基准测试中超越了其他候选集。也可能是数学家喜欢那些有趣的素数。无论如何，他暗示 275 个候选值中的任何一个都应该给出良好的结果。我的猜测是人们坚持使用 13、17 和 5，因为它们就像是具有已知功效的事实上的标准。

引用：

与 32 位情况一样，选择 275 个 a、b、c 中的任意一个 64位序列的选择，以及以上八行中的任何一行 C 代码，将为 64 位字提供带有句点的异或移位 RNG 264−1，总共 8×275 = 2200 个选择。这是一个基本的 32 位 采用 32 位种子值的 xorshift C 过程

unsigned long xor(){
static unsigned long y=2463534242;
yˆ=(y<<13); y=(y>>17); return (yˆ=(y<<5)); }

它使用我最喜欢的选择之一，[a, b, c] = [13,17,5]，并且将通过几乎所有的随机性测试，除了 Diehard 中的二元排名测试 [2].y:

论文中的示例中还使用了其他一些集合，包括 13、7 和 17。