Об алгоритме генератора случайных чисел 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 от фактического значения.

Довольно странное поведение, тебе не кажется?

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

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

Answer 3

«Однако я не могу понять назначение более чем одной переменной памяти» - если вам нужно «запомнить» 128 битов, тогда вам нужно 4 x 32-битных целых числа.

Что касается очень странного распределения 100 рандомов, не знаю! Я мог бы понять, возможно, если вы сгенерировали несколько миллионов, и шаги на графике были артефактами, но не 100.