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 (LCG) módulo 2n ^. 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 ]}

Las LCG con módulo potencia de 2 son simples, eficientes y tienen salidas binarias distribuidas uniformemente , pero sufren un problema bien conocido de períodos cortos en los bits de orden inferior. ^{[ 5 ] : 31–34}

Un PCG aborda esto agregando una transformación de salida entre el estado del LCG y la salida del PCG. Esto agrega dos elementos al LCG:

• Si es posible, el módulo y el estado LCG se expanden al doble del tamaño de la salida deseada, de modo que los bits de estado de período más corto no afecten en absoluto a la salida, y
• Los bits más significativos del estado se utilizan para seleccionar una rotación o desplazamiento bit a bit que se aplica al estado para producir la salida.

La rotación variable garantiza que todos los bits de salida dependan del bit más significativo del estado, por lo que todos los bits de salida tienen un período completo.

La familia PCG incluye varias variantes. El núcleo LCG está definido para anchos de 8 a 128 bits, 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 puede variarse para producir diferentes flujos. La constante es un entero impar arbitrario , ^{[ 6 ]} por lo que no es necesario almacenarla explícitamente; se puede usar la dirección de la variable de estado misma (con el bit menos significativo activado).

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

• RR: Una 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 más significativos se utilizan para la cantidad de rotación, los siguientes 2 ^{b −1} bits más significativos se rotan a la derecha y se utilizan como salida, y los 2 ^{b −1} +1− b bits menos significativos se descartan.
• RS: Un desplazamiento aleatorio (dependiente de la entrada), para casos donde 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 más significativos se utilizan para un desplazamiento, que se aplica a los siguientes 2 ^{b −1} +2 ^{b −3 −1 bits más significativos, y los 2 b −1} bits menos significativos del resultado se emiten. Los 2 ^{b −1} −2 ^{b −3} − b +4 bits menos significativos se descartan.
• XSH: Una operación de desplazamiento xorx ^= x >> constant . La constante se elige como la mitad de los bits (redondeados hacia abajo) no descartados por la siguiente operación RR o RS.
• XSL: Una versión simplificada de xorshift, que divide el valor por la mitad aplicando la operación XOR entre la mitad superior e inferior. El valor resultante se utiliza para rotaciones posteriores.
• RXS: Un desplazamiento XOR por una cantidad variable (dependiente de la entrada). Los b −2 bits más significativos se utilizan para seleccionar una cantidad de desplazamiento entre b −2 y 2 ^{b −2} + b −3.
• M: Multiplicar por una constante fija.

Cada una de estas operaciones es invertible (y, por lo tanto, biyectiva ) o una truncación (y, por lo tanto ^{, biyectiva} para un k fijo ), de modo 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.

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

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

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

• XSH-RS: Similar, pero con menos bits para seleccionar 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 mediante 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 tamaño reducido; 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 su uso 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: De forma similar a lo anterior, convierte 128 bits de estado en 128 bits de salida, cuando la aplicación lo requiere.

  (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;

Finalmente, si se requiere un período de generación mayor que ^2¹²⁸ , el generador puede extenderse 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 ciclo que proporciona un período igual a 2 elevado a la potencia del tamaño total del estado.

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. Se puede implementar como:

#include <stdint.h> static uint64_t estado = 0x4d595df4d0f33173 ; // O algo que dependa de la semilla static uint64_t const multiplicador = 6364136223846793005u ; static uint64_t const incremento = 1442695040888963407u ; // O una constante impar arbitrariastatic uint32_t rotr32 ( uint32_t x , unsigned r ) { return x >> r | x << ( - r & 31 ); }uint32_t pcg32 ( void ) { uint64_t x = estado ; unsigned count = ( unsigned )( x >> 59 ); // 59 = 64 - 5estado = 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 seed ) { estado = seed + incremento ; ( void ) pcg32 (); }

El generador aplica la transformación de salida al estado inicial en lugar del estado final para aumentar el paralelismo disponible a nivel de instrucciones y 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 ; unsigned count = ( unsigned )( x >> 61 ); // 61 = 64 - 3mcg_state = x * multiplier ; x ^= x >> 22 ; return ( uint32_t )( x >> ( 22 + count )); // 22 = 32 - 3 - 7 }void pcg32_fast_init ( uint64_t seed ) { mcg_state = 2 * seed + 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 supera 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.

O'Neill propone probar los PRNG aplicando pruebas estadísticas a sus variantes de tamaño reducido y determinando el número mínimo 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 deficientes pueden pasar si se les da un estado suficientemente grande; ^{[ 8 ]} pasar a pesar de un estado pequeño es una medida de la calidad de un algoritmo y muestra qué tan 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) supera 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. En comparación, xorshift* , una de las mejores alternativas, requiere 40 bits de estado, ^{[ 5 ] : 19} y Mersenne Twister falla a pesar de 19937 bits de estado. ^{[ 9 ]}

Se ha demostrado que es prácticamente posible (con un cálculo extenso) recuperar la semilla del generador pseudoaleatorio a partir de 512 bytes de salida consecutivos. ^{[ 10 ]} Esto implica que es prácticamente posible predecir el resto de la secuencia pseudoaleatoria a partir de 512 bytes.

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

• PCG, una familia de sitios web de generadores de números aleatorios mejorados
• PCG, una familia de mejores generadores de números aleatorios — ¡inspirado en /r/programming! Discusión en Reddit por el autor