10 de septiembre de 2011

Alea jacta est

Encontrar una fórmula (léase algoritmo) para generar números aleatorios que son, por definición, impredecibles, es por tanto imposible.
No obstante, desde los principios de la computación se han creado algoritmos que generan números pseudoaleatorios, esto es, estadísticamente son muy próximas a una verdadera secuencia de números realmente aleatorios, y tienen además otra particularidad: las secuencias de números pseudoaleatorios son finitas. Después de haber generado el último número, se repiten.
Por ejemplo, John Von Neumann ideó en 1.946 el algoritmo de los medios cuadrados: se escoge un número de 10 cifras inicial (semilla), se eleva al cuadrado, y se escogen las 10 cifras de la mitad del resultado (si este tiene menos de 20 cifras, se rellenan con ceros), y se vuelve a repetir el proceso. Para un número de n cifras, la secuencia más larga que se puede obtener es de 8n números. Diferentes semillas dan como resultado diferentes secuencias de números (de diferentes longitudes).
Ejemplo con 4 cifras y semilla igual a 540: 0540→00291600→08503056→25300900→09054081

La ventaja de los generadores de números pseudoaleatorios es que las secuencias que generan normalmente son suficientes para la mayoría de aplicaciones y son fáciles de implementar (el registro de desplazamiento lineal con realimentación lo hice yo en un PIC en 2º de carrera, generaba una secuencia pseudoaleatoria de 256 bits) en software.
El algoritmo Mersenne Twister (de 1.997) por ejemplo puede generar 219.937-1 (algo más de 4,3·106.001) iteraciones antes de repetirse.

Ahora bien, para generar números realmente aleatorios tenemos que usar hardware, no software, para poder aprovechar el caos que forma parte del Universo. Usando mecánica cuántica:
  • el ruido de disparo cuántico en un circuito electrónico; por ejemplo, una fuente de luz y un fotodiodo. Debido al principio de incertidumbre, los fotones crean ruido electrónico. El ruido se pasa a través de un conversor analógico-digital y se obtiene un número aleatorio.
  • una fuente de radiación y un contador Geiger conectado a un PC.
  • fotones atravesando un espejo semirreflectante. Los 2 eventos mutuamente exclusivos (reflexión y transmisión) se convierten en 0 y 1.
Sin usar efectos cuánticos:
  • el ruido térmico provoca variaciones en la conductividad de una resistencia, y por lo tanto, el voltaje que pasa por ella.  El voltaje se convierte en un número mediante un conversor analógico-digital. Bajando la temperatura del sistema, el ruido va reduciendo su amplitud, por lo que dichos sistemas suelen dejar de funcionar a unos -120°C.
  • ruido atmosférico, captado a través de una antena conectada a un PC.
  • ruido electromagnético generado por un diodo avalancha conectado en inverso.
Normalmente el ruido obtenido con un generador hardware de números aleatorios se combina con otro generador (hardware o software) para eliminar posibles desviaciones o repeticiones (debidas por ejemplo a los 50Hz de la red eléctrica o a una emisora de radio o TV cercana).

 Los fractales parecen caóticos, pero no lo son. De hecho se repiten. Eso hablo en otro post.

7 comentarios:

Jota___ dijo...

Olé! Olé!!!

Joder, que clarito me ha quedado!
Ahora miro hacia atrás en el tiempo, y me parece increíble lo desconocedor de verdades que he sido.

Comoen la alegoría de la cueva de Platón, gracias por mostrarme la luz, Pat.

Mutten dijo...

Uf! creo que esta noche estoy espeso...

Iván dijo...

Pero qué simple, joder! Cómo no habíamos caído antes Josh?? Ruido cuántico... me siento gilipollas. Todo el día viendo fotones pasar y haciendo ruído, y no caer! Y no te cuento con las variaciones atmosféricas... hoy nazco y muero suicidado ;)
Gracias Pat!!

Jota___ dijo...

FELIZ CUMPLEAÑOS, CARCAMAL!!!

Iván dijo...

Cómo mola la "Pedrada aleatoria"

breadbimbo dijo...

Pedrada aleatoria es cuando en un tumulto tiras hacia atrás una piedra.
Por lo menos en la física Newtoniana. Se diferencia de la física cuántica en que tiene como resultado una lluvia de hostias.

Muy buen post Pat!

breadbimbo dijo...

"Post Pat"... cosas que un andaluz y un murciano pueden escribir pero no pronunciar.