为什么 xorshift 随机数生成器在所有示例中使用相同的 "amount" 或 SBR/SBL？

Question

我正在阅读一本解释 xorshift 算法的书（我知道，基本的东西）。然后，在 Internet 上进行更多搜索时，我发现所有基本示例似乎都将位 right/left 移动相同的“数量”(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 运行dom 数字生成器有一个有趣的理论背景故事。移位和 XOR 的使用对应于执行 matrix-vector 乘积，其中矩阵和向量均由 0 和 1 组成。所讨论的特定矩阵是根据移位大小的选择和这些移位的方向导出的。

为了使 RNG 表现良好（具体来说，在生成所有可能值之前不重复任何输出），由移位导出的矩阵必须是可逆的。大多数移位选择不会给出可逆矩阵，xorshift 运行的作者通过计算机搜索找到所有可能的移位大小。在详细介绍 RNG 的 xorshift 系列的论文中，作者 detailed the specific choice of shifts you mentioned 说了以下内容：

It uses one of my favorite choices, [a, b, c] = [13, 17, 5], and will pass almost all tests of randomness, except the binary rank test in Diehard [2]. (A long period xorshift RNG necessarily uses a nonsingular matrix transformation, so every successive n vectors must be linearly independent, while truly random binary vectors will be linearly independent only some 30% of the time.) Although I have only tested a few of them, any one of the 648 choices above is likely to provide a very fast, simple, high quality RNG.

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

为什么 xorshift 随机数生成器在所有示例中使用相同的 "amount" 或 SBR/SBL？

why xorshift random number generator uses the same "amount" of SBR/SBL in all examples?

c++

random

algorithm

xor