Generador congruencial permutado

Un generador congruencial permutado ( PCG ) es un algoritmo de generación de números pseudoaleatorios desarrollado en 2014 por el Dr. ME O'Neill que aplica una función de permutación de salida para mejorar las propiedades estadísticas de un generador congruencial lineal módulo 2 ⁿ . Logra un excelente rendimiento estadístico ^{[1] [2] [3] [4]} con un código pequeño y rápido, y un tamaño de estado pequeño. ^[5]

Un PCG se diferencia de un generador congruencial lineal clásico (LCG) en tres formas:

• El módulo y el estado de LCG son mayores, generalmente el doble del tamaño de la salida deseada,
• Utiliza un módulo de potencia de 2 , lo que da como resultado una implementación particularmente eficiente con un generador de período completo y bits de salida imparciales, y
• El estado no se emite directamente, sino que se utilizan los bits más significativos del estado para seleccionar una rotación o desplazamiento bit a bit que se aplica al estado para producir la salida.

Es la rotación variable la que elimina el problema de un período corto en los bits de orden bajo que padecen los LCG de potencia de 2. ^{[5] : 31–34}

Variantes

La familia PCG incluye varias variantes. El núcleo LCG está definido para anchos de entre 8 y 128 bits ^{[ cita requerida ]} , aunque solo se recomiendan 64 y 128 bits para uso práctico; los tamaños más pequeños se utilizan para pruebas estadísticas de la técnica.

La constante aditiva en el LCG se puede variar para producir diferentes flujos. La constante es un entero impar arbitrario, ^[6] por lo que no necesita almacenarse explícitamente; se puede utilizar la dirección de la variable de estado en sí (con el bit bajo configurado).

Existen varias transformaciones de salida diferentes definidas. Todas funcionan bien, pero algunas tienen un margen mayor que otras. ^{[5] : 39} Se construyen a partir de los siguientes componentes:

• RR: Rotación aleatoria (dependiente de la entrada), con una salida de la mitad del tamaño de la entrada. Dada una palabra de entrada de 2 ^b bits, los b −1 bits superiores se utilizan para la cantidad de rotación, los 2 ^{b −1} bits siguientes más significativos se rotan a la derecha y se utilizan como salida, y los 2 ^{b −1} +1− b bits inferiores se descartan.
• RS: Un desplazamiento aleatorio (dependiente de la entrada), para casos en los que las rotaciones son más costosas. Nuevamente, la salida es la mitad del tamaño de la entrada. Comenzando con una palabra de entrada de 2 ^b bits, los b −3 bits superiores se utilizan para una cantidad de desplazamiento, que se aplica a los 2 ^{b −1} +2 ^{b −3} −1 bits siguientes más significativos , y se emiten los 2 ^{b −1} bits menos significativos del resultado. Los 2 ^{b −1} −2 ^{b −3} − b +4 bits inferiores se descartan.
• XSH: operación xorshiftx ^= x >> constant . La constante se elige para que sea la mitad de los bits que no se descartan en la siguiente operación (redondeados hacia abajo).
• XSL: Una versión simplificada de xorshift, que dobla el valor a la mitad mediante la operación XOR de la mitad superior en la inferior. El valor doblado se utiliza para rotaciones posteriores.
• RXS: Un desplazamiento xorshift de una cantidad aleatoria (dependiente de la entrada).
• M: Una multiplicación por una constante fija.

Estos se combinan en las siguientes transformaciones de salida recomendadas, ilustradas aquí en sus tamaños más comunes:

• XSH-RR: Un xorshift mezcla algunos bits de orden alto hacia abajo, luego los bits 63 a 59 seleccionan una cantidad de rotación que se aplicará a los bits 27 a 58.

  (64→32 bits) count = (int)(x >> 59); x ^= x >> 18; return rotr32((uint32_t)(x >> 27), count); .

• XSH-RS: similar, pero menos bits seleccionan la cantidad de desplazamiento.

  (64→32 bits) count = (int)(x >> 61); x ^= x >> 22; return (uint32_t)(x >> (29 - count)); .

• XSL-RR: una versión simplificada de XSH-RR, optimizada para estados de 128 bits implementados utilizando dos palabras en máquinas de 64 bits.

  (128→64 bits) count = (int)(x >> 122); x64 = (uint64_t)(x ^ (x >> 64)); return rotr64(x64, count);

• RXS-M-XS: la transformación de salida más lenta y potente cuando se utiliza para producir una salida de la mitad del tamaño; se vuelve la más débil cuando se utiliza según lo previsto, para producir una salida del mismo tamaño que el estado. Para usar cuando el tamaño del estado debe limitarse a 32 o 64 bits.

  (32→32 bits) count=(int)(x >> 28); x ^= x >> (4 + count); x *= 277803737u; return x ^ (x >> 22);

  (64→64 bits) count=(int)(x >> 59); x ^= x >> (5 + count); x *= 12605985483714917081u; return x ^ (x >> 43);

• XSL-RR-RR: similar al anterior, convierte 128 bits de estado en 128 bits de salida, cuando la aplicación lo solicita.

  (128→128 bits) count = (int)(x >> 122); low64 = rotr64((uint64_t)(x ^ (x >> 64)), count); high64 = rotr64((uint64_t)(x >> 64), low64 & 63); return (uint128_t)high64 << 64 | low64;

Cada paso de estas transformaciones de salida es invertible (y, por lo tanto, uno a uno ) o un truncamiento, por lo que su composición asigna el mismo número fijo de estados de entrada a cada valor de salida. Esto preserva la equidistribución del LCG subyacente.

Por último, si se requiere una longitud de ciclo superior a 2 ¹²⁸ , el generador se puede ampliar con una matriz de subgeneradores. Se elige uno (en rotación) para agregarlo a la salida del generador principal y, cada vez que el estado del generador principal llega a cero, los subgeneradores se activan en un patrón que proporciona un período exponencial en el tamaño total del estado.

Código de ejemplo

El generador recomendado para la mayoría de los usuarios ^{[5] : 43} es PCG-XSH-RR con estado de 64 bits y salida de 32 bits. Puede implementarse como:

#include <stdint.h> static uint64_t state = 0x4d595df4d0f33173 ; // O algo que dependa de la semilla static uint64_t const multiplier = 6364136223846793005u ; static uint64_t const increment = 1442695040888963407u ; // O una constante impar arbitraria               estático uint32_t rotr32 ( uint32_t x , unsigned r ) { devolver x >> r | x << ( - r & 31 ); }              uint32_t pcg32 ( void ) { uint64_t x = estado ; sin signo recuento = ( sin signo )( x >> 59 ); // 59 = 64 - 5         estado = x * multiplicador + incremento ; x ^= x >> 18 ; // 18 = (64 - 27)/2 return rotr32 (( uint32_t )( x >> 27 ), count ); // 27 = 32 - 5 }              void pcg32_init ( uint64_t semilla ) { estado = semilla + incremento ; ( void ) pcg32 (); }      

El generador aplica la transformación de salida al estado inicial en lugar del estado final para aumentar el paralelismo a nivel de instrucción disponible para maximizar el rendimiento en los procesadores superescalares modernos . ^{[5] : 43}

Una versión ligeramente más rápida elimina el incremento, reduciendo el LCG a un generador multiplicativo ( estilo Lehmer ) con un período de solo 2 ⁶² , y utiliza la función de salida XSH-RS más débil:

static uint64_t mcg_state = 0xcafef00dd15ea5e5u ; // Debe ser impar static uint64_t const multiplier = 6364136223846793005u ;         uint32_t pcg32_fast ( void ) { uint64_t x = mcg_state ; recuento sin signo = ( sin signo )( x >> 61 ); // 61 = 64 - 3         mcg_state = x * multiplicador ; x ^= x >> 22 ; return ( uint32_t )( x >> ( 22 + count )); // 22 = 32 - 3 - 7 }             void pcg32_fast_init ( uint64_t semilla ) { mcg_state = 2 * semilla + 1 ; ( void ) pcg32_fast (); }      

El ahorro de tiempo es mínimo, ya que la operación más costosa (la multiplicación de 64×64 bits) se mantiene, por lo que se prefiere la versión normal, salvo en casos extremos . Aun así, esta versión más rápida también pasa las pruebas estadísticas. ^[4]

Al ejecutarse en un procesador de 32 bits, la multiplicación de 64×64 bits debe implementarse utilizando tres operaciones de multiplicación de 32×32→64 bits. Para reducir esto a dos, existen multiplicadores de 32 bits que funcionan casi tan bien como el de 64 bits, como 0xf13283ad ^[6] , 0xffffffff0e703b65 o 0xf2fc5985.

Comparación con otros generadores de números pseudoaleatorios

Melissa O'Neill propone probar los PRNG aplicando pruebas estadísticas a sus variantes de tamaño reducido y determinando la cantidad mínima de bits de estado interno necesarios para pasar. ^{[7] BigCrush} de TestU01 examina suficientes datos para detectar un período de 2 ³⁵ , por lo que incluso un generador ideal requiere 36 bits de estado para pasarlo. Algunos generadores muy malos pueden pasarlo si se les da un estado lo suficientemente grande; ^[8] pasar a pesar de un estado pequeño es una medida de la calidad de un algoritmo y muestra cuán grande es el margen de seguridad que existe entre ese límite inferior y el tamaño del estado utilizado en aplicaciones prácticas.

PCG-RXS-M-XS (con salida de 32 bits) pasa BigCrush con 36 bits de estado (el mínimo posible), PCG-XSH-RR ( pcg32()arriba) requiere 39 y PCG-XSH-RS ( pcg32_fast()arriba) requiere 49 bits de estado. A modo de comparación, xorshift* , una de las mejores alternativas, requiere 40 bits de estado, ^{[5] : 19} y Mersenne Twister falla a pesar de tener 19937 bits de estado. ^[9]

Predicción y recuperación de semillas

Se ha demostrado que es prácticamente posible (con un cálculo grande) recuperar la semilla del generador pseudoaleatorio dados 512 bytes de salida consecutivos. ^[10] Esto implica que es prácticamente posible predecir el resto del flujo pseudoaleatorio dados 512 bytes.

Véase también

• Ciclo completo
• xoroshiro128+ , xoroshiro128**, xoshiro256+, xoshiro256**: una familia de competidores

Referencias

1. Lemire, Daniel (22 de agosto de 2017). «Prueba de generadores de números aleatorios no criptográficos: mis resultados» . Consultado el 3 de octubre de 2017 .
2. Cook, John D. (7 de julio de 2017). "Prueba del generador de números aleatorios de PCG" . Consultado el 3 de octubre de 2017 .
3. Cook, John D. (14 de agosto de 2017). "Testing RNGs with PractRand" ( Prueba de generadores de números aleatorios con PractRand) . Consultado el 3 de octubre de 2017 .
4. O'Neill, ME (29 de julio de 2017). "PCG Passes PractRand" (PCG aprueba PractRand) . Consultado el 3 de noviembre de 2017 .
5. O'Neill, Melissa E. (5 de septiembre de 2014). PCG: una familia de algoritmos simples, rápidos y con uso eficiente del espacio y estadísticamente buenos para la generación de números aleatorios (PDF) (informe técnico). Harvey Mudd College . HMC-CS-2014-0905.
6. O'Neill, ME (10 de agosto de 2017). "Crítica de las transmisiones de PCG (y también de SplitMix)" . Consultado el 3 de noviembre de 2017 .
7. O'Neill, ME (20 de agosto de 2017). "Visualización del corazón de algunos PRNG" . Consultado el 3 de noviembre de 2017 .
8. O'Neill, ME (20 de agosto de 2017). "Too Big to Fail" (Demasiado grande para quebrar) . Consultado el 3 de noviembre de 2017 .
9. L'Ecuyer, Pierre; Simard, Richard (agosto de 2007). "TestU01: biblioteca de CA para pruebas empíricas de generadores de números aleatorios" (PDF) . ACM Transactions on Mathematical Software . 33 (4): 22-1–22-40. CiteSeerX 10.1.1.499.2830 . doi :10.1145/1268776.1268777. S2CID  273446. 
10. Bouillaguet, Charles; Martinez, Florette; Sauvage, Julia (28 de septiembre de 2020). "Recuperación práctica de semillas para el generador de números pseudoaleatorios PCG". Transacciones IACR sobre criptología simétrica . 2020 (3): 175–196. doi :10.13154/tosc.v2020.i3.175-196. S2CID  222137612.

Enlaces externos

• PCG, una familia de mejores generadores de números aleatorios
• PCG, una familia de mejores generadores de números aleatorios, ¡inspirados en /r/programming! Discusión en Reddit del autor