En Xorshift de números aleatorios algoritmo generador de

Question

A continuación se presenta una implementación básica de la Xorshift RNG (copiado de la Wikipedia):

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)); 
} 

entiendo que w es el valor devuelto y x, y y z son el estado (variables de "memoria"). Sin embargo, no puedo entender el propósito de más de una variable de memoria. ¿Alguien puede explicarme este punto?

Además, he intentado copiar el código anterior a 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 

Entonces, he generado 100 números y se representaron sus log10 valores:

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

Aquí está la salida de la trama :

y TH es lo que sucede cuando se generan 10000 (y no 100) números:

La tendencia general es muy clara. Y no olvide que el eje Y es log10 del valor real.

Comportamiento bastante extraño, ¿no crees?

Answer 1

El problema aquí es, por supuesto, que está usando Python para hacer esto.

Python tiene una noción de enteros grandes, por lo que aunque está copiando una implementación que trata con números de 32 bits, Python simplemente dice "Voy a seguir adelante y guardar todo para usted".

Si intenta esto en su lugar:

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

Se dará cuenta de que se produce un número cada vez más largos, por ejemplo, aquí está el primer número:

252977563114 

y aquí está la última:

8735276851455609928450146337670748382228073854835405969246191481699954934702447147582960645 

Este es el código que se ha solucionado para manejar esto:

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

"Sin embargo, no puedo entender el propósito de más de una variable de memoria" - si necesita 'recordar' 128 bits, entonces necesita 4 enteros de 32 bits.

En cuanto a la muy extraña distribución de 100 randoms, ni idea! Podría entender si hubiera generado algunos millones, y los pasos en el gráfico fueran artefactos, pero no 100.

Answer 3

Y con un generador:

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