Método congruente inverso

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de abril de 2020; las comprobaciones requieren 3 ediciones .

El método congruencial inverso (o generador de Eichenauer-Lehn , también posiblemente Eichenauer-Lehn ) es un método de generación de números pseudoaleatorios basado en el uso del número de módulo inverso para generar el siguiente miembro de la secuencia.

Descripción

El método congruencial inverso fue propuesto por Eichenauer y Lehn en 1986 [1] como reemplazo del método congruencial lineal sin celosía [2] .

Este método consiste en calcular una secuencia de números aleatorios en el anillo de residuos módulo un número natural . $X_{{n}}$ $norte$

La principal diferencia con el método lineal es que al generar una secuencia, se utiliza el número inverso al elemento anterior en lugar del elemento anterior en sí.

Los parámetros del generador son [3] :

$semilla$ - sal
$a$ - multiplicador $(0\leqslant a<n)$
$b$ - incremento $(0\leqslant b<n)$

En el caso de una n simple

El valor de los miembros de la secuencia se da como:

$x_{0}=semilla$
$x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n$	si $x_{i}\neq 0$
$x_{i+1}=b$	si $x_{i}=0$

En el caso de n compuesto

Si el número es compuesto, los elementos de la secuencia se calculan de la siguiente manera: $X_{{n}}$

$x_{0}=semilla$
$x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n$

Los parámetros se eligen de tal manera que . $(semilla,n)=1;(a,n)=1$

Período

La secuencia es periódica y el período no excede la dimensión del anillo . El período máximo se alcanza si el polinomio es primitivo . Una condición suficiente para el período máximo de la secuencia es tal elección de constantes y que el polinomio sea irreducible [4] . $x_{i+1}$ $norte$ $norte$ $f(x)=x^{2}-bx-a\in \mathbb {F} _{n}[x]$ $a$ $b$ $f(x)$

En el caso de un compuesto, el período máximo posible es ( función de Euler ) [5] . $norte$ $\varfi (n)$

Ejemplo

El generador de congruencia inversa con parámetros genera una secuencia en el anillo , donde los números y , así como y son inversos entre sí. En este ejemplo, el polinomio es irreducible en y los números no son sus raíces, por lo que el periodo es máximo e igual a . $n=5,a=2,b=3,semilla=1$ $\{1,0,3,2,4,1,...\}$ $\mathbb {F} _{5}$ $una$ $cuatro$ $2$ $3$ $f(x)=x^{2}-3x-2$ $\mathbb {F} _{5} [x]$ $0.1.2.3.4$ $n=5$

Ejemplos de implementación

Pitón

El código def egcd ( a , b ): if a == 0 : return ( b , 0 , 1 ) else : g , y , x = egcd ( b % a , a ) return ( g , x - ( b // a ) * y , y ) def modinv ( a , m ): gcd , x , y = egcd ( a , m ) if gcd != 1 : return Ninguno # modular inverse no existe else : return x % m def ICG ( n , a , c , semilla ): if ( semilla == 0 ): return c return ( a * modinv ( semilla , n ) + c ) % n semilla = 1 n = 5 a = 2 c = 3 cuenta = 10 para i en el rango ( recuento ): imprimir ( semilla ) semilla = ICG ( n , a , c , semilla )

C++

El código #incluir <iostream> utilizando el espacio de nombres estándar ; int mod_inv ( int a , int n ) { int b0 = norte , t , q ; intx0 = 0 , x1 = 1 ; _ si ( n == 1 ) devuelve 1 ; mientras ( un > 1 ) { q = un / n ; t = norte , norte = un % norte , un = t ; t = x0 , x0 = x1 - q * x0 , x1 = t ; } si ( x1 < 0 ) x1 += b0 ; devolver x1 ; } int ICG ( int n , int a , int c , int semilla ) { si ( semilla == 0 ) devolver c ; return ( a * mod_inv ( semilla , n ) + c ) % n ; } int principal ( vacío ) { semilla int = 1 ; entero n = 5 ; int a = 2 ; int c = 3 ; número int = 10 ; para ( int i = 0 ; i < cuenta ; i ++ ) { cout << semilla << endl ; semilla = ICG ( n , a , c , semilla ); } devolver 0 ; }

Generadores inversos compuestos

La principal desventaja de los generadores congruentes inversos es el aumento de la complejidad computacional con el aumento del período. Esta deficiencia se corrige en los generadores congruenciales inversos compuestos.

La construcción de generadores inversos compuestos es una combinación de dos o más generadores inversos congruentes.

Sean números primos distintos, cada uno . Para cada índice dentro de , sea una secuencia de elementos con punto . En otras palabras, . $p_{1},\puntos,p_{r}$ $p_{j}\geq 5$ $j$ $1\leq j\ \leq r$ $\{y_{n}^{(j)}\}_{n\geq 0}$ $\in \mathbb {F} _{p_{j}}$ $p_{j}$ $\{y_{n}^{(j)}|0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}$

Sea una secuencia de números aleatorios dentro de , donde . $\{x_{n}^{(j)}\}_{n\geq 0}$ $x_{n}^{(j)}\en [0;1]$ $x_{n}^{(j)}={\frac {y_{n}^{(j)}}{p_{j}}};{n\geq 0};1\leq j\ \leq r$

La secuencia resultante se define como la suma de: . $(x_{n})_{n\geq 0}$ $x_{n}:=x_{n}^{(1)}+x_{n}^{(2)}+\puntos +x_{n}^{(r)}\mod 1$

El período de la secuencia resultante [6] . $T=p_{1}p_{2}\puntos p_{r}$

Una de las ventajas de este enfoque es la capacidad de utilizar generadores congruentes inversos que funcionan en paralelo.

Un ejemplo de un generador inverso compuesto

Sea y . Para simplificar, pongamos y . Para cada uno calculamos . $r=2,p_{1}=5$ $p_{2}=7$ $(y_{k}^{(1)})_{k\geq 0}=(0,1,2,3,4,\puntos)$ $(y_{k}^{(2)})_{k\geq 0}=(0,1,2,3,4,5,6,\puntos)$ $1\leq n\leq 35$ $x_{n}={\frac {y_{n}^{(1)}}{5}}+{\frac {y_{n}^{(2))){7}}$

entonces _ Es decir, obtuvimos una secuencia con un punto . $(x_{n})_{n\geq 0}=\{0.0,$ ${\ estilo de visualización}$ $0.34$ ${\ estilo de visualización}$ $0,69$ ${\ estilo de visualización}$ $0.03,$ ${\ estilo de visualización}$ $0.37$ ${\ estilo de visualización}$ $0.71$ ${\ estilo de visualización}$ $0.06,$ ${\ estilo de visualización}$ $0.4$ ${\ estilo de visualización}$ $0.74$ ${\ estilo de visualización}$ $0.09,$ ${\ estilo de visualización}$ $0.43$ ${\ estilo de visualización}$ $0.77$ ${\ estilo de visualización}$ $0.11$ ${\ estilo de visualización}$ $0,46$ ${\ estilo de visualización}$ $0.8$ ${\ estilo de visualización}$ $0.14$ ${\ estilo de visualización}$ $0.49$ ${\ estilo de visualización}$ $0.83$ ${\ estilo de visualización}$ $0.17$ ${\ estilo de visualización}$ $0.51$ ${\ estilo de visualización}$ $0.86$ ${\ estilo de visualización}$ $0.2$ ${\ estilo de visualización}$ $0.54$ ${\ estilo de visualización}$ $0.89$ ${\ estilo de visualización}$ $0.23$ ${\ estilo de visualización}$ $0.57$ ${\ estilo de visualización}$ $0.91$ ${\ estilo de visualización}$ $0.26$ ${\ estilo de visualización}$ $0.6$ ${\ estilo de visualización}$ $0.94$ ${\ estilo de visualización}$ $0.29$ ${\ estilo de visualización}$ $0,63$ ${\ estilo de visualización}$ $0.97$ ${\ estilo de visualización}$ $0.31$ ${\ estilo de visualización}$ $0,66$ ${\ estilo de visualización}$ $0.0\}$ ${\ estilo de visualización 5 \ veces 7 = 35}$

Para deshacernos de los números fraccionarios, podemos multiplicar cada elemento de la secuencia resultante por y obtener una secuencia de números enteros: $35$ $(x_{n}^{(int)})_{n\geq 0}=\{0,$ $12,$ $24,$ $una,$ $13,$ $25,$ $2,$ $catorce,$ $26,$ $3,$ $quince,$ $26,$ $cuatro,$ $dieciséis,$ $28,$ $5,$ $17,$ $28,$ ${\ estilo de visualización 6,}$ $Dieciocho,$ $treinta,$ $7,$ $19,$ $31,$ $ocho,$ $veinte,$ $32,$ $9,$ $21,$ $33,$ $diez,$ $22,$ $34,$ $once,$ $22,$ $0\}$

Beneficios de los generadores congruentes inversos

Los generadores congruentes inversos se utilizan con fines prácticos por varias razones.

En primer lugar, los generadores congruentes inversos tienen una uniformidad bastante buena [7] , además, las secuencias resultantes están completamente desprovistas de la estructura reticular característica de los generadores congruentes lineales [1] [8] [9] .

En segundo lugar, las secuencias binarias obtenidas mediante el ICG no presentan desviaciones estadísticas no deseadas. Las secuencias obtenidas por este método han sido verificadas por una serie de pruebas estadísticas y permanecen estables con parámetros cambiantes [7] [8] [10] [11] .

En tercer lugar, los osciladores compuestos tienen las mismas propiedades que los osciladores inversos lineales simples [12] , pero al mismo tiempo tienen un período que supera significativamente el período de los osciladores individuales [13] . Además, el dispositivo de generadores compuestos permite lograr un alto aumento de rendimiento cuando se utiliza en sistemas multiprocesador [14] .

Existe un algoritmo que permite el desarrollo de generadores compuestos con periodos de longitud y complejidad predecibles, así como buenas propiedades estadísticas de las secuencias de salida [15] .

Desventajas de los generadores congruentes inversos

La principal desventaja de los generadores congruentes inversos es la lentitud de generar elementos de la secuencia: el cálculo de un elemento de la secuencia requiere operaciones de multiplicación [16] $O(\log n)$ .

Notas

↑ 1 2 Knut, 2013 , pág. 45.
↑ Eichenauer, Lehn, 1986 .
↑ Hellekalek, 1995 , pág. 255: "Tenemos que elegir el módulo p, un multiplicador a, un término aditivo b".
↑ Amy Glen: Sobre la duración del período de las secuencias numéricas pseudoaleatorias, 2002 , 5.3, p. 67: "Si x2-bx-a es un polinomio primitivo sobre Fp, entonces Xi tiene una longitud de período completa p".
↑ Amy Glen: Sobre la duración del período de las secuencias numéricas pseudoaleatorias, 2002 , 5.4, p. 69: "La secuencia Xi es puramente periódica con una longitud de período d ≤ φ(m)".
↑ Hellekalek, 1995 , pág. 256: "Es elemental ver que el periodo de la sucesión (Xn)n es igual a M := p1*p2*...* pr".
↑ 1 2 Eichenauer-Herrmann, Niederreiter, 1992 .
↑ 1 2 Eichenauer-Herrmann, 1991 .
↑ Eichenauer-Herrmann, Grothe, Niederreiter et al, 1990 , p. 81: "Estos generadores no muestran la estructura reticular simple de los generadores congruenciales lineales ampliamente utilizados".
↑ Eichenauer-Herrmann, 1993 .
↑ Hellekalek, 1995 , pág. 261: "Las excelentes propiedades teóricas y empíricas de los métodos inversivos permanecen estables bajo la variación de los parámetros, siempre que tengamos la máxima duración del período".
↑ Bubicz, Stoklosa, 2006 , pág. 2: "El enfoque compuesto brinda las mismas propiedades sobresalientes de las secuencias producidas que los generadores inversivos simples".
↑ Bubicz, Stoklosa, 2006 , pág. 2: "Los generadores inversores compuestos permiten obtener una duración del período significativamente mayor que la obtenida por un solo ICG".
↑ Bubicz, Stoklosa, 2006 , pág. 2: "Parecen estar diseñados para aplicaciones con plataformas de hardware paralelas multiprocesador".
↑ Bubicz, Stoklosa, 2006 , pág. 2: “Existe una forma constante y sencilla de elección de parámetros, basada en el algoritmo de Chou. Garantiza la máxima longitud".
↑ Anne Gille-Genest: Generadores de números pseudoaleatorios, 2012 , p. 12: "La principal desventaja de estos dos generadores inversos es que el cálculo de un número aleatorio requiere la multiplicación de O(log m ) en F m , por lo que el algoritmo no es rápido".

Literatura

Libros

Knut D. E. El arte de la programación : Volumen 2. Algoritmos obtenidos - 3 - M .: Williams , 2013. - 828 p. — ISBN 978-5-8459-0081-4

Artículos

Eichenauer J. , Lehn J. Un generador de números pseudoaleatorios congruentes no lineales (inglés) // Statistische Hefte - Springer Berlin Heidelberg , Springer Science + Business Media , 1986. - vol. 27, edición. 1.- Pág. 315-326. — ISSN 0932-5026 ; 1613-9798 - doi:10.1007/BF02932576
Eichenauer-Herrmann J. , Grothe H. , Niederreiter H. , Topuzoǧlu A. Sobre la estructura reticular de un generador no lineal con módulo 2ᵅ (inglés) // J. Comput. aplicación Matemáticas. - Elsevier BV , 1990. - Vol. 31, edición. 1.- Pág. 81-85. — ISSN 0377-0427 ; 1879-1778 - doi:10.1016/0377-0427(90)90338-Z
Eichenauer-Herrmann J. Los números pseudoaleatorios congruentes inversos evitan los planos // Matemáticas . compensación -AMS , 1991. -Vol . 56, edición. 193. - Pág. 297-301. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2008543
Eichenauer-Herrmann J. , Niederreiter H. Límites inferiores para la discrepancia de números pseudoaleatorios congruentes inversos con módulo de potencia de dos // Matemáticas . compensación -AMS , 1992. -Vol . 58, edición. 198. - Pág. 775-779. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2153216
Eichenauer-Herrmann J. Independencia estadística de una nueva clase de números pseudoaleatorios congruentes inversivos // Matemáticas . compensación -AMS , 1993. -Vol . 60. - Pág. 375-384. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1993-1159168-9
Chou W. S. Sobre polinomios de período máximo inverso sobre campos finitos (inglés) // Appl. Álgebr. Ing. Com. - Springer Science + Business Media , 1995. - vol. 6, edición. 4.- Pág. 245-250. — ISSN 0938-1279 ; 1432-0622 - doi:10.1007/BF01235718
Hellekalek P. Generadores de números pseudoaleatorios inversivos: conceptos, resultados y enlaces (inglés) // WSC'95 : Actas, Conferencia de simulación de invierno de 1995 / D. Goldsman , C. Alexopoulos - Washington : IEEE Computer Society , 1995. - P. 255 - 262. — 1463 pág. - ISBN 978-0-7803-3018-4 - doi:10.1145/224401.224612
Bubicz J. , Stoklosa J. Algoritmo de diseño de generador congruencial inversor compuesto (inglés) // IMCSIT 2006 : Actas de la 4.ª conferencia internacional sobre informática y tecnología de la información - Amman : ASPU , 2006. - vol. 1.- Pág. 1-6.
Gille Genest Anne. Generadores de números pseudoaleatorios . — 2012. (enlace inaccesible)
Glen Amy. Sobre la duración del período de secuencias numéricas pseudoaleatorias // La Universidad de Adelaide: honores en matemáticas puras. — 2002.