¿Quién ideó el primer generador algorítmico de números aleatorios y cómo funciona?

¿Primero? No lo sé. Pero aparentemente el método del cuadrado medio de von Neumann fue descubierto originalmente por un fraile franciscano alrededor de 1250 . Incluso si hubiera métodos anteriores, ¡estos ya son bastante antiguos! (Wikipedia cita The Broken Dice y Other Mathematical Tales of Chance para este hecho).

No creo que nadie lo use hoy, pero es genial para explicar la idea de los pRNG. En una autopromoción flagrante, voy a decirle que consulte mi respuesta en ¿Cómo hacen las máquinas para “aleatorizar” la información? para una explicación de cómo funciona.

Cada generador algorítmico de números aleatorios (o “generador de números pseudoaleatorios” PRNG) en uso tiene la estructura básica de alternar repetidamente entre dos operaciones: actualizar un estado interno y generar una salida basada en ese estado interno.

El método de “cuadrado medio” de von Neumann mencionado por otras respuestas utiliza el “cuadrado del estado, y toma los 10 dígitos del medio” como la función de actualización, y simplemente devuelve el estado como la función de salida. Desafortunadamente, es fácil encontrar números que conduzcan a ciclos cortos en la salida de este método, por lo que no es un buen método en general.

Una técnica común es un “generador de congruencia lineal”, que, dado un estado s usa la función de actualización (a * s + b)% c, o multiplica el estado por alguna constante a, luego agrega una segunda constante b, luego encuentra el resto de eso por una tercera constante c. Por lo general, la función de salida era el nuevo estado, o el nuevo estado dividido por c para producir un número aleatorio entre 0 y 1. Con una elección cuidadosa de las constantes, el PRNG puede parecer algo aleatorio. Pero esto también tiene problemas: la salida circulará, con el período c, a través de todos los valores posibles de 0 a c en algún orden, sin repeticiones. Además, si toma pares de resultados sucesivos y los traza, aparecerán franjas distintivas en el gráfico resultante.

Otra técnica es un “registro de desplazamiento de retroalimentación lineal” (LFSR). Un registro de desplazamiento es simplemente una matriz de bits (generalmente) que funciona como una cola: cuando se agrega un nuevo valor, todos los demás valores se desplazan hacia abajo una posición y el valor más antiguo cae al final. Entonces, usando un registro de desplazamiento decimal de 10 dígitos, puede tener un estado como 1234567890. Al presionar un 5 en el registro se obtendría el estado 5123456789. Un LFSR simplemente establece que la entrada es una “función lineal” de algunos de los dígitos en el registro, digamos el 2 °, 3 ° y 6 °, generalmente el módulo de adición de la base del registro. Entonces, con un estado inicial de 1234567890, la nueva entrada sería (2 + 3 + 6)% 10 = 11% 10 = 1, por lo que el nuevo estado sería 1123456789, siendo 0 la salida. La siguiente entrada sería (1 + 2 + 5)% 10 = 8, con 9 salidas, dando 8112345678. Luego 6811234567 con 8 salidas, luego 1681123456 con 7 salidas, etc. A diferencia de los métodos anteriores, el tamaño del registro puede ser bastante grande y no todo se emite con cada llamada al PRNG. Las variantes de esta técnica se han utilizado en algunas tecnologías de encriptación militar.

Muchos PRNG modernos utilizan funciones de cifrado hash, tanto para actualizar el estado como para generar una salida del estado. Su objetivo es no solo generar números aleatorios con buenas propiedades estadísticas, sino también hacer que sea lo más difícil posible predecir resultados futuros basados ​​en resultados pasados.

Cualquier algoritmo utilizado para calcular un número irracional le dará una cadena de números aleatorios. ¿Por qué porque un número irracional no puede terminar ni repetirse? Para las computadoras, calcularlas puede requerir un número excesivo de términos y precisión. Sin embargo, recuerdo haber visto PI calculado en una cantidad tan grande de lugares que requería un libro. Se podría colocar en una mesa grande y luego acceder a él a voluntad. La idea de von Neumann es buena porque resuelve el problema de requerir el cálculo de grandes números. Su problema es que si los diez lugares intermedios son todos ceros, obviamente fallará. Uno podría preguntarse, ¿cómo sería justo si los números medios originales fueran grandes o pequeños en valor? ¿Podrían los números medios eventualmente moverse hacia un cierto valor haciendo desaparecer la aleatoriedad?

Este método del cuadrado medio se usa como función hash. También hay otras instrucciones para usar los REGISTROS DE CAMBIO DE COMENTARIOS (puede que no sean algorítmicos) [aunque cualquier hardware tiene una implementación de software equivalente] utilizando los postulados de GOLUMB.