3.4.3 Método de Knuth

Sin duda alguna el método más frecuentemente usado en la actualidad lo propuso Donald Knuth. Su generador es un caso particular del generador congruencial lineal tal vez el más simple y sencillo de todos pero a la vez uno de los mejores que se conocen hasta la fecha.

3.4.3.1 Definición

El generador de Knuth se obtiene del congruencial lineal cuando , , , la semilla y por lo tanto , para . En este caso los parámetros , y son constantes no negativas.

Notas:

1. La semilla debe ser un número entero definida en el conjunto , sin embargo, normalmente los algoritmos que implementan el método de Knuth no imponen restricción y, simplemente, filtran ese dato mediante la expresión y es este resultado el que se emplea como semilla.
2. Frecuentemente cuando el generador se denomina multiplicativo . Es un tipo de generador que se emplea mucho por su facilidad de implementación.
3. Nuevamente, no para todos los parámetros el generador será bueno por ello algo de teoría debe emplearse para llegar a buenos resultados. Principalmente la secuencia debería ser de periodo completo es decir que el periodo del generador debería ser , la secuencia debería parecer aleatoria.

 

Ejemplo 3 — 2 : Generador congruencial evidentemente malo.

Al considerar los números generados por este método con los parámetros , , y se obtiene los resultados que se muestran en la Tabla 3 - 1.

Es claro que es un pésimo generador pues es degenerado y su periodo no es el máximo; más aún las secuencias (obviamente) no parecen aleatorias.

Ejemplo 3 — 3: Generador congruencial aparentemente bueno

En la Tabla 3 - 2 se presenta un generador congruencial con , , y . Al observar con algún detalle es claro que no es degenerado, presenta un periodo completo y la secuencia es (por lo menos en apariencia) aleatoria.

Claramente, la calidad del generador depende de los parámetros que se seleccionen. Efectivamente Knuth y otros investigadores en el área han demostrado que la selección de los parámetros para un buen generador debe cumplir algunas condiciones mínimas. A continuación se exponen ciertas condiciones deseables en cada uno de esos parámetros.

Dado que existe un número finito de residuos en este generador, la secuencia eventualmente se repetirá. Es decir, existirán dos enteros y , de forma que para los cuales y, en consecuencia para todo entero positivo . De esta manera si es el entero positivo más pequeño para el cual , entonces el generador producirá un conjunto de número iniciales seguido de un segundo conjunto el cual se repetirá indefinidamente.

Al entero se le denomina periodo del generador . Así mismo se dice que el generador es de periodo máximo siempre que .

3.4.3.2 Criterios para la selección de la semilla

La semilla o condición de frontera debe ser un entero definido en el conjunto que puede ser seleccionada arbitrariamente . Esto significa que la calidad del método no depende para nada de la condición de frontera, por esa razón es frecuente que el usuario suministre ese dato o que se emplee un método (no necesariamente aleatorio) para suministrar este número.

En la práctica, sin embargo, es frecuente que los algoritmos (ver sección 1.4.3.4 ) realicen una transformación empleando la función de valor absoluto y la función módulo para garantizar que cumpla con estas condiciones, es decir que si el número suministrado al algoritmo es entonces .

3.4.3.3 Criterios para la selección del módulo y el factor

El número debe ser grande , tomado de tal manera que sea del orden de la longitud de palabra del computador. Es decir debería poder escribirse de la forma o algún número que cercano a él como , donde es el número de bits empleado para el tipo de entero que se defina para , con lo cual se asegura que el módulo va a ser tan grande como sea posible. Por ejemplo si el lenguaje de programación emplea 4 Bytes para almacenar un entero entonces ó . A continuación se enuncian, sin demostración, algunos resultados importantes que sirven para seleccionar apropiadamente el parámetro . Se deja, sin embargo, la inquietud al lector para que consulte la bibliografía incluida cuando desee ampliar su conocimiento y demostración de esos resultados.

Teorema 3 - 1

Si el factor y el módulo son primos relativos, es decir que el , existe un entero para el cual .

Teorema 3 - 2

Si , entonces el periodo del generador es el entero positivo más pequeño para el cual donde .

Teorema 3 - 3

Si el entonces el periodo de la secuencia es si y únicamente si para cada número primo que divide a se tiene que

1. para cada primo impar .
2. Si 4 divide a , entonces .
3. El .

Con base en estos enunciados y otros de menor importancia, es posible concluir, además, que:

1. Es recomendable que cumpla la restricción de que y, en la mediad de lo posible que .
2. El parámetro c debe ser un número impar no múltiplo de 5.

3.4.3.4 Algoritmo

Una primera aproximación a la implementación de esta técnica puede observarse en el pseudo código que sigue:

Algoritmo 3 - 1 : Esquema general del método Congruencial

En el algoritmo se recibe como parámetro la semilla que debe ser un número entero. Para garantizar que se encuentre en el rango apropiado se pasa a través de la función valor absoluto para suprimirle un posible signo negativo y luego a través de la función módulo.

 

En la siguiente instrucción existe un llamada a la función . Esta función construye una lista dinámica (posiblemente) bidimensional en la que en la primera columna se almacenarán las semillas que el usuario ha empleado hasta el momento y ligada a cada semilla en un sentido horizontal se guardará el que deberá usarse para calcular el siguiente número aleatorios cuando el usuario emplee nuevamente la función de Knuth con esa semilla asociada. Para calcular este valor dentro de esta función se deberá emplear una instrucción como .

De esta manera cada vez que se desee generar un número aleatorio esta función extrae el que se requiere en el cálculo de . Cuando la semilla que el usuario envía no se encuentra en la lista se crea una nueva fila para esa semilla y se retorna el mismo valor de la semilla dado como parámetro a esta función (el valor filtrado) e internamente se calcula el que se empleará la próxima vez que se invoque a esta función con el valor de esa semilla.

 

Ejemplo 3 - 2 : Funcionamiento de la Función Anterior_Z

Suponiendo que se ha diseñado un generador de Knuth con los parámetros, , y . Suponiendo también que la primera vez el usuario invoca a la función entonces ésta llama a su vez a la función quien se da cuenta que hasta ese momento no había sido llamada anteriormente y por lo tanto creará un registro en el cual almacene la semilla 7 y calculará y guardará el valor 4 que corresponde al próximo valor de que deberá usarse cuando el usuario vuelva a llamar la función de Knuth con esta misma semilla (como se muestra en la Tabla 3 en donde se tiene la secuencia para los parámetros dados y la semilla ).

Tabla 3 - 3: Secuencia con una semilla igual a 7

Cuando el usuario ejecuta nuevamente la instrucción , la función busca en la lista y encuentra que esa semilla ya está en uso y, en consecuencia, extraerá el valor de que deberá usarse en el cálculo del aleatorio (en este caso el 4) actualizará la lista, es decir reemplazará el 4 por el 5 y retornará .

Ahora bien, cuando el usuario emplee nuevamente la función entonces encuentra que esa semilla no ha sido utilizada por lo tanto creará un registro en el que la almacena guarda el próximo dato a utilizar, que como se muestra en la Tabla 4 corresponde al valor de 0, y retorna 3.

Con este mismo procedimiento es claro que, si se opera secuencialmente , , , , , etc.

Nota:
Al encontrar unos buenos parámetros se pueden encontrar diferentes secuencias que producirán buenos números aleatorios. Este hecho es importante puesto que en simulación de sistemas complejos varias veces se exige que se empleen distintos generadores (en este caso secuencias independientes).

Con un valor de y apropiados se pueden tener simultáneamente miles de millones de buenos generadores de números aleatorios implementados en un solo algoritmo.