Cómo generar números al azar con ordenadores que no son tan aleatorios

Un millón de dígitos aleatorios es una tabla publicada por la RAND Corporation publicada en 1947 como ayuda para científicos, ingenieros y estadísticos que necesitaban utilizar números aleatorios de comprobada validez.
Un millón de dígitos aleatorios es una tabla publicada por la RAND Corporation publicada en 1947 como ayuda para científicos, ingenieros y estadísticos que necesitaban utilizar números aleatorios de comprobada validez. Travelin' Librarian

Muchos programas de ordenador necesitan números aleatorios para funcionar. Desde videojuegos a sistemas de seguridad y simuladores. Los valores aleatorios se utilizan para el análisis estadístico, el arte o simplemente cuando hay que elegir algo al azar, como en los sorteos. Sin embargo, la aleatoriedad perfecta que atribuimos a objetos como monedas, dados o las bolas de un bombo es algo difícil de alcanzar cuando se trata de generarla con ordenadores.

MÁS INFORMACIÓN

La precisión de los ordenadores y su carácter determinista son la clave del asunto. Un ordenador o un programa siempre dará los mismos resultados de salida ante los mismos datos de entrada. Al menos mientras no se introduzca entremedias algún tipo de factor aleatorio.

Pero es precisamente en los generadores de números aleatorios donde está el problema. En realidad no son "tan aleatorios". Sirva como ejemplo el famoso botón de "reproducción aleatoria" de los iPod y otras aplicaciones musicales, que crea listas de canciones al azar. Incluso Apple tuvo que afinar la forma en que funcionaba porque había gente que se quejaba de que era "poco aleatoria".

Cómo funciona la simulación del azar

Un generador de números aleatorios está limitado por su propia definición. Suelen funcionar así: se toma un valor inicial (llamado semilla), se realizan con él ciertas enrevesadas operaciones matemáticas y de ahí surge el resultado. Si el generador está bien diseñado cada vez que se utilice ofrecerá un nuevo número y la secuencia será aleatoria. O al menos, lo más aleatoria posible. El problema es que cada vez que se comience por la misma semilla la secuencia será idéntica. Como decía el matemático y pionero de la informática Donald Knuth: "los números al azar no deberían generarse mediante un método elegido al azar".

Podría pensarse que los propios números ya generados pueden utilizarse como semilla. De este modo el proceso tiende a volverse más desordenado e impredecible cada vez. ¿O no? Esto tiene un límite: la precisión de cálculo de esos valores. Supongamos que la semilla puede ser cualquier número entre 0 y 65535. Todo funcionará bien hasta que al cabo de 65536 valores alguno haya de repetirse obligatoriamente. Si un generador está bien diseñado e implementado pasará por el mayor número de valores posibles antes de entrar en el ciclo (y esos posibles valores serán muchos). Pero al final, tarde o temprano, acabará repitiéndose.

Una solución de compromiso es utilizar factores externos, por ejemplo los movimientos del ratón del ordenador o las milésimas de segundo que marca el reloj interno cuando se llama a la función aleatoria – factores poco predecibles. Pero no suelen resolver el problema; por ejemplo el reloj del ordenador puede coincidir en sus ciclos con los de los cálculos de la función aleatoria, y los movimientos del ratón están limitados por su precisión. Debido a todo esto estos algoritmos tuvieron humildemente que cambiar de nombre y técnicamente se denominan generadores de números pseudo-aleatorios. No son aleatorios, pero "casi".

Pruebas de aleatoriedad

Serie de fotografías de satélite del colapso de la barrera de hielo Larsen C entre junio y abril de 2002.

ampliar foto

Serie de fotografías de satélite del colapso de la barrera de hielo Larsen C entre junio y abril de 2002. NASA

Para comprobar las secuencias y los generadores pseudo-aleatorios se utilizan diversas pruebas estadísticas. El problema es que matemáticamente no existe la prueba perfecta. Una muy sencilla sería comprobar si al aplicarlos a la secuencia de lanzamientos de un dado simulado aparecen más o menos las mismas veces los valores 1, 2, 3… etcétera. Otras pruebas similares exigen comparar las secuencias de dos o tres valores consecutivos (11, 12, 13…) y comparar sus frecuencias.

Curiosamente hay secuencias que pasan todas estas pruebas sin ser aleatorias. Quizá la más famosa de ellas es el número de Champernowne, que comienza así: 0,1234567891011121314… Es simplemente una larga ristra con todos los números naturales. Todos sus decimales, ya sean tomados de uno en uno, de dos en dos o de tres en tres, aparecen más o menos con la misma frecuencia.

Localización de la barrera Larsen C y de la barrera Wordie y el sistema glaciar Fleming con las posiciones de los frentes de hielo desde 1947 hasta 2016.

ampliar foto

Localización de la barrera Larsen C y de la barrera Wordie y el sistema glaciar Fleming con las posiciones de los frentes de hielo desde 1947 hasta 2016. Chen Zhao/Christopher Watson/Matt Kings

Si bien los generadores pseudoaleatorios superan las pruebas más sencillas muchos de ellos fracasan ante la aleatoriedad necesaria para las aplicaciones de análisis numérico o criptografía. Teniendo en cuenta que los resultados de innumerables estudios científicos dependen de lo primero y la seguridad del dinero que guardamos en los bancos y enviamos por internet de lo segundo, más vale que existan métodos mejores.

Tasa de adelgazamiento de la región del glaciar Fleming entre (a) 2002-2008 y (b) 2008-2015.

ampliar foto

Tasa de adelgazamiento de la región del glaciar Fleming entre (a) 2002-2008 y (b) 2008-2015. Chen Zao/Christopher Watson/Matt Kings

Una forma que encontraron los matemáticos de comprobar con mayor precisión la aleatoriedad de una secuencia es intentando describirla mediante un pequeño programa que pudiera generarla. Una secuencia como "1111…111" repetida mil veces no parece muy aleatoria, porque puede reducirse a la frase "escribir 1 mil veces", algo mucho más corto. En cambio, algo como "10010111100…" donde los 0 y 1 se obtienen lanzando una moneda –curiosamente, igual de probable estadísticamente que la primera secuencia– no podría describirse de forma más breve. Esto se conoce como complejidad de Kolmogorov (o entropía algorítmica) y es clave para cuantificar la aleatoriedad.

Irónicamente esta complejidad de Kolmogorov no puede calcularse, aunque sí que se pueden conocer sus límites, por ejemplo comprimiendo la información: la que no sea aleatoria podrá comprimirse un poco (porque se podrá resumir) mientras que la verdaderamente aleatoria no podrá comprimirse (dado que no habrá repeticiones ni patrones detectables). Esto está íntimamente relacionado con la entropía o "desorden" de la secuencia en cuestión.

Los problemas de no usar correctamente la aleatoriedad pueden ser graves. Tal y como comentaba el experto Sergey Ignatchenko de ITShare.com la versión Debian del Linux fue básicamente insegura entre 2006 y 2008 porque uno de los desarrolladores hizo un cambio en el código de su generador de números aleatorios. Lo mismo sucedió en 2013 con una función del lenguaje Java que limitó su aleatoriedad, permitiendo descubrir claves de carteras de Bitcoin, por ejemplo. En la web de apuestas Planet Poker cometieron en 2000 el error de usar un generador aleatorio pobremente diseñado, que era incapaz de generar todas las mezclas posibles para las barajas, quedando solo un pequeño número que podía estudiarse estadísticamente para obtener ventaja – básicamente era como "poder ver las cartas de los oponentes".

Física al rescate

Lejos quedan libros como Un millón de dígitos aleatorios, una tabla que la RAND Corporation publicó en 1947 para quienes necesitara números al azar de comprobada validez. Desde hace décadas, sitios como Random.org ofrecen en internet números "verdaderamente aleatorios" para todo tipo de propósitos: análisis científicos, juegos, sorteos… Dicen que su calidad es superior a la de los generadores de números pseudoaleatorios porque obtienen los números de procesos puramente físicos, en su caso del "ruido atmosférico". Básicamente se trata de tres radios AM/FM sintonizadas entre emisoras, en la zona donde todo lo que se oye es ruido de fondo. Ese ruido es aleatorio y a partir de él se generan los números que luego se preparan para ofrecerse en diversos formatos.

Además de esta ingeniosa solución que emplea el ruido electrónico hay sistema similares basadas en otros procesos físicos que se consideran impredecibles y son normalmente subatómicos: desintegración radioactiva, ruido térmico o el ruido de disparo (shot) típico de los dispositivos electrónicos y ópticos.

Por otro lado, sitios como Random Sanity Project ofrecen comprobaciones gratuitas de la aleatoriedad de cualquier grupo de números. Algo interesante si se planea utilizar software de este tipo para algo importante o simplemente para comprobar que todo es correcto

Por otro lado, sitios como Random Sanity Project ofrecen comprobaciones gratuitas de la aleatoriedad de cualquier grupo de números. Algo interesante si se planea utilizar software de este tipo para algo importante o simplemente para comprobar que todo es correcto. También permite detectar cómo los seres humanos no somos muy buenos generando secuencias aleatorias. Basta examinar una secuencia simulada por un humano intentando imitar los lanzamientos de una moneda o un dado para darse cuenta rápidamente de cuál es la auténtica: las personas apenas superamos las pruebas más básicas debido a nuestros sesgos mentales.

La aleatoriedad de la física cuántica

El último paso en esta carrera por conseguir la aleatoriedad son los generadores aleatorios que aprovechan las propiedades de las partículas subatómicas y el mundo cuántico para generar secuencias aleatorias.

En 2010 el físico español Antonio Acín formó parte de un equipo que publicó un trabajo en Nature acerca de cómo se podía certificar la aleatoriedad de secuencias numéricas aprovechando el teorema de Bell de la mecánica cuántica. En 2012 dos profesores de la Universidad Nacional Australiana desarrollaron un generador basado en la medición del vacío, del que surgen aleatoriamente partículas virtuales produciendo ruido aleatorio. En 2016 investigadores de la Universidad Politécnica de Cataluña desarrollaron un chip capaz de generar varios gigabits aleatorios por segundo usando las propiedades cuánticas de la luz.

Hoy en día las CPU Ivy Bridge de Intel incluyen este tipo de generadores de números aleatorios basados en procesos físicos; sus velocidades generándolos están en torno a los 3 Gbps. Tampoco es demasiado complicado –ni siquiera caro– comprar tarjetas de ampliación especializadas o dispositivos USB que realizan la misma función: basta elegir el método preferido (diodos, ruido eléctrico, efecto fotoeléctrico) y la velocidad deseada, que comienza alrededor de los 100 Kbps. Su precio: a partir de 10 euros. Nunca conseguir lo más parecido al azar verdadero, algo que no es tarea fácil, fue tan barato ni tan cómodo.

Archivado en: Leer mas

One Tecno

Tech

ARM anuncia nuevas CPUs y GPU en Computex 2017

30 mayo, 2017

En Computex 2017, ARM anunció dos nuevas CPUs y una nueva GPU para actualizar su línea de productos para dispositivos que estarán llegando en 2018. Las dos nuevas CPUs que ARM ha anunciado son el Cortex-A75 y Cortex-A55, que se supone que sustituyen al Cortex-A73 y A53 en los teléfonos inteligentes de hoy. ARM dice […]
La entrada ARM anuncia nuevas CPUs y GPU en Computex 2017 aparece primero en HD Tecnología. … […]

Tech

ASUS X399 ROG Zenith Extreme, una bestia

13 agosto, 2017

AMD está a punto de lanzar su próxima generación de procesadores Ryzen ThreadRipper con 16 Núcleos y 32 hilos, y las empresas están preparando sus placas madres para estas bestias.
ASUS X399 ROG Zenith Extreme

La nueva ASUS X399 ROG Zenith Extreme ha sido fotografiada, con un unboxing completo revelando que la nueva placa madre es una bestia, con el nuevo socket TR4, antenas Wi-Fi, y mucho más. ASUS incluye una tarjeta ethernet PCIe, tarjeta de extensión ASUS DIMM2, una pantalla LCD y cuatro ranuras PCIe reforzadas.
La nueva X399 ROG Zenith Extreme de ASUS es la primera placa madre X399 que viene con formato E-ATX, que es un poco más grande que una placa madre ATX tradicional.
Fuente: Videocardz
La entrada ASUS X399 ROG Zenith Extreme, una bestia aparece primero en HD Tecnología. […]

ONE News

Be the first to comment

Escribe un comentario

Tu dirección de correo no será publicada.


*