Xorshift

I generatori di numeri casuali a disgiunzione esclusiva, anche chiamati generatori di registraturni, sono una classe di generatori di numeri pseudo-casuali che furono inventati da Giorgio Marsaglia. Essi sono una sottoserie di registri a scorrimento a retroazione lineare (LFSR) che permettono una particolare implementazione efficiente in software senza l'eccessivo uso dei polinomi sparsi. Generano il numero successivo in sequenza sostituendo ripetutamente lo xor di un numero con una sua versione bit-shifted. Ciò rende l'esecuzione estremamente efficiente sull'architettura del computer moderno, tuttavia ciò non beneficia sull'efficienza in un'implementazione hardware. Come tutti gli LFSR, i parametri devono essere scelti molto attentamente in modo da raggiungere un lungo periodo.

Esempio di distribuzione casuale di Xorshift128

Per l'esecuzione nel software, i generatori xorshift sono tra i generatori di numeri pseudo-casuali più veloci, e richiedono uno stato e un codice molto piccoli. Tuttavia, non superano ogni test statistico senza una rifinizione ulteriore. Tale debolezza legata a combinarli con una funzione non lineare, come descritto sul foglio di carta originale. Dato che i generatori a disgiunzione esclusiva semplici (senza un passo non lineare) bucano i test statistici, essi sono stati accusati di essere inaffidabili.

Implementazione esemplare

Ecco una versione in linguaggio di programmazione C dei tre algoritmi Xorshift. Il primo ha una parola di stato a 32 bit e un periodo $2^{32}-1$. Il secondo ha una parola di stato a 64 bit e un periodo $2^{64}-1$. L'ultimo ha 4 parole di stato a 32 bit e un periodo $2^{128}-1$. L'algoritmo a 128 bit supera i diehard test ma buca quelli di MatrixRank e di LinearComp della suite dal framework TestU01.

Tutti usano tre scambi e tre o quattro operazioni xor:

#include <stdint.h>

struct xorshift32_state {
    uint32_t a;
};

/* The state must be initialized to non-zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
	/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
	uint32_t x = state->a;
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return state->a = x;
}

struct xorshift64_state {
    uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return state->a = x;
}

/* struct xorshift128_state can alternatively be defined as a pair
   of uint64_t or a uint128_t where supported */
struct xorshift128_state {
    uint32_t x[4];
};

/* The state must be initialized to non-zero */
uint32_t xorshift128(struct xorshift128_state *state)
{
	/* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t t  = state->x[3];
    
    uint32_t s  = state->x[0];  /* Perform a contrived 32-bit shift. */
	state->x[3] = state->x[2];
	state->x[2] = state->x[1];
	state->x[1] = s;

	t ^= t << 11;
	t ^= t >> 8;
	return state->x[0] = t ^ s ^ (s >> 19);
}