• Author / Uploaded
• Braiyan Alex-ander Hurtado

Citation preview

Fundaci´on Universitaria Los Libertadores Generadores de n´umeros Aleatorios (Clasicos-Actuales) Yuly Vanessa Rincon S. [email protected]

Braiyan Alexander Hurtado B. [email protected]

Abril 9 2019 Resumen Lo que se quiere conseguir con esta practica es implementar los diferentes metodos para generar n´ umeros aleatorios tanto los clasicos como el congruencial y actuales como el xorshift y el retraso de Fibonacci utilizando el lenguaje de programaci´on Python y comparando algunos con sus librerias.

P¨ alabras clave : Aleatoriedad, Distribuci´on, xn = (axn−1 + k)modM (1) pero estos metoPeriodicidad, Uniformidad dos hoy en dia son facilmente predec´ıbles usando algebra de matrices y un poco de matem´atica discreta como se ilustra mas adelante, por este 1. Objetivos motivo se han ideado nuevas maneras para generar n´ umeros aleatorios que no son tan faciles 1.1. General de predecir en este documento se mostrar´an al1) Leer y analizar el material de Bb. sobre gunos. n´ umeros aleatorios e implementarlos experimentalmente en el lenguaje de programaci´on Python.

1.2.

3.

Marco Te´ orico

Para lograr un buen dise˜ no de alguna aplicaci´on que tenga que ver con procesos aleatorios es necesario simular datos al azar, necesitamos que un computador genere una secuencia aleatoria, pero este no puede generar por si solo una secuencia de esta manera, por ello se empieza a generar metodos para simular que son aleatorios (en realidad pseudoaleatorios)

Especificos

1) Leer y entender el material te´orico sobre n´ umeros aleatorios. 2) Implementar en python metodos clasicos y actuales para la generaci´on de n´ umeros aleatorios. 3) Realizar almenos pruebas minimas para garantizar unos buenos dise˜ nos de los generadores. 4) Implementar un codigo para Crakear los n´ umeros generados por un RNG Congruencial de re3.1. RNG CONGRUENCIAL currencia com´ un para predecir la secuencia. Por sus siglas en ingles Random − number − Generator es un generador que se basa en me2. Introducci´ on todos congruentes, genera secuencias de la for2 3 2 Existen metodos clasicos para generar n´ ume- ma f (x), f (x), f (x), ..... donde f (x) es f (f (x) ros aleatorios usando diferentes recurrencias, el y asi..., su recurrencia mas b´asica es : xn = congruential RNG m´as comun usa la recurrencia (axn−1 + k)modM eventualmente por introducir la operaci´on modulo se repetir´a despues de cierto ciclo para garantizar un periodo largo (Maximo 1

M) se debe escoger con cuidado los valores de a, k, M que son n´ umeros enteros positivos, acontinuaci´on unos criterios para escogerlos: M = n´ umero primo mas grande que no se pase de por ejemplo 232 , 264 a = n´ umero primo no mas grande que M K = cualquier n´ umero impar Habiendo escogido con cuidado estos parametros solo se necesita una semilla (x0 ) aleatoria para empezar la secuencia, si la semilla es aleatoria y con distribuci´on uniforme entonces la secuencia tendr´a distribuci´on uniforme como indica el autor : ’If f is one-one function over Z then for any random seed x0 chosen uniformly of Z the random variable f (x) is also uniformly distributed over Z’ [1][2].

3.2.

unas tablas con buenos candidatos para escoger y dise˜ nar generadores Lagged-Fibonacci y XorShif.

4.

En esta secci´on se hara un breve analisis (importante) de los generadores y se dise˜ nara los tres tipos de RNGs ya estudiados. Todo el codigo esta en el archivo randomLAB.py y aparte un archivo crakingCongruential.py que se explicar´a mas adelante, en el primer archivo al ejecutarse el programa este empieza con la funci´on menu. DEF MENU : Este desprende las opciones para escoger este esta dentro de un ciclo While para que no termine hasta que la variable auxiliar tenga estado logico False (ocurre solo cuando se presiona la letra ’g’), acontinuaci´on el objetivo de esta funci´on es capturar un dato y almacenarlo en una variable posteriormente llamar una funci´on semilla, una funci´on captura e invoca una clase y se repite hasta que la variable auxiliar se False.

XORSHIFT

Este tipo de generador se basa en una secuencia de la siguiente manera βT, βT 2 , βT 2 , βT 3 , ... donde β es la semilla pero esta vez no es un entero, es un vector binario de tama˜ no 1xn que debe cumplir las mismas condiciones que la semilla de RNG Congruential, y T se puede expresar como una matriz binaria nxn no singular que nos generar´a en la semilla varios cambios de posici´on en binario, normalmente es : T = (I + La )(I + Rb )(I + Lc ), aqu´ı I es la matriz identidad, L es la matriz que genera un cambio a la izquierda de una posici´on, el exponente indica que el cambio no es de 1 sino de a y R es la transpuesta de L que genera un cambio a la derecha de uno, pero la secuencia tambien la podemos expresar de la siguiente manera : (I + La )∗ = y s se escogio la operaci´on multiplicaci´on ∗ ya que esta en comparaci´on con la operaci´on Xor y +,- tiene un periodo muacho mas largos (para m´as sobre periodicidad visite : [1],[2][3],[4]), para generar secuencia menores a 20 n´ umeros r y s son : 5 y 1 respectivamente y para mayores a 20 son : 17 y 5 respectivamente por cosas de conveniencia y por que estos n´ umeros son aconsejables en tablas ya que generan buenos resultados. Una particularidad de esta clase es que esta es la unica que no recibe mas que la cantidad de n´ umeros que se desean generar y este genera sus propias semillas usando la librer´ıa datetime y time para esperar unos microsegundos, inmediatamente despues de generar cada semilla se llama el metodo ’Secuencia’ que genera los retrasos y al final hace modulo 103 para no genere n´ umeros mas grandes a este y como es n´ umero primo grande genera una buena distribuci´on uniforme.

A[1] ∗ a + k = A[2]modM Ejemplo1 : Se tiene la secuencia producida por un RNG Congruencial [768 54 747 221 321 48 225 669 414 163 260 723 127 119 420 685 809 630]. Determinar el modulo, el incremento y el multiplicador, comprobarlo. Soluci´ on : Siguiendo los pasos del item anterior : 2) Generando parejas [768, 54][54, 747][747, 221][221, 321][321, 48]...

4

3) Generando los determinantes |768

54|

|54

747|

La soluci´on es de la forma : x = x0 +

|747 221|

∀

δ1 = [768 ∗ 747 + 54 ∗ 221 + 747 ∗ 54]

n ∗k d

k = 0, 1, 2, ..., d − 1

x0 es la primera soluci´on o soluci´on unica de la forma : b i x0 = d d

−[542 + 7472 + 768 ∗ 221] δ1 = 104685 haciendo el proceso con varios obtenemos la secuencia de determinantes que es :

−714 ∗ a = 693

mod

mod

n d

997

Se busca el inverso de di y queda despejada x0 Para nuestro caso d = 1 y por lo tanto se puede dividir cualquier n´ umero entre 1. Ahora busca152541, 242271, 176469, 152346] mos el inverso de −714 en Z997 debe ser un n´ ume4) Encontrando el maximo comun divisor de ro p que al multiplicarlo por (−714∗p)mod997 = 1, otra manera seria ir probando con diferenlos primeros dos tes n´ umeros a que al multiplicarse por −714 y haciendo mod997 de como resultado 693, este 104685 207376|997 n´ umero es 87 ya que −714 ∗ 87 = −62118 y esto 105 208| mod997 = 693, para la primera variable a = 87 No existen m´as n´ umeros en los cuales se pueda reemplazamos y despejamos k de (1) o (2). dividir estos dos, haciendo estos con todos los 768 ∗ (87) + k = 54 mod 997 n´ umeros obtenemos la siguiente secuencia [104685, 207376, 133598, 56829,

k = 54 − 66816 mod 997

[997, 997, 997, 997, 997, 997]

k = −66762 mod 997 Deducimos que M = 997 5) Finalmente armamos y solucionamos el sis- Finalmenet −66762 mod 977 = 37 tema de ecuaciones : k = 37 Esto se demuestra facilmente ingresando los n´ umeros de la secuencia y al solucionar la ecuaci´on con estos valores debe dar el siguiente n´ umero. Este 54 ∗ a + k = 747 mod 997 (2) ejercicio es propuesto para que lo solucionen los Ahora a (2) le restamos (1) lectores en el documento ’Random Number Generators, George Marsagli’, como inspiraci´on al −714 ∗ a = 693 mod 997 (3) documento se soluciona el ejercicio como ejemEs importante aclarar que esta es una ecuaci´on plo en este articulo y se deja una secuencia como en congruencias, lo que quiere decir que tendra ejecicio para los lectores : Ejecicio : Se tiene la secuencia : [98, 258, 658, umero entero : soluci´on si db es un n´ 661, 170, 438, 111, 789, 490, 241, 117, 804, 29, i ∗ x = b mod n 584, 476, 206, 528, 336, 853, 650, 641, 120, 313, 297, 257, 157, 904, 279, 212, 543, 872, 199, 12, Donde b = 693 y d = mcd(714, 997), de ser asi 43, 619, 65, 674, 701, 270, 688] Determinar el la ecuaci´on tiene d soluciones. multiplicador, el incremento y el modulo. 768 ∗ a + k = 54

mod

997

(1)

5

5.2.

Dise˜ no

6.1.1.

El codigo al ejecutarse empieza guardando en la variable ’dato’ la lista que le regresa la funcion capura la cual es lal encargada de pedir 10 musetras de los n´ umeros .aleatorios”. se invoca la clase Craking y se pasa como parametro la lista de muestras. CLASS CRAKING: Se inicializa el metodo init el cual llama el metodo determinantes que crea una lista vacia ’y’ se recorre la lista con un ciclo for y en la variable ’s’ se guarda la primera parte de la determinante, en ’f’ se guarda la segunda parte de la determinante, en ’t’ se restan las dos partes y se almacena el valor absoluto (ya que solo las necesitamos para encontrar el mcd) en ’y’. Despues se guarda en la variable ’self.m’ el valor que retorna la funci´on ’modulo’ al cual se le pasa la lista como parametro y esta se encarga de llamar al metodo ’mcd’ el cual encuentra el mcd de dos n´ umeros y el metodo ’modulo’ con un for agrega a la lista ’y’ el mcd, de los primeros dos, de los primeros tres, los primeros cuatro, .... haciendo mcd(a,b,c) = mcd(mcd(a,b),c) finalmente retorna el ultimo valor de la lista para asegurar que si sea el modulo. Ya teniendo el valor de M (modulo) se llama el metodo ’sistema’ el cual se encarga de solucionar el sistema de ecuaciones como se explica en el ejemplo 1. restamos de la ecuacion (1) a (2) mod m y se guardan en las variables ’p’ y ’h’ se encuentra el mcd de ’p’ y ’m’ y se comprueba que el sistema tenga soluci´on con un if h %D==0, de no ser asi apararece un mensaje que dice ’El sistema no tiene soluci´on’, acontinuaci´on se incluye un ciclo while para buscar un numero ’b’ que cumpla la condici´on de que al ser multiplicado por ’p’ y modulo ’m’ de como resultado ’h’ en ese caso el ciclo termina y procede a hacer lo mismo con elvalor de ’k’ finalmente retorna los valores de ’u’,’k’ que son ’a’ y ’k’ respectivamente. Al final el programa muestra estos tres valores.

6.

Una de las propiedades que debe cumplir las secuencias es que el valor esperado sea 0.5, Esta prueba consiste en tres sencillos pasos : 1) Encontrar la media E(x) o valor esperado de la secuencia con la ecuacion 1. PN

E(x) =

i=1

xi

N

(1) 2) Encontrar los limites superior e inferior Limite inferior para la media (lim) : F/2 (2) 12 ∗ N Limite superior para la media (lsm) : lim = E(x) − √

F/2 (3) 12 ∗ N 3) Mirar si la media esta en este rango, de ser asi esto nos garantiza que la media = 0.5 lsm = E(x) + √

6.2.

Prueba de Varianza

Otra propiedad que debe cumplir la secuencia es que tenga varianza = 1/12 esto consiste en tres sencillos pasos : 1) Encontrar la varianza V(x) de la secuencia con la ecuacion 4. PN

E(x) =

i=1

x2i − 2 ∗ xi ∗ E(x) + E(x)2 (4) N −1

2) Encontrar los limites superior e inferior Limite inferior para la varianza (liv) : 2 X/2,n−1 liv = 12 ∗ (N − 1)

Limite superior para la varianza (lsv) : lsv =

2 X1−/2,n−1 12 ∗ (N − 1)

3) Mirar si la varianza esta en este rango, de ser asi esto nos garantiza que la varianza de la secuencia es : 1/12.

Pruebas de Aleatoriedad (ALGO EXTRA)

6.3. 6.1.

Prueba de Medias

Analisis

Prueba de chi-cuadrado

La prueba chi-cuadrada busca determinar si Existen varias pruebas para comprobar que la secuencia se distribuye uniformemente en el intanbuenos son los generadores de numeros alea- tervalo [0,1] para llevar esta prueba acabo es netorios nos centraremos en explicar 3. cesario dividir el intervalo (0,1) en subintervalos 6

√ en donde es recomendable M = N . posteriormente se clasifica cada numero pseudo-aleatorio del conjunto en m intervalos. A la cantidad de n´ umeros que se clasifican en cada intervalo se le denimina frecuencia observada (Oi ) y a la cantidad de n´ umeros que se espera encontrar en cada intervalo se le llama frecuencia esperada (Ei ) te´oricamente, la secuencia es igual a n/m. A partir de los valores de las frecuencia se determina el estadistico mediante la ecuaci´on : X02 =

la media, la varianza y los dos limites para cada uno.

7.

Conclusiones

1)Se logr´o leer y entender los documentos propuestos por el ingeniero subidos en la plataforma de Bb. para el analisis y entendimiento del mismo sobre la generaci´on de n´ umeros aleatorios y sus recurrencias.

m X

Ei − Oi Ei i=1

. 2)Se realizaron los dise˜ nos de los generadores de n´ umeros aleatorios de acuerdo a la teoria exSi el valor del estadistico x20 es menor al de las plicada en el marco teorico y hecha paso a paso tablas de x2,m−1 , entonces no se puede rechazar de tal manera que se tenga un buen entendimienque el conjunto de n´ umeros sigue una distribu- to de la mec´anica para realizar los generadores. ci´on uniforme. En caso contrario, se rechaza que la secuencia sigue una distribuci´on uniforme. 3)Apoyandose del programa MediasVarianza.py se realizan las pruebas para cada uno de los metodos para la generaci´on de n´ umeros aleatorios 6.4. Dise˜ no del programa ramdomLAB1.py, y el resultado es Al poner como restricci´on que el n´ umero de el siguiemte: datos a ingresar para hacer la prueba sea 40 po- Para cada uno se generan 40 n´ umeros aleatorios demos reemplazar F/2 de la ecuaci´on 2 y 3 por y se pasan como entrada al programa para pruela constante 1.96, esto es equivalente ya que al bas de medias y varainza. hacer el paso a paso es mirar en la tabla de dis˜ PROPIO): tribuci´on normal de probabilidad tomando una RNG-CONGRUENTE (DISENO aceptaci´on del 0.95, asi alfa = 1 - 0.95 = 0.05 Secuencia producida por el generador : lo dividimos en 2 y como los datos son 40 - 1 = 674 701 270 688 736 856 159 909 790 991 995 8 39 buscamos en la table 0.025, 39 y nos arroja 33 594 501 767 435 602 521 817 560 416 56 153 el resultado 1.96, pasa lo mismo con los n´ umera- 894 254 648 636 606 531 842 124 323 322 818 64 dores de la ecuaci´on 4 y 5 que los reemplazamos 173 944 379 462 por 58.12 y 23.6543 respectivamente. Teniendo Resultado al pasarlo por el programa de pruebas en cuenta la teoria de como funciona y los pa- : rametros que acabamos de considerar se procede Media : 531.30 a explicar el dise˜ no en codigo, primero garanti- Limite inferior : 531.2105 zamos que se introduzcan exactamente 40 datos Limite superior : 531.3894 si eso se cumple continua el codigo de lo con- Prueba de medias : La media se encuentra entre trario aparece un mensaje y finaliza, de seguir, los limites asi que pasa la prueba de medias comvierte estos elementos en una lista con el co- Varianza : 0.0641 mando list y se lo pasa a la clase, en clase se Limite inferior : 0.05054 procede a calcular la media o valor esperado con Limite superior : 0.12418 el metodo Media que suma todos los valores de Prueba de varianza : La varianza se encuentra la lista y los retorna divididos en el tama˜ no de dentro los limites asi que pasa la prueba de vala lista, despues se llama al metodo limites pa- rianza ra la media el cual usa la ecuacion 2 y 3 para encontrar estos limites y retorna sus dos valores, RNG-CONGRUENTE (RANDOM PYTHON): el programa continua con el metodo Vaianza que Secuencia producida por el generador : calcula la varianza usando la ecuacion 4, por ulti- 524 166 809 847 598 860 716 234 449 434 800 974 mo calcula con el metodo limitas para la varianza 336 554 511 649 337 692 688 310 748 771 116 311 usando las ecuaciones 5 y 6, finalmente muestra 7

155 503 388 266 271 409 20 109 500 234 869 800 589 988 64 870 Resultado al pasarlo por el programa de pruebas : Media : 511.725 Limite inferior : 511.6355 Limite superior : 511.8144 Prueba de medias : La media se encuentra entre los limites asi que pasa la prueba de medias Varianza : 0.0660 Limite inferior : 0.05054 Limite superior : 0.12418 Prueba de varianza : La varianza se encuentra dentro los limites asi que pasa la prueba de varianza

36 5 69 6 77 4 Resultado al pasarlo por el programa de pruebas : Media : 46.775 Limite inferior : 46.6855 Limite superior : 46.8644 Prueba de medias : La media se encuentra entre los limites asi que pasa la prueba de medias Varianza : 0.0760 Limite inferior : 0.05054 Limite superior : 0.12418 Prueba de varianza : La varianza se encuentra dentro los limites asi que pasa la prueba de varianza Finalmente se logro demostrar que los dise˜ nos quedaron bien ya que pasaron estas dos pruebas minimas para aleatoriedad. 4)La secci´on donde se describio el Craking RNG se realiz´o un ejemplo analiticamente donde se encontraron las constantes de modulo, incremento y multiplicador (m,k,a respectivamente) y el resultado al pasar la secuencia 768 54 747 221 321 48 225 669 414 163 260 723 127 119 420 685 809 630 fue a = 87, k = 37, m = 997 usando el programa CrakingCongruential.py se obtuvo los siguientes resultados de la figura 5: En el

˜ PROPIO): SeRNG-XORSHITT (DISENO cuencia producida por el generador : 923 99 75 959 396 959 75 99 923 0 577 587 742 874 132 641 635 874 331 266 136 897 377 358 320 244 92 809 201 6 637 878 339 282 168 961 505 614 832 247 Resultado al pasarlo por el programa de pruebas : Media : 476.75 Limite inferior : 476.6605 Limite superior : 476.8394 Prueba de medias : La media se encuentra entre los limites asi que pasa la prueba de medias Varianza : 0.10214 Limite inferior : 0.05054 Limite superior : 0.12418 Prueba de varianza : La varianza se encuentra dentro los limites asi que pasa la prueba de varianza RNG-XORSHITT (NUMPY PYTHON): Secuencia producida por el generador : 150 119 758 147 80 147 758 119 150 0 210 221 562 20 979 857 613 125 170 260 440 800 499 918 735 369 658 215 350 620 139 198 316 552 3 947 793 485 890 679 Resultado al pasarlo por el programa de pruebas : Media : 426.275 Limite inferior : 426.1855 Limite superior : 426.3644 Prueba de medias : La media se encuentra entre los limites asi que pasa la prueba de medias Varianza : 0.08721 Limite inferior : 0.05054 Limite superior : 0.12418 Prueba de varianza : La varianza se encuentra dentro los limites asi que pasa la prueba de varianza

Figura 5: Resultado experimental del Craking

documento [1] el autor realiza un ejemplo para la secuencia 308 785 930 695 864 237 1006 819 204 777 378 495 376 357 70 747 356 encontr´o a = 69, k = 13, m = 1024 usando el programa CrakingCongruential.py se obtuvo los si˜ PRORNG-LAGGED-FIBONACCI (DISENO guientes resultados de la figura 6: Con estas y PIO): Secuencia producida por el generador : m´as pruebas que quiera hacer el lector demos16 65 68 16 98 41 91 69 6 77 4 65 85 33 43 84 39 tramos la eficiencia del programa CrakingCon48 88 87 14 3 23 2 12 64 84 51 19 18 79 68 16 98 gruential.py para generadores de n´ umeros alea8

Figura 6: Resultado experimental del Craking

torios congruenciales de recurrencia com´ un.

8.

Bibliograf´ıa

[1] Marsaglia, George (2003) Random Number Generators,”Journal of Modern Applied Statistical Methods: Vol. 2 : Iss. 1 , Article 2. Available at: http://digitalcommons.wayne.edu/ [2] Matrices and the Structure of Random Number Sequences George Marsaglia and Liang-Huei Tsay Computer Science Department Washington State University [3] TABLES OF LINEAR CONGRUENTIAL GENERATORS OF DIFFERENT SIZES AND GOOD LATTICE STRUCTURE - PIERRE L’ECUYER MATHEMATICS OF COMPUTATION Volume 68, Number 225, January 1999, Pages 249–260 [4] Xorshift RNGs George Marsaglia The Florida State University ´ [5] LOS NUMEROS ALEATORIOS Y LA INGENIERIA LUIS GERARDO ASTAIZA A. Ingenlero Mecanlco, M.I.S. Profesor Asoclado Unlversldad NaCIONAL [6] UNIFORMIDAD DE ´ LOS NUMEROS ALEARTORIOS

9