关于Xorshift随机数生成器算法

Question

以下是Xorshift RNG 的基本实现(复制自维基百科):

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实际值.

很奇怪的行为,你不觉得吗？

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
...