Los generadores congruenciales inversos son un tipo de generador de números pseudoaleatorios congruenciales no lineales , que utilizan el inverso multiplicativo modular (si existe) para generar el siguiente número en una secuencia. La fórmula estándar para un generador congruencial inverso, módulo algún primo q es:
semilla Si Si
Tal generador se denota simbólicamente como ICG (q, a, c, semilla) y se dice que es un ICG con parámetros q , a , cy semilla semilla .
Período
La secuencia debe tener después de un número finito de pasos y dado que el siguiente elemento depende solo de su predecesor directo también etc. La longitud máxima que puede tener el período T para una función módulo q es T = q . Si el polinomio (anillo polinomial sobre ) es primitivo , entonces la secuencia tendrá la longitud máxima. Estos polinomios se denominan polinomios de período máximo inverso (IMP). La condición suficiente para el máximo período de secuencia es una elección adecuada de los parámetros a y c de acuerdo con el algoritmo descrito en. [1] Eichenauer-Herrmann, Lehn, Grothe y Niederreiter han demostrado que los generadores congruentes inversiva tienen buenas propiedades de homogeneidad, en particular con respecto a la estructura de celosía y las correlaciones seriales.
Ejemplo
ICG (5,2,3,1) da la secuencia: (1,0,3,2,4,1, .....) (como en , 1 y 4 son su propio inverso, 2 es el inverso de 3 y viceversa). En este ejemplo es irreductible en ya que ni 0, 1, 2, 3 ni 4 son raíces, y por lo tanto el período es igual a q = 5. Para mostrar que f es primitiva, se debe mostrar que x es un elemento primitivo de.
Generador inversor compuesto
La construcción de un generador inversor compuesto (CIG) se basa en combinar dos o más generadores inversos congruentes de acuerdo con el método que se describe a continuación.
Dejar ser enteros primos distintos, cada uno . Para cada índice j, 1≤ j ≤ r, sea ser una secuencia de elementos de , que es periódica con una duración de período . En otras palabras,.
Para cada índice j, 1≤ j ≤ r, consideramos dónde es la duración del período de la siguiente secuencia .
La secuencia de números pseudoaleatorios compuestos se define como la suma
- .
El enfoque compuesto permite combinar Generadores Congruenciales Inversivos, siempre que tengan período completo, en sistemas de generación en paralelo.
Ejemplo
Dejar y . Para simplificar, tome y . Calculamos para cada 1≤ j≤ 35, luego (tenemos que hacer las 35 sumas diferentes para obtener 0 + 0 y volvemos a comenzar la misma secuencia, el período es ). Este método permite obtener periodos muy largos y se pueden realizar operaciones modulares con módulos relativamente pequeños.
Ventajas de CIG
Los CIG se aceptan con fines prácticos por varias razones.
En primer lugar, las secuencias binarias producidas de esta manera están libres de desviaciones estadísticas indeseables. Las secuencias inversoras ampliamente probadas con una variedad de pruebas estadísticas permanecen estables bajo la variación del parámetro. [2] [3] [4]
En segundo lugar, existe una forma sencilla y estable de elección de parámetros, basada en el algoritmo de Chou [1] que garantiza la máxima duración del período.
En tercer lugar, el enfoque compuesto tiene las mismas propiedades que los generadores inversos individuales [5] [6], pero también proporciona una duración del período significativamente mayor que la obtenida por un generador congruencial inversor único. Parecen estar diseñados para aplicaciones con plataformas de hardware paralelas de multiprocesador.
Existe un algoritmo [7] que permite diseñar generadores compuestos con una duración de período predecible, un nivel de complejidad lineal predecible, con excelentes propiedades estadísticas de los flujos de bits producidos.
El procedimiento de diseño de esta compleja estructura comienza con la definición de campo finito de p elementos y termina con la elección de los parámetros de una y c para cada congruential Generador inversiva siendo el componente del generador de compuesto. Significa que cada generador está asociado a un polinomio IMP fijo. Tal condición es suficiente para el período máximo de cada Generador Congruencial Inversivo [8] y finalmente para el período máximo del generador compuesto. La construcción de polinomios IMP es el enfoque más eficiente para encontrar parámetros para el generador congruencial inversor con la duración máxima del período.
Discrepancia y sus límites
Las propiedades de equidistribución e independencia estadística de las secuencias generadas, que son muy importantes para su usabilidad en una simulación estocástica , se pueden analizar en base a la discrepancia de s-tuplas de números pseudoaleatorios sucesivos con y respectivamente.
La discrepancia calcula la distancia de un generador a uno uniforme, una discrepancia baja significa que la secuencia generada se puede utilizar con fines criptográficos y el primer objetivo del generador congruencial Inversivo es proporcionar números pseudoaleatorios.
Definición
Para N puntos arbitrarios la discrepancia se define por , donde el supremo se extiende sobre todos los subintervalos J de, es veces el número de puntos entre cayendo en J ydenota el s volumen -dimensional de J .
Hasta ahora, teníamos secuencias de números enteros de 0 a , para tener secuencias de , Se puede dividir una secuencia de números enteros por su periodo T .
A partir de esta definición, podemos decir que si la secuencia es perfectamente aleatorio, entonces está bien distribuido en el intervalo luego y todos los puntos están en J así que por eso pero en cambio si la secuencia se concentra cerca de un punto, entonces el subintervalo J es muy pequeño y entonces Luego tenemos el mejor y el peor de los casos:
- .
Notaciones
Es necesaria alguna notación adicional. Para enteros y dejar ser el conjunto de puntos de celosía distintos de cero con por .
Definir
y
por . Verdadero La abreviatura se utiliza, y representa el producto interior estándar de en .
Límite superior
Dejar y ser enteros. Dejar con por .
Entonces la discrepancia de los puntos satisface
- ≤ +
Límite inferior
La discrepancia de puntos arbitrarios satisface
para cualquier punto de celosía distinto de cero , dónde denota el número de coordenadas distintas de cero de .
Estos dos teoremas muestran que el CIG no es perfecto porque la discrepancia es estrictamente mayor que un valor positivo, pero también el CIG no es el peor generador ya que la discrepancia es menor que un valor menor que 1.
También existen teoremas que limitan el valor promedio de la discrepancia para los generadores inversores compuestos y también los que toman valores tales que la discrepancia está limitada por algún valor dependiendo de los parámetros. Para obtener más detalles, consulte el documento original. [9]
Ver también
Referencias
- ^ a b W.S. Chou, Sobre polinomios inversos del período máximo sobre campos finitos , Álgebra aplicable en ingeniería, comunicación y computación, Nº 4/5, 1995, págs. 245-250.
- ^ J. Eichenauer-Herrmannn. Los números pseudoaleatorios congruentes inversos evitan los planos , Math.Comp., Vol. 56, 1991, págs. 297-301.
- ^ J. Eichenauer-Herrmannn, H. Grothe, A. Topuzoglu, Sobre la estructura de celosía de un generador no lineal con módulo, J.Comput. Apl. Math., Vol. 31, 1990, págs. 81-85.
- ^ J. Eichenauer-Herrmannn, H. Niederreiter , Límites inferiores para la discrepancia de números pseudoaleatorios congruentes inversos con potencia de dos módulos , Math. Comp., Vol. 58, 1992, págs. 775-779.
- ^ J. Eichenauer-Herrmannn, Independencia estadística de una nueva clase de números pseudoaleatorios congruentes inversos , Matemáticas. Comp., Vol. 60, 1993, págs. 375-384.
- ^ P. Hellekalek, Generadores de números pseudoaleatorios inverso: conceptos, resultados y vínculos , Actas de la Conferencia de simulación de invierno, 1995, pp 255-262.
- ^ J. Bubicz, J. Stoklosa, Algoritmo de diseño de generador congruencial inversor compuesto , §3.
- ^ H. Niederreiter , Nuevos desarrollos en la generación de vectores y números pseudoaleatorios uniformes , Métodos Monte Carlo y Cuasi-Monte Carlo en Computación Científica, Berlín, 1995.
- ^ J. Eichenauer-Herrmann, F.Emmerich, Números pseudoaleatorios congruentes inversos compuestos: un análisis de caso promedio , American Mathematical Society.