Los generadores de números aleatorios Xorshift , también llamados generadores de registro de desplazamiento, son una clase de generadores de números pseudoaleatorios que fueron descubiertos por George Marsaglia . [1] Son un subconjunto de registros de desplazamiento de retroalimentación lineal (LFSR) que permiten una implementación particularmente eficiente en software sin utilizar polinomios excesivamente dispersos. [2] Generan el siguiente número en su secuencia tomando repetidamente el exclusivo o de un número con un bit desplazadoversión de sí mismo. Esto hace que se ejecuten de manera extremadamente eficiente en arquitecturas de computadoras 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 prolongado. [3]
Para su ejecución en software, los generadores xorshift se encuentran entre los generadores de números aleatorios no criptográficamente seguros más rápidos , y requieren un código y un estado muy pequeños. Sin embargo, no pasan todas las pruebas estadísticas sin un mayor refinamiento. Esta debilidad es bien conocida y se corrige (como señaló Marsaglia en el artículo original) combinándolas con una función no lineal, lo que da como resultado, por ejemplo, un generador xorshift + o xorshift *. Una implementación nativa en C de un generador xorshift + que pasa todas las pruebas de la suite BigCrush (con un orden de magnitud menos fallas que Mersenne Twister o WELL ) generalmente toma menos de 10 ciclos de reloj en x86 para generar un número aleatorio, gracias a la canalización de instrucciones . [4]
Los codificadores conocidos como + y * todavía dejan puntos débiles en los bits bajos, [5] por lo que están destinados al uso de punto flotante, ya que la conversión de un número aleatorio en punto flotante descarta los bits bajos. Para fines generales, el codificador ** (pronunciado 'estrella estelar') hace que los generadores LFSR pasen todos los bits.
Debido a que los generadores xorshift simples (sin un paso no lineal) fallan en algunas pruebas estadísticas, se les ha acusado de no ser confiables. [3] : 360
Implementación de ejemplo
A C versión [a] de tres algoritmos xorshift [1] : 4,5 se da aquí. El primero tiene una palabra de estado de 32 bits y el período 2 32 -1. El segundo tiene una palabra de estado de 64 bits y un período 2 64 -1. El último tiene cuatro palabras de estado de 32 bits y un período de 2 128 −1. Todos utilizan tres turnos y tres o cuatro operaciones exclusivas o:
#include struct xorshift32_state { uint32_t a ; };/ * La palabra de estado debe inicializarse a un valor distinto de cero * / uint32_t xorshift32 ( struct xorshift32_state * state ) { / * Algoritmo "xor" de p. 4 de Marsaglia, "Xorshift RNGs" * / uint32_t x = estado -> a ; x ^ = x << 13 ; x ^ = x >> 17 ; x ^ = x << 5 ; estado de retorno -> a = x ; } struct 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 ; estado de retorno -> a = x ; } struct xorshift128_state { uint32_t a , b , c , d ; };/ * La matriz de estado debe inicializarse para que no sea todo cero * / uint32_t xorshift128 ( struct xorshift128_state * state ) { / * Algoritmo "xor128" de p. 5 de Marsaglia, "Xorshift RNGs" * / uint32_t t = estado -> d ;uint32_t const s = estado -> a ; estado -> d = estado -> c ; estado -> c = estado -> b ; estado -> b = s ;t ^ = t << 11 ; t ^ = t >> 8 ; estado de retorno -> a = t ^ s ^ ( s >> 19 ); }
El algoritmo de 128 bits pasa las pruebas más duras . Sin embargo, falla las pruebas MatrixRank y LinearComp del conjunto de pruebas BigCrush del marco TestU01 .
Variaciones
Todos los generadores xorshift fallan en algunas pruebas del conjunto de pruebas BigCrush de TestU01 . Esto es cierto para todos los generadores basados en recurrencias lineales, como el Mersenne Twister o WELL . Sin embargo, es fácil codificar la salida de dichos generadores para mejorar su calidad.
xorwow
Marsaglia sugirió codificar la salida combinándola con un contador aditivo simple módulo 2 32 (que él llama una "secuencia de Weyl" después del 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 struct xorwow_state { uint32_t a , b , c , d , e ; contador uint32_t ; };/ * La matriz de estado debe inicializarse para que no sea todo cero en las primeras cuatro palabras * / uint32_t xorwow ( struct xorwow_state * state ) { / * Algoritmo "xorwow" de p. 5 de Marsaglia, "Xorshift RNGs" * / uint32_t t = estado -> e ; uint32_t s = estado -> a ; estado -> e = estado -> d ; estado -> d = estado -> c ; estado -> c = estado -> b ; estado -> b = s ; t ^ = t >> 2 ; t ^ = t << 1 ; t ^ = s ^ ( s << 4 ); estado -> a = t ; estado -> contador + = 362437 ; return t + estado -> contador ; }
Esto funciona bien, pero falla algunas pruebas en BigCrush. [6] Este generador es el predeterminado en el kit de herramientas CUDA de Nvidia . [7]
xorshift *
A xorshift * generador toma un xorshiftgenerador y aplica una multiplicación invertible (módulo del tamaño de la palabra) a su salida como una transformación no lineal, como sugiere Marsaglia. [1] El siguiente generador de 64 bits con 64 bits de estado tiene un período máximo de 2 64 −1 [8] y solo falla la prueba MatrixRank de BigCrush:
#include struct xorshift64s_state { uint64_t a ; };uint64_t xorshift64s ( struct xorshift64s_state * estado ) { uint64_t x = estado -> a ; / * El estado se debe sembrar con un valor distinto de cero. * / x ^ = x >> 12 ; // a x ^ = x << 25 ; // b x ^ = x >> 27 ; // c estado -> a = x ; return x * UINT64_C ( 0x2545F4914F6CDD1D ); }
Se sugiere un generador similar en Numerical Recipes [9] como RanQ1
, pero también falla la prueba BirthdaySpacings.
Si el generador se modifica para devolver solo los 32 bits altos, pasa a BigCrush sin fallas. [10] : 7 De hecho, una versión reducida con solo 40 bits de estado interno pasa la suite, lo que sugiere un gran margen de seguridad. [10] : 19
Vigna [8] sugiere lo siguientexorshift1024 *generador con 1024 bits de estado y un período máximo de 2 1024 −1; sin embargo, no siempre pasa BigCrush. [5] xoshiro256 ** es, por tanto, una opción mucho mejor.
#include / * El estado debe sembrarse de modo que haya al menos un elemento distinto de cero en la matriz * / struct xorshift1024s_state { uint64_t matriz [ 16 ]; int index ; };uint64_t xorshift1024s ( struct xorshift1024s_state * state ) { int index = state -> index ; uint64_t const s = estado -> matriz [ índice ++ ]; uint64_t t = estado -> matriz [ índice & = 15 ]; t ^ = t << 31 ; // a t ^ = t >> 11 ; // b t ^ = s ^ ( s >> 30 ); // c estado -> matriz [ índice ] = t ; estado -> índice = índice ; return t * ( uint64_t ) 1181783497276652981 ; }
Ambos generadores, como ocurre con todos xorshift *generadores, emiten una secuencia de valores de 64 bits que se equidistribuyen en la máxima dimensión posible (excepto que nunca generarán cero para 16 llamadas, es decir, 128 bytes, seguidos). [8]
xorshift +
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 agrega dos salidas consecutivas de un subyacentexorshiftgenerador basado en turnos de 32 bits. [11]
XSadd, sin embargo, tiene alguna debilidad en los bits de bajo orden de su salida; falla varias pruebas de BigCrush cuando las palabras de salida están invertidas en bits. Para corregir este problema, Vigna [12] introdujo elxorshift + familia, basada en cambios de 64 bits: lo siguiente xorshift128 +El generador usa 128 bits de estado y tiene un período máximo de 2 128 −1. Pasa BigCrush, pero no cuando se invierte. [5]
#include struct xorshift128p_state { uint64_t a , b ; };/ * El estado debe ser sembrado para que no sea todo cero * / uint64_t xorshift128p ( struct xorshift128p_state * state ) { uint64_t t = state -> a ; uint64_t const s = estado -> b ; estado -> a = s ; t ^ = t << 23 ; // a t ^ = t >> 17 ; // b t ^ = s ^ ( s >> 26 ); // c estado -> b = t ; return t + s ; }
Este generador es uno de los generadores más rápidos que pasan BigCrush. [4] Una desventaja de agregar resultados consecutivos es que mientras elxorshift128 generador es bidimensionalmente equidistribuido, el asociado xorshift128 +El generador solo está equidistribuido unidimensionalmente. [12]
Generadores Xorshift +, incluso tan grandes como xorshift1024 +, exhiben cierta linealidad detectable en los bits de orden inferior de su salida. [5]
xoshiro y xoroshiro
xoshiro y xoroshiro son otras variaciones de los generadores de registro de desplazamiento, que utilizan rotaciones además de cambios. Según Vigna, son más rápidos y producen resultados de mejor calidad que xorshift. [13] [14]
Esta clase de generador tiene variantes para la salida de punto flotante y entero de 32 y 64 bits; para coma 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 coma flotante. Los algoritmos también incluyen una jump
función, que adelanta el estado en una serie de pasos, generalmente una potencia de dos que permite que muchos subprocesos de ejecución comiencen en estados iniciales distintos.
xoshiro256 **
xoshiro256 ** es el generador de números aleatorios de 64 bits de propósito general de la familia.
/ * Adaptado del código incluido en la web de Sebastian Vigna * /#include uint64_t rol64 ( uint64_t x , int k ) { return ( x << k ) | ( x >> ( 64 - k )); }struct xoshiro256ss_state { uint64_t s [ 4 ]; };uint64_t xoshiro256ss ( struct xoshiro256ss_state * estado ) { uint64_t * s = estado -> s ; uint64_t resultado constante = 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 +
xoshiro256 + es aproximadamente un 15% más rápido que xoshiro256 **, pero los tres bits más bajos tienen una complejidad lineal baja; por lo tanto, debe usarse solo para resultados de coma flotante extrayendo los 53 bits superiores.
#include uint64_t rol64 ( uint64_t x , int k ) { return ( x << k ) | ( x >> ( 64 - k )); }struct xoshiro256p_state { uint64_t s [ 4 ]; };uint64_t xoshiro256p ( struct xoshiro256p_state * state ) { uint64_t ( * s ) [ 4 ] = & state -> s ; uint64_t resultado constante = 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 ; }
Otras variantes
Si el espacio es escaso, xoroshiro128 ** es el equivalente de xoshiro256 **, y xoroshiro128 + es el equivalente de 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 los pesos de Hamming, generando una falla después de 5 TB de salida. Los autores no creen que esto pueda detectarse en programas del mundo real.
Para la 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; de manera similar, xoroshiro64 ** y xoroshiro64 * son el equivalente de xoroshiro128 ** y xoroshiro128 + respectivamente. A diferencia de las funciones con estado más grande, xoroshiro64 ** y xoroshiro64 * no son puertos sencillos de sus contrapartes de mayor precisión.
Más recientemente, los generadores ++ se han fabricado como una alternativa a los generadores **.
Inicialización
Es la recomendación de los autores del artículo de xoshiro inicializar el estado de los generadores usando un generador que sea radicalmente diferente de los generadores inicializados, así como uno que nunca dará el estado "todo-cero"; para los generadores de registro de desplazamiento, es imposible escapar de este estado. [14] [15] Los autores recomiendan específicamente usar el generador SplitMix64, a partir de una semilla de 64 bits, de la siguiente manera:
#include struct splitmix64_state { uint64_t s ; };uint64_t splitmix64 ( struct splitmix64_state * state ) { uint64_t result = ( state -> s + = 0x9E3779B97f4A7C15 ); resultado = ( resultado ^ ( resultado >> 30 )) * 0xBF58476D1CE4E5B9 ; resultado = ( resultado ^ ( resultado >> 27 )) * 0x94D049BB133111EB ; devuelve resultado ^ ( resultado >> 31 ); }// como ejemplo; se podría hacer lo mismo para cualquiera de los otros generadores struct xorshift128_state xorshift128_init ( uint64_t seed ) { struct splitmix64_state smstate = { seed }; struct xorshift128_state result = { 0 };uint64_t tmp = splitmix64 ( & smstate ); resultado . a = ( uint32_t ) tmp ; resultado . b = ( uint32_t ) ( tmp >> 32 );tmp = splitmix64 ( & smstate ); resultado . c = ( uint32_t ) tmp ; resultado . d = ( uint32_t ) ( tmp >> 32 );devolver resultado ; }
Notas
- ^ En C y la mayoría de los otros lenguajes basados en C, el signo de intercalación (
^
) representa el XOR bit a bit , y losoperadores"<<
" y ">>
" representan cambios bit a bit a la izquierda y a la derecha, respectivamente.
Referencias
- ↑ a b c Marsaglia, George (julio de 2003). "Xorshift RNG" . Revista de software estadístico . 8 (14). doi : 10.18637 / jss.v008.i14 .
- ^ Brent, Richard P. (agosto de 2004). "Nota sobre los generadores de números aleatorios Xorshift de Marsaglia" . Revista de software estadístico . 11 (5). doi : 10.18637 / jss.v011.i05 .
- ^ a b Panneton, François; L'Ecuyer, Pierre (octubre de 2005). "En los generadores de números aleatorios xorshift" (PDF) . Transacciones ACM sobre modelado y simulación por computadora . 15 (4): 346–361. doi : 10.1145 / 1113316.1113319 . S2CID 11136098 .
- ^ a b Vigna, Sebastiano. "xorshift * / xorshift + generators y el tiroteo PRNG" . Consultado el 25 de octubre de 2014 .
- ^ a b c d Lemire, Daniel; O'Neill, Melissa E. (abril de 2019). "Xorshift1024 *, Xorshift1024 +, Xorshift128 + y Xoroshiro128 + fallan las pruebas estadísticas de linealidad". Matemática Computacional y Aplicada . 350 : 139-142. arXiv : 1810.05313 . doi : 10.1016 / j.cam.2018.10.019 . S2CID 52983294 .
Informamos que estos generadores codificados fallan sistemáticamente en Big Crush, específicamente las pruebas de complejidad lineal y rango de matriz que detectan la linealidad, al tomar los 32 bits de orden más bajo en orden inverso de cada palabra de 64 bits.
- ^ Le Floc'h, Fabien (12 de enero de 2011). "Resultados XORWOW L'ecuyer TestU01" . Chase The Devil (blog) . Consultado el 2 de noviembre de 2017 .
- ^ "Pruebas cuRAND" . Nvidia . Consultado el 2 de noviembre de 2017 .
- ^ a b c Vigna, Sebastiano (julio de 2016). "Una exploración experimental de los generadores xorshift de Marsaglia, codificados" (PDF) . Transacciones ACM en software matemático . 42 (4): 30. arXiv : 1402.6246 . doi : 10.1145 / 2845077 . S2CID 13936073 . Propone generadores xorshift *, sumando una multiplicación final por una constante.
- ^ Presione, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (2007). "Sección 7.1.2.A. Método Xorshift de 64 bits" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
- ^ a b O'Neill, Melissa E. (5 de septiembre de 2014). PCG: Una familia de algoritmos estadísticamente buenos, simples, rápidos y eficientes en el espacio para la generación de números aleatorios (PDF) (Informe técnico). Universidad Harvey Mudd . págs. 6–8. HMC-CS-2014-0905.
- ^ Saito, Mutsuo; Matsumoto, Makoto (2014). "XORSHIFT-ADD (XSadd): una variante de XORSHIFT" . Consultado el 25 de octubre de 2014 .
- ^ a b Vigna, Sebastiano (mayo de 2017). "Más codificaciones de los generadores xorshift de Marsaglia" (PDF) . Revista de Matemática Computacional y Aplicada . 315 (C): 175–181. arXiv : 1404.0390 . doi : 10.1016 / j.cam.2016.11.006 . S2CID 6876444 . Describe los generadores xorshift +, una generalización de XSadd.
- ^ Vigna, Sebastiano. "Generadores xoshiro / xoroshiro y el tiroteo PRNG" . Consultado el 7 de julio de 2019 .
- ^ a b Blackman, David; Vigna, Sebastiano (2018). "Generadores de números pseudoaleatorios lineales codificados". arXiv : 1805.01407 . Cite journal requiere
|journal=
( ayuda ) - ^ Matsumoto, Makoto; Wada, Isaku; Kuramoto, Ai; Ashihara, Hyo (septiembre de 2007). "Defectos comunes en la inicialización de generadores de números pseudoaleatorios". Transacciones ACM sobre modelado y simulación por computadora . 17 (4): 15 – es. doi : 10.1145 / 1276927.1276928 . S2CID 1721554 .
Otras lecturas
- Brent, Richard P. (julio de 2006). "Algunos generadores de números aleatorios de largo período que utilizan cambios y xors" . Diario ANZIAM . 48 : C188 – C202. Enumera generadores de varios tamaños con cuatro turnos (dos por palabra de retroalimentación).