jueves, 21 de febrero de 2013

Método Lineal de congruencias de Lehmer


Este es el método más simple para generar números pseudoaleatorios. Consiste en seleccionar 4 números iniciales, que reciben el nombre de semillas. Las semillas se representan con las letras a, c, m, y x y producen un resultado r como se presenta en la siguiente fórmula:
           
            r = (ax + c) mod m

mod es una operación aritmética que consiste en obtener el resto de la división entera. Por ejemplo suponga la siguiente operación:
            3 mod 2 = ?
En este caso dividimos 3 en 2. 2 por 1 es 2, y el resto es 1. Por lo tanto:
            3/2 = 2
            3 mod 2 = 1

El primer cálculo con la fórmula dará un resultado representado con r. Para volver a calcular otro entero pseudoaleatorio, se debe tomar el resultado y utilizarlo como otra de las semillas a, c o x, en ese orden.

Consideremos un ejemplo para comprenderlo mejor. Suponga que elegimos las siguientes semillas:

a: 2      c: 3      x: 5      m: 3

Consideremos el primer resultado, (2*5 + 3) mod 3 que da como resultado 1. Entonces utilizamos 1 como la nueva semilla a.

a: 1      c: 3      x: 5      m: 3

Ahora calculamos el segundo resultado, (1*5 + 3) mod 3 que da como resultado 2. Entonces utilizamos 2 como la nueva semilla c.

a: 1      c: 2      x: 5      m: 3

Ahora calculamos el tercer resultado, (1*5 + 2) mod 3 que da como resultado 1. Entonces utilizamos 1 como la nueva semilla x.

a: 1      c: 2      x: 1      m: 3

Ahora calculamos el cuarto resultado, (1*1 + 2) mod 3 que da como resultado 0. Entonces utilizamos 0 como la nueva semilla a. Si continuamos con este método hasta obtener 20 resultados obtendremos la siguiente cadena de resultados:

1-2-1-0-2-2-2-0-1-2-2-1-1-0-1-1-1-2-0-1

Como puede observar el ciclo comienza a repetirse después de cierto tiempo, pero los números que se generan se encuentran entre el 0 y el 2. Esto demuestra que la semilla m determina el rango en el que se encontrarán los números generados.

Hasta ahora, este método parece muy predecible pero eso es sólo por las semillas que hemos estado utilizando. Sin embargo la simplicidad de este método es muy conveniente a la hora de crear programas, donde las semillas pueden ser enteros muy grandes. Suponga que tiene como semillas a, c, x, y m a 1020393, 1992938, 4004993 y 65535 respectivamente. Con esto puede crear secuencias impredecibles a la simple percepción humana ya que los números generados estarán en el rango 0 a 65535.

Para finalizar le presento un programa de ejemplo en C++ que implementa una función para generar los números pseudoaleatorios.

//Generador de enteros pseudoaleatorios con método de Lehmer 
/** AUTOR: MASTER DREEP **/
#include<iostream>
#include<ctime>
using namespace std;


//--- PRIMERO SE DECLARAN LAS SEMILLAS ---//
unsigned int a = 1020393;
unsigned int c = 1992938;
unsigned int x = 4004993;
unsigned int m = 65535;



//--- DETERMINA LA SEMILLA QUE CAMBIARÁ ---//
int POS_semilla = 0;


unsigned int pseudo_aleatorio(){ 

    // Obtenemos r
    unsigned int r = ((a*x)+c)%m;
    
    //Ahora la establecemos como la semilla
    //que le corresponde según POS_semilla
    switch(POS_semilla){ 
        case 0:
            a = r;
            break;
        case 1:
            c = r;
            break;
        case 2:
            x = r;
            break;
    }


    //Ahora determinamos la próxima posición
    if((POS_semilla+1)>2){
        //Si la próxima posición es mayor que 2
        //debe volver a ser 0
        POS_semilla = 0;
    }


    else{
        //Si la próxima posición no será mayor
        //que 2 debe incrementarse.
        POS_semilla += 1;
    }
    return r;
}


void establecer_semilla(unsigned int nSem){
    a = nSem;
}



//-- PROGRAMA DE PRUEBA DE LAS FUNCIONES --//
int main(){
    cout << "Cuantos enteros generar?: ";
    int n;
    cin >> n;


    //Vamos a establecer la semilla a con la 
    //hora, así cada vez que se ejecute el programa
    //dará valores distintos, ya que la hora siempre
    //cambia...
    establecer_semilla(time(0));


    //Ahora generaremos n enteros
    for(int i=0; i<n; i++){
        cout << "entero " << (i+1) << ": ";
        cout << pseudo_aleatorio() << endl;
    }
}

1 comentario: