[C con Clase] rand, srand

[Steven Davidson]

Hola Rosendo,

El pasado 2007-07-10 12:45:02, rosendo escribió:

r> GRACIAS STEVEN, pero lo concreto es eso crear mi propio algoritmo pseudo codigo.-
r>   ¿podrian darme una idea de como hacerlo?
r>    

Esto realmente es una pregunta acerca de la teoría de los números. El algoritmo más simple y popular es el propuesto por Lehmer, que viene a ser el siguiente:

Lehmer_rand()
1.  generado <- (mult*generado + delta) mod m
2.  Terminar( generado )

Lehmer_srand( semilla )
1.  generado <- semilla

Aquí la variable 'generado' es global para ser compartida por ambas funciones, ya que ambas necesitan modificar su valor. Las otras variables realmente son constantes y signfican:

'm'       es el divisor,                    m > 0
'mult'    es el multiplicador,              0 <   mult   < m
'delta'   es el incremento,                 0 <=  delta  < m

'semilla' es el valor inicial o "semilla",  0 <= semilla < m
Este valor sí es una variable, ya que sirve para iniciar un secuencia u otra del generador de números pseudo-aleatorios.

Obtendremos números enteros, comprendidos en el intervalo [0,m).

Dependiendo de los valores que escojamos para las constantes y el valor semilla, podemos tener un buen generador o uno poco aleatorio. Por ejemplo,

generado <- (generado+1) mod 32,  mult=delta=1

Esto obviamente no es un buen generador, ya que es demasiado lineal. Una posible secuencia con el valor semilla 28 sería: 29, 30, 31, 0, 1, ...

Otro ejemplo de un generador bastante pobre es el siguiente:

generado <- (7*generado) mod 32,  mult=7, delta=0

También tenemos problemas. Una posible secuencia con el valor semilla 1 sería: 7, 17, 23, 1, 7, ...  Como puedes ver obtenemos 4 números y volvemos a repetir, de todos los 32 posibles valores que tenemos.

En general, es mejor usar un valor primo y bastante elevado para 'm'. Si usamos números enteros de 32 bits, podemos usar el valor primo 2^31-1 = 2147483647. Como una propuesta establecida, elegimos delta=0. Con esto sólo tenemos que preocuparnos por el valor de 'mult', que aunque puede escoger de entre muchos valores, sólo unos cuantos realmente nos sirven. Puedes elegir mult=16087. Al final, obtendremos la fórmula,

generado <- (16087*generado) mod 2147483647


Como los generadores de números pseudo-aleatorios son usados en algoritmos criptográficos, existen otros algoritmos más "seguros". Un generador también sencillo y popular es BBS (Blum-Blum-Shub). Sin embargo, este generador es a nivel de bit. Esto significa que obtendremos bits, que supongo que podemos crear una secuencia de 32 para resultar en un número entero de 32 bits. Su algoritmo es el siguiente:

BBS_rand()
1.  generado <- (generado*generado) mod n
2.  bit <- generado mod 2
2.  Terminar( bit )

BBS_srand( semilla )
1.  generado <- semilla

BBS requiere algo más de planificación que el algoritmo de Lehmer. Empezamos por elegir dos números enteros primos los cuales cada uno están a una diferencia de un múltiplo de 4. Dicho de otro modo, si dividiéramos cualesquiera de estos dos números por 4, obtendremos 3 como su resto. Por ejemplo,

p = 7,    7 mod 4 = 3
q = 11,  11 mod 4 = 3

Luego, definimos 'n' como el producto de estos dos números primos; o sea,
n = p*q

Siguiendo nuestro ejemplo, obtenemos que,

n = 7 * 11 = 77

Ahora elegimos un valor para 'semilla', el cual no tiene ningún factor de 'p' ni de 'q'. A esto decimos que 's' es "relativamente primo" a 'n'. Por ejemplo,

s = 103

Con esto, nuestro algoritmo, viene a ser el siguiente:

generado <- (103*103) mod 77
generado <- 26

generado <- (generado*generado) mod 77
bit <- generado mod 2

Algunas secuencias de bits serían,

 0,    0,    0,    1,    1,   ...
(26), (60), (58), (53), (37), ...

Nuevamente, la recomendación es la misma: elige valores muy elevados para obtener secuencias "más aleatorias". Si analizamos un poco el algoritmo, vemos que tendremos problemas si en la secuencia generamos 0 ó 1, ya que el cuadrado de estos valores es el mismo: 0*0 = 0 y 1*1 = 1. Esto significa que nos quedamos "atrapados" en la iteración con una secuencia nada aleatoria. Podríamos rectificar esto modificando el valor generado que básicamente implicaría "replantar la semilla".


Existen algunos otros algoritmos, como por ejemplo el de Park y Miller. Te dejo algunos enlaces que encontré: http://www.firstpr.com.au/dsp/rand31/  http://c-faq.com/lib/rand.html


Espero que esto te sirva.

Steven