关于Xorshift随机数生成算法

Question

以下是Xorshift随机数生成器的基本实现（摘自维基百科）：

uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;

  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

我了解到w是返回值，x，y和z是状态（“内存”）变量。然而，我不明白为什么需要多个内存变量的目的。有人能解释一下吗？

此外，我试图将上述代码复制到Python中：

class R2:
    def __init__(self):
        self.x = x = 123456789
        self.y = 362436069
        self.z = 521288629
        self.w = 88675123
    def __call__(self):
        t = self.x ^ (self.x<<11)
        self.x = self.y
        self.y = self.z
        self.z = self.w
        w = self.w
        self.w = w ^ (w >> 19) ^(t ^ (t >> 8))
        return self.w

接下来，我生成了100个数字，并绘制了它们的log10值：

r2 = R2()
x2 = [math.log10(r2()) for _ in range(100)]
plot(x2, '.g')

这是图表的输出结果：

当生成10000个数字（而不是100个）时，会发生以下情况： 总体趋势非常明显。不要忘记Y轴是实际值的log10。

相当奇怪的行为，你觉得呢？

- Boris Gorelik

---

log10的输出应该是你的线索，32位最大值的log10是9点几，而不是100。 - Lasse V. Karlsen

Answer 1

这里的问题当然是你正在使用Python来执行此操作。

Python有一个大整数的概念，所以即使你复制了一个处理32位数字的实现，Python仍然会说"我会为你保留所有东西"。

如果你尝试使用以下方法：

x2 = [r2() for _ in range(100)]
print(x2);

您会发现它生成的数字越来越长，例如这是第一个数字：

252977563114

这是最后一段：

8735276851455609928450146337670748382228073854835405969246191481699954934702447147582960645

以下是已经修正过的代码，可以处理此问题:

...
def __call__(self):
    t = self.x ^ (self.x<<11) & 0xffffffff                   # <-- keep 32 bits
    self.x = self.y
    self.y = self.z
    self.z = self.w
    w = self.w
    self.w = (w ^ (w >> 19) ^(t ^ (t >> 8))) & 0xffffffff    # <-- keep 32 bits
    return self.w
...

- Lasse V. Karlsen

Answer 2

使用生成器：

def xor128():
  x = 123456789
  y = 362436069
  z = 521288629
  w = 88675123
  while True:
    t = (x ^ (x<<11)) & 0xffffffff
    (x,y,z) = (y,z,w)
    w = (w ^ (w >> 19) ^ (t ^ (t >> 8))) & 0xffffffff
    yield w

- Aristide

Answer 3

"然而，我不明白为什么需要多个内存变量的目的" - 如果你需要“记住”128位，则需要4个32位整数。

至于100个随机数的非常奇怪的分布，我不知道！也许如果你生成了几百万个，并且图表中的步骤是人为因素，那就可以理解，但不是100个。

- Mitch Wheat