Los generadores de números aleatorios Xorshift , también llamados generadores de registros de desplazamiento , son una clase de generadores de números pseudoaleatorios que fueron inventados por George Marsaglia . [1] Son un subconjunto de los registros de desplazamiento de retroalimentación lineal (LFSR) que permiten una implementación particularmente eficiente en software sin el uso excesivo de polinomios dispersos . [2] Generan el siguiente número en su secuencia tomando repetidamente el o exclusivo de un número con una versión de sí mismo desplazada en bits . Esto hace que la ejecución sea extremadamente eficiente en las arquitecturas informáticas modernas, pero no beneficia la eficiencia en una implementación de hardware. Como todos los LFSR, los parámetros deben elegirse con mucho cuidado para lograr un período largo. [3]
Para la ejecución en software, los generadores xorshift se encuentran entre los PRNG más rápidos, ya que requieren un código y un estado muy pequeños. Sin embargo, no pasan todas las pruebas estadísticas sin un refinamiento adicional. Esta debilidad se corrige al combinarlos con una función no lineal, como se describe en el artículo original. Debido a que los generadores xorshift simples (sin un paso no lineal) no pasan algunas pruebas estadísticas, se los ha acusado de ser poco confiables. [3] : 360
Aquí se proporciona una versión en C [a] de tres algoritmos xorshift [1] : 4,5 . El primero tiene una palabra de estado de 32 bits y un período 2 de 32 −1. El segundo tiene una palabra de estado de 64 bits y un período 2 de 64 −1. El último tiene cuatro palabras de estado de 32 bits y un período 2 de 128 −1. El algoritmo de 128 bits pasa las pruebas más exigentes . Sin embargo, no pasa las pruebas MatrixRank y LinearComp del conjunto de pruebas BigCrush del marco TestU01 .
Todos utilizan tres turnos y tres o cuatro operaciones exclusivas-o:
#include <stdint.h> estructura xorshift32_state { uint32_t a ; }; /* El estado debe inicializarse a un valor distinto de cero */ uint32_t xorshift32 ( struct xorshift32_state * state ) { /* Algoritmo "xor" de la p. 4 de Marsaglia, "Xorshift RNGs" */ uint32_t x = state -> a ; x ^= x << 13 ; x ^= x >> 17 ; x ^= x << 5 ; return state -> a = x ; } estructura xorshift64_state { uint64_t a ; }; uint64_t xorshift64 ( struct xorshift64_state * estado ) { uint64_t x = estado -> a ; x ^= x << 13 ; x ^ = x >> 7 ; x ^= x << 17 ; devolver estado -> a = x ; } /* struct xorshift128_state se puede definir alternativamente como un par de uint64_t o un uint128_t donde sea compatible */ struct xorshift128_state { uint32_t x [ 4 ]; }; /* El estado debe inicializarse a un valor distinto de cero */ uint32_t xorshift128 ( struct xorshift128_state * state ) { /* Algoritmo "xor128" de la p. 5 de Marsaglia, "Xorshift RNGs" */ uint32_t t = state -> x [ 3 ]; uint32_t s = state -> x [ 0 ]; /* Realizar un desplazamiento artificial de 32 bits. */ state -> x [ 3 ] = state -> x [ 2 ]; state -> x [ 2 ] = state -> x [ 1 ]; state -> x [ 1 ] = s ; t ^= t << 11 ; t ^= t >> 8 ; estado de retorno -> x [ 0 ] = t ^ s ^ ( s >> 19 ); } En el caso de una palabra de estado de 64 bits, existen parámetros que contienen el período 2 64 −1 con dos pares de operador exclusivo y desplazamiento. [4]
#include <stdint.h> estructura xorshift64_state { uint64_t a ; }; uint64_t xorshift64 ( struct xorshift64_state * estado ) { uint64_t x = estado -> a ; x ^= x << 7 ; x ^= x >> 9 ; devolver estado -> a = x ; } Todos los generadores xorshift fallan en algunas pruebas del conjunto de pruebas BigCrush . Esto es así para todos los generadores basados en recurrencias lineales, como Mersenne Twister o WELL . Sin embargo, es fácil alterar la salida de dichos generadores para mejorar su calidad.
Los codificadores conocidos como + y * aún dejan debilidad en los bits bajos, [5] por lo que están pensados para uso en punto flotante, donde los bits más bajos de los números de punto flotante tienen un impacto menor en el valor interpretado. [6] Para propósitos generales, el codificador ** (pronunciado starstar ) hace que los generadores LFSR pasen todos los bits.
Marsaglia sugirió alterar la salida combinándola con un contador aditivo simple módulo 2 32 (al que llama una " secuencia de Weyl " en honor al teorema de equidistribución de Weyl ). Esto también aumenta el período en un factor de 2 32 , a 2 192 −2 32 :
#include <stdint.h> estructura xorwow_state { uint32_t x [ 5 ]; uint32_t contador ; }; /* La matriz de estados debe inicializarse para que no sea todo cero en las primeras cuatro palabras */ uint32_t xorwow ( struct xorwow_state * state ) { /* Algoritmo "xorwow" de la p. 5 de Marsaglia, "Xorshift RNGs" */ uint32_t t = state -> x [ 4 ]; uint32_t s = state -> x [ 0 ]; /* Realizar una rotación artificial de 32 bits. */ state -> x [ 4 ] = state -> x [ 3 ]; state -> x [ 3 ] = state -> x [ 2 ]; state -> x [ 2 ] = state -> x [ 1 ]; state -> x [ 1 ] = s ; t ^ = t >> 2 ; t ^= t << 1 ; t ^= s ^ ( s << 4 ); estado -> x [ 0 ] = t ; estado -> contador += 362437 ; devolver t + estado -> contador ; } Esto funciona bien, pero falla en algunas pruebas en BigCrush. [7] Este generador es el predeterminado en el kit de herramientas CUDA de Nvidia . [8]
Un generador xorshift* aplica una multiplicación invertible (módulo del tamaño de la palabra) como una transformación no lineal a la salida de un generador xorshift , como lo sugiere Marsaglia. [1] Todos los generadores xorshift* emiten una secuencia de valores que está equidistribuida en la máxima dimensión posible (excepto que nunca emitirán cero durante 16 llamadas, es decir, 128 bytes, en una fila). [9]
El siguiente generador de 64 bits tiene un período máximo de 2 64 −1. [9]
#include <stdint.h> /* xorshift64s, variante A_1(12,25,27) con multiplicador M_32 de la línea 3 de la tabla 5 */ uint64_t xorshift64star ( void ) { /* la semilla inicial debe ser distinta de cero, no use una variable estática para el estado si es multiproceso */ static uint64_t x = 1 ; x ^= x >> 12 ; x ^= x << 25 ; x ^= x >> 27 ; return x * 0x2545F4914F6CDD1DULL ; } El generador solo falla la prueba MatrixRank de BigCrush, sin embargo, si el generador se modifica para devolver solo los 32 bits altos, entonces pasa BigCrush con cero fallas. [10] : 7 De hecho, una versión reducida con solo 40 bits de estado interno pasa la suite, lo que sugiere un amplio margen de seguridad. [10] : 19 Un generador similar sugerido en Numerical Recipes [11] también RanQ1falla la prueba BirthdaySpacings .
Vigna [9] sugiere el siguiente generador xorshift1024* con 1024 bits de estado y un período máximo de 2 1024 −1; sin embargo, no siempre pasa BigCrush. [5] Por lo tanto, xoshiro256** es una opción mucho mejor.
#include <stdint.h> /* El estado debe inicializarse de modo que haya al menos un elemento distinto de cero en la matriz */ struct xorshift1024s_state { uint64_t x [ 16 ]; int index ; }; uint64_t xorshift1024s ( struct xorshift1024s_state * state ) { int index = state -> index ; uint64_t const s = state -> x [ index ++ ]; uint64_t t = state -> x [ index &= 15 ]; t ^= t << 31 ; // a t ^= t >> 11 ; // b -- Nuevamente, los desplazamientos y los multiplicadores son ajustables t ^= s ^ ( s >> 30 ); // c state -> x [ index ] = t ; state -> index = index ; return t * 1181783497276652981ULL ; } Un generador xorshift+ puede lograr un orden de magnitud menor de fallas que Mersenne Twister o WELL . Una implementación nativa en C de un generador xorshift+ que pase todas las pruebas de la suite BigCrush puede generar típicamente un número aleatorio en menos de 10 ciclos de reloj en x86 , gracias a la canalización de instrucciones . [12]
En lugar de utilizar la multiplicación, es posible utilizar la suma como una transformación no lineal más rápida. La idea fue propuesta por primera vez por Saito y Matsumoto (también responsables del Mersenne Twister) en el generador XSadd , que suma dos salidas consecutivas de un generador xorshift subyacente basado en desplazamientos de 32 bits. [13] Sin embargo, una desventaja de sumar salidas consecutivas es que, mientras que el generador xorshift128 subyacente es equidistribuido bidimensionalmente, el generador xorshift128+ es solo unidimensionalmente equidistribuido. [14]
XSadd tiene algunas debilidades en los bits de orden inferior de su salida; falla varias pruebas de BigCrush cuando las palabras de salida están invertidas en bits. Para corregir este problema, Vigna introdujo la familia xorshift+ , [14] basada en desplazamientos de 64 bits. Los generadores xorshift+ , incluso tan grandes como xorshift1024+ , exhiben cierta linealidad detectable en los bits de orden inferior de su salida; [5] pasa BigCrush, pero no cuando los 32 bits de orden inferior se utilizan en orden inverso desde cada palabra de 64 bits. [5] Este generador es uno de los generadores más rápidos que pasan BigCrush. [12]
El siguiente generador xorshift128+ utiliza 128 bits de estado y tiene un período máximo de 2 128 −1.
#include <stdint.h> estructura xorshift128p_state { uint64_t x [ 2 ]; }; /* El estado debe ser inicializado de modo que no sea todo cero */ uint64_t xorshift128p ( struct xorshift128p_state * state ) { uint64_t t = state -> x [ 0 ]; uint64_t const s = state -> x [ 1 ]; state -> x [ 0 ] = s ; t ^= t << 23 ; // a t ^= t >> 18 ; // b -- Nuevamente, los desplazamientos y los multiplicadores son ajustables t ^= s ^ ( s >> 5 ); // c state -> x [ 1 ] = t ; return t + s ; } El generador xorshiftr+ (r significa reducido; se lee "xorshifter plus") se basó principalmente en xorshift+ pero incorpora modificaciones que lo hacen significativamente más rápido (especialmente en dispositivos livianos) y más exitoso en pruebas de aleatoriedad (incluida la suite BigCrush de TestU01) en comparación con sus predecesores. [15] Es uno de los generadores más rápidos que pasa todas las pruebas en la suite BigCrush de TestU01. Al igual que xorshift+, una implementación nativa en C de un generador xorshiftr+ que pasa todas las pruebas de la suite BigCrush generalmente puede generar un número aleatorio en menos de 10 ciclos de reloj en x86 , gracias a la canalización de instrucciones . [12] [15]
A diferencia de xorshift+ , xorshiftr+ no devuelve la suma de dos variables derivadas del estado mediante pasos de estilo xorshift, sino que devuelve una única variable con la última operación de su ciclo; sin embargo, presenta una adición justo antes de devolver un valor, es decir, en la fase de ajuste de la semilla para el siguiente ciclo; de ahí el "+" en el nombre del algoritmo. Los tamaños de las variables, incluido el estado, se pueden aumentar sin comprometer los puntajes de aleatoriedad, pero se pueden observar caídas de rendimiento en dispositivos livianos.
El siguiente generador xorshiftr128+ utiliza 128 bits de estado (con dos variables) y tiene un período máximo de 2 128 −1.
#include <stdint.h> struct xorshiftr128plus_state { uint64_t s [ 2 ]; // semillas }; /* El estado debe inicializarse de modo que no sea todo cero */ uint64_t xorshiftr128plus ( struct xorshiftr128plus_state * state ) { uint64_t x = state -> s [ 0 ]; uint64_t const y = state -> s [ 1 ]; state -> s [ 0 ] = y ; x ^= x << 23 ; // shift & xor x ^= x >> 17 ; // shift & xor x ^= y ; // xor state -> s [ 1 ] = x + y ; return x ; } xoshiro (abreviatura de "xor, shift, rotate") y xoroshiro (abreviatura de "xor, rotate, shift, rotate") utilizan rotaciones además de desplazamientos. Según Vigna, son más rápidos y producen una salida de mejor calidad que xorshift. [16] [17]
Esta clase de generador tiene variantes para salidas de números enteros y de punto flotante de 32 y 64 bits; para el punto flotante, se toman los 53 bits superiores (para binary64 ) o los 23 bits superiores (para binary32 ), ya que los bits superiores son de mejor calidad que los bits inferiores en los generadores de punto flotante. Los algoritmos también incluyen una jumpfunción que adelanta el estado en una cierta cantidad de pasos, generalmente una potencia de dos que permite que muchos subprocesos de ejecución comiencen en estados iniciales distintos.
Para una salida de 32 bits, xoshiro128** y xoshiro128+ son exactamente equivalentes a xoshiro256** y xoshiro256+, con uint32_t en lugar de uint64_t , y con diferentes constantes de desplazamiento/rotación.
Más recientemente, se han creado los generadores xoshiro++ como una alternativa a los generadores xoshiro** . Se utilizan en algunas implementaciones de compiladores Fortran como GNU Fortran, Java y Julia . [18]
xoshiro256** es el generador de números aleatorios de 64 bits de propósito general de la familia. Se utiliza en el compilador GNU Fortran , Lua (a partir de Lua 5.4) y el marco .NET (a partir de .NET 6.0). [18]
/* Adaptado del código incluido en el sitio web de Sebastiano Vigna */#include <stdint.h> uint64_t rol64 ( uint64_t x , int k ) { devolver ( x << k ) | ( x >> ( 64 - k )); } estructura xoshiro256ss_state { uint64_t s [ 4 ]; }; uint64_t xoshiro256ss ( struct xoshiro256ss_state * estado ) { uint64_t * s = estado -> s ; uint64_t const resultado = rol64 ( s [ 1 ] * 5 , 7 ) * 9 ; uint64_t const t = s [ 1 ] << 17 ; s [ 2 ] ^= s [ 0 ]; s [ 3 ] ^= s [ 1 ]; s [ 1 ] ^= s [ 2 ]; s [ 0 ] ^= s [ 3 ]; s [ 2 ] ^= t ; s [ 3 ] = rol64 ( s [ 3 ], 45 ); devolver resultado ; } xoshiro256+ es aproximadamente un 15% más rápido que xoshiro256**, pero los tres bits más bajos tienen baja complejidad lineal; por lo tanto, debe usarse solo para resultados de punto flotante extrayendo los 53 bits superiores.
#include <stdint.h> uint64_t rol64 ( uint64_t x , int k ) { devolver ( x << k ) | ( x >> ( 64 - k )); } estructura xoshiro256p_state { uint64_t s [ 4 ]; }; uint64_t xoshiro256p ( struct xoshiro256p_state * estado ) { uint64_t * s = estado -> s ; uint64_t const resultado = s [ 0 ] + s [ 3 ]; uint64_t const t = s [ 1 ] << 17 ; s [ 2 ] ^= s [ 0 ]; s [ 3 ] ^= s [ 1 ]; s [ 1 ] ^= s [ 2 ]; s [ 0 ] ^= s [ 3 ]; s [ 2 ] ^= t ; s [ 3 ] = rol64 ( s [ 3 ], 45 ); devolver resultado ; } Si el espacio es limitado, xoroshiro128** y xoroshiro128+ son equivalentes a xoshiro256** y xoshiro256+. Estos tienen espacios de estado más pequeños y, por lo tanto, son menos útiles para programas masivamente paralelos. xoroshiro128+ también exhibe una dependencia leve en el recuento de población , lo que genera una falla después de5 TB de salida. Los autores no creen que esto pueda detectarse en programas del mundo real. En lugar de perpetuar la tradición de Marsaglia decambio de sentidocomo operación básica,xoroshiro128+Utiliza una transformación lineal basada en desplazamiento/rotación diseñada por Sebastiano Vigna en colaboración con David Blackman. El resultado es una mejora significativa en la velocidad y la calidad estadística. [19]
xoroshiro64** y xoroshiro64* son equivalentes a xoroshiro128** y xoroshiro128+. A diferencia de los generadores xoshiro, no son versiones directas de sus contrapartes de mayor precisión.
Los bits más bajos de la salida generada porxoroshiro128+son de baja calidad. Los autores dexoroshiro128+reconoce que no pasa todas las pruebas estadísticas, afirmando
Este es xoroshiro128+ 1.0, nuestro mejor y más rápido generador de estado pequeño para números de punto flotante. Sugerimos usar sus bits superiores para la generación de punto flotante, ya que es ligeramente más rápido que xoroshiro128**. Pasa todas las pruebas que conocemos excepto los cuatro bits inferiores, que podrían fallar las pruebas de linealidad (y solo esas), por lo que si la baja complejidad lineal no se considera un problema (como suele ser el caso) también se puede usar para generar salidas de 64 bits; además, este generador tiene una dependencia muy leve del peso de Hamming, lo que hace que nuestra prueba (http://prng.di.unimi.it/hwd.php) falle después de 5 TB de salida; creemos que este ligero sesgo no puede afectar a ninguna aplicación. Si está preocupado, use xoroshiro128** o xoshiro256+.
Sugerimos utilizar una prueba de signo para extraer un valor booleano aleatorio y desplazamientos a la derecha para extraer subconjuntos de bits.
El estado debe inicializarse de modo que no sea cero en todas partes. Si tiene una semilla de 64 bits, le sugerimos que inicie un generador splitmix64 y use su salida para completar s.
NOTA: los parámetros (a=24, b=16, c=37) de esta versión dan un valor ligeramente
mejores resultados en nuestra prueba que la versión 2016 (a=55, b=14, c=36). [20]
Estas afirmaciones sobre no pasar las pruebas se pueden confirmar ejecutando PractRand en la entrada, lo que da como resultado una salida como la que se muestra a continuación:
Prueba RNG con PractRand versión 0.93RNG = RNG_stdin64, semilla = 0xfac83126conjunto de prueba = normal, plegado = estándar (64 bits)rng=RNG_stdin64, semilla=0xfac83126longitud= 128 megabytes (2^27 bytes), tiempo= 2,1 segundos Nombre de la prueba Crudo Procesado Evaluación [Low1/64]BRank(12):256(2) R= +3748 p~= 3e-1129 ¡¡ ... [Low1/64]BRank(12):384(1) R= +5405 p~= 3e-1628 ¡¡ ... ...y 146 resultados de pruebas sin anomalías
Reconociendo que los autores continúan diciendo:
Sugerimos utilizar una prueba de signos para extraer un valor booleano aleatorio [20]
Por lo tanto, los programadores deberían preferir los bits más altos (por ejemplo, hacer cara o cruz escribiendo random_number < 0en lugar de random_number & 1). Sin embargo, debe tenerse en cuenta que la misma prueba falla en algunas instancias del Mersenne Twister y WELL .
Los problemas estadísticos se extienden mucho más allá de los últimos bits, porque falla la prueba PractRand incluso cuando se trunca [21] y falla múltiples pruebas en BigCrush incluso cuando los bits se invierten. [22]
En el artículo de xoshiro, se recomienda inicializar el estado de los generadores utilizando un generador que sea radicalmente diferente de los generadores inicializados, así como uno que nunca proporcione el estado "todo cero"; para los generadores de registro de desplazamiento, es imposible escapar de este estado. [17] [23] Los autores recomiendan específicamente utilizar el generador SplitMix64, a partir de una semilla de 64 bits, de la siguiente manera:
#include <stdint.h> estructura splitmix64_state { uint64_t s ; }; uint64_t splitmix64 ( struct splitmix64_state * estado ) { uint64_t resultado = ( estado -> s += 0x9E3779B97f4A7C15 ); resultado = ( resultado ^ ( resultado >> 30 )) * 0xBF58476D1CE4E5B9 ; resultado = ( resultado ^ ( resultado >> 27 )) * 0x94D049BB133111EB ; devolver resultado ^ ( resultado >> 31 ); } estructura xorshift128_state { uint32_t x [ 4 ]; }; // se podría hacer lo mismo para cualquiera de los otros generadores void xorshift128_init ( struct xorshift128_state * state , uint64_t seed ) { struct splitmix64_state smstate = { seed }; uint64_t tmp = splitmix64 ( & smstate ); estado -> x [ 0 ] = ( uint32_t ) tmp ; estado -> x [ 1 ] = ( uint32_t )( tmp >> 32 ); tmp = splitmix64 ( & smstate ); estado -> x [ 2 ] = ( uint32_t ) tmp ; estado -> x [ 3 ] = ( uint32_t )( tmp >> 32 ); } ^representa XOR bit a bit , y <<y >>representan desplazamientos bit a bit .Informamos que estos generadores codificados fallan sistemáticamente en Big Crush (específicamente las pruebas de complejidad lineal y rango de matriz que detectan linealidad) al tomar los 32 bits de orden más bajo en orden inverso de cada palabra de 64 bits.