Los ordenadores y videoconsolas, basadas en procesadores con un comportamiento 100% matemático y preciso, necesitan a veces generar aleatoriedad. Hoy traigo la historia de una de las mayores pifias que una empresa informática (IBM) haya cometido jamás relacionada con, precisamente, la falta de aleatoriedad.
Comentarios
Me ha encantado la demostración con el video. Tu vas por ahi tan tranquilo viendo nubes de números aleatorios, te cambian el angulo y ZAS en toda la aleatoriedad.
#3 Realmente tendrías que analizar millones de números para distinguir ambas. De hecho, si te pones a escribir números al azar no será una secuencia tan aleatoria como una pseudoaleatoria porque intentarás no repetir, etc y ya estarás condicionando la secuencia
Nine, nine, nine, nine, nine
#1
Nine!
#1,#32
nine!#30 es que la llamada se hizo en tiempo de programación mediante una interfaz física
#31
http://es.wikipedia.org/wiki/Entrop%C3%ADa_de_Shannon
http://es.wikipedia.org/wiki/N%C3%BAmero_aleatorio
#1 #32 #34
NYAN
"Si hay algo que no puede dejarse al azar, es el algoritmo de generación de números aleatorios." (John von Neumann)
Muy interesante. Enhorabuena. Realmente, generar números aleatorios en una maquina determinista tiene su complicación.
De hecho, utilizo la librería de Lecuyer y es una viguería. Lo que dijo von Newmann #8 es muy cierto. El tamaño del periodo en grandes simulaciones se nota mucho.
Como crear el universo en el amstrad cpc:
10 PLOT RND*640, RND*400, RND*2 +1
20 GOTO 10
#4 ¡yo lo tenía! Un 464. Me encantaba el "IF... NEXT".
#4 Gracias por darle uso a mi XCPC en el BSD
Para aleatoriedad buena, la de la radio de mi antiguo coche; le dabas al botón random y te salía siempre la misma secuencia "aleatoria" (14, 44, 62...)
Jo, vaya metida de pata. Y de hecho esto me recuerda a: http://xkcd.com/221/
#23 Dime el concurso, que yo creo que he detectado la secuencia de #15
#24 No creo, no tiene mucho sentido. De hecho creo que el RNG del estándar ANSI C es el lineal que comenta el artículo.
#26 el método getRandomNumber() es sólo un accesor. La especificación no dice que sea un generador aleatorio, sólo que devuelve UN número aleatorio. El generador es el dado y a ese seguro que no le encuentras secuencias!
#28 te enfadas si te digo que tu secuencia pasada por un calculador de entropía canta a no aleatoria?
#29 No veo la llamada a getNumberFromDiceLaunch()... Voy a revisar el código
#29 Que me voy a enfadar , todo lo contrario, pero explicame que es un calculador de entropía y defineme que es aleatorio porque entonces no me he enterado...
flipaba con los numeros aleatorios cuando empezé a programar en basic en el año 1987
a pesar que en el manual ponia que era una secuencia pseudoaleatoria, yo creo que en el Amstrad eran aleatorios reales aprovechando el generador de ruido del chip de sonido. Nunca pude detectar la mínima secuencia repetida
#2 Segun tenia entendido yo, con el basic al inicializar el parametro "randomize usr o urs" generaba un numero a partir de una formula y cogiendo decimales de la hora cuando se ponia en RND, algo así mas o menos, vamos que si coges una milesima o millosenima de segundo y encima le aplicas alguna formula pocas veces se va a repetir ese numero no?, y aun así yo creo que si coges el numero de una millonesima o así de un segundo ya es de cojones aleatorio, vamos que no me explico yo la movida esa de ibm
#2 El Amstrad CPC y todos los BASIC de la época usaba una fórmula similar, aunque con los coeficientes mejor escogidos. De hecho el manual del Spectrum viene la fórmula completa que utilizaba.
#16 Las secuencias tienen que ser reproducibles para poder alimentar algoritmos con los mismos datos si fuera necesario, por eso lo ideal es poder plantarle una semilla una vez y que a partir de ahí siga solo.
#16 Lo del "RANDOMIZE USR [dirección]" del BASIC no tiene mucho que ver con calcular números aleatorios, en realidad.
Ésa era símplemente la forma más habitual de invocar desde BASIC el código máquina que había sido cargado en memoria en una sentencia anterior. Solía aparecer en los pequeños programas cargadores en BASIC que venían justo antes del bloque de datos de los juegos de Spectrum. Si te acuerdas, al cargar un juego siempre venía en dos partes (al menos): una primera parte Program: Nombre, y una segunda parte Bytes: Nombre.
La primera parte era un pequeño programa en BASIC autoejecutable que se encargaba de cargar en memoria el código máquina que venía en la segunda parte. Normalmente con una sentencia del tipo LOAD "" CODE 23456. Donde el número es la dirección de memoria donde se carga.
Una vez cargado, ése código máquina no es autoejecutable. Debía ser invocado con una llamada especial USR 23456. El problema es que USR no era una instrucción, sino una función. Esto es, no podía ejecutarse por sí sola, sino sólo ser llamada pasando algún argumento y devolviendo un valor que debía ser usado por una intrucción propiamente dicha.
Algunos usaban instrucciones como LET a = USR 23456, ó PRINT USR 23456, pero eran instrucciones que tenían consecuencias posiblemente no deseadas. La mayoría usaba RANDOMIZE USR 23456 porque RANDOMIZE es la instrucción que se empleaba para propocionar una semilla (Los números aleatorios en sí se obtenían con RND), lo cual no imprime nada en pantalla, ni malgasta memoria en una variable inútil.
TL;DR: RANDOMIZE USR [dirección] era la forma menos dañina de invocar el código máquina desde un programa BASIC porque USR no se podía ejecutar por sí sola.
#2 ¿y el ruido cómo se generaba? ¿no estaría el generador de ruido usando el generador de números aleatorios?
Lo normal es tomar la fecha, incluyendo milisegundos, como semilla para los números pseudoaleatorios. Más que nada porque a cada milisegundo tienes una nueva e irrepetible. Siguen sin ser aleatorios, pero ni Rain Man detectaría el sesgo...
#2 te vas a reír pero el generador de ruido del chip de sonido usa números pseudoaletorios!
Si encuentras una secuencia repetida en un generador pseudoaletorio preséntate a un concurso que ganas fijo. No es que no la haya, es que no la viste. Si ponía pseudoaletorio es que lo era. No van a poner características peores porque sí en el manual
#22 te reto!
Decidle a una persona que lance una moneda 100 veces y apunte si es cara o cruz.
Decidle a otra persona que haga lo mismo pero sin moneda.
Se puede saber a quién pertenece cada resultado sin ver quién lo hizo.
Me ha gustado mucho el artículo. Gracias por el envío!
Todo el mundo sabe que el mejor generador de números aleatorios que existe es el "Tiempo Restante" al descargar algo con el Explorer...
Fuera de coña, interesante artículo. Matizar simplemente que lo de que los ordenadores son siempre deterministas es una verdad a medias, con la programación multi-hilo tener determinismo puede ser francamente complicado. De hecho, no ser determinista es un problema común en la creación de motores físicos.
Por cierto, para tener números aleatorios de verdad (basados en ruido atmosférico): http://www.random.org/
Recuerdo a mi profesor de física computacional contándonos esta historia como introducción a los métodos de Montecarlo. Según iba avanzando se iba cabreando más y gritando más. Vaya risas nos echamos.
#18 " con métodos de dibujo gráfico del lenguaje que estés usando."
Me refería a eso, no lo voy a pintar con el gedit, no?
Matlab, ... etc etc, eso es lo que preguntaba
La tendencia a agruparse en hiperplanos de dimensión n-1 de los números aleatorios cuando se usan para generar vectores n dimensionales aleatorios (cogiéndolos de n en n) es una "propiedad" de los generadores "linear congruential" (no sé como traducir esto).
Según el numerical recipies (http://apps.nrbook.com/c/index.html, capítulo 7.1),
el número de planos que salen es como mucho m^ donde k es la dimensión de los vectores y m es modulo que se usa en el generador.
Consecuencia: si el generador trabaja internamente con enteros de 64 bits (cosa bastante frecuente) m como mucho tiene que valer 2^64, por lo que si generáis vectores de dimensión 64, todos los puntos estarán agrupados en un hiperplano de dimensión 63.
Así que cuidadín, yo una vez tuve un problema por no tener eso en cuenta, pero esa es otra historia ...
#58 Me contesto a mi mismo: según el artículo los "linear congruential generators" se traducen como "generadores de congruencia lineales".
Otro desastre relacionado http://digitaloffense.net/tools/debian-openssl/
Qué programa han usado para representar los números en una gráfica? Me interesa.
#13 Parece Matlab. Octave (con gnuplot) puede darte resultados similares y es libre ( y gratis
)
#14 Me adelante, pero tu lo explicas mas claro
#13 Tu pregunta es un poco absurda. Simplemente, si quieres dibujar los puntos en un plano (rectángular), generas pares de valores para su coordenada X y su coordenada Y, y los pintas en pantalla con métodos de dibujo gráfico del lenguaje que estés usando.
Si lo quieres en 3D, pues generas X, Y y Z, y con por ejemplo openGL los pintas en pantalla (o te curras tú las funciones de tranformación para girar una matriz en el espacio, y la que convierte los puntos 3D a otra matriz 2D para dibujarla con los anteriores métodos gráficos).
Y si quieres lo fácil, matlab es un lenguaje volcado en las matemáticas que viene con muchas funciones gráficas "programadas" de serie.
Para random bueno la emisión de Redes, igual puede ser un miercoles a las 23:15 en el canal 24h que un domingo a las 7:50 en la 2.
Vaya rayadas que me leo después de currar...
3,6,9,67,1,49,56,33,1,7,635,193,574,2938,3649,917,174,7,1,2,3,4,5,6,7,8,9,0,9,8,7,6,5,7,8,4,3,18,34,3,5,7,3,783 !!
Aaaaaaaah adoro mi cerebro !!
Nunca me habia planteado la dificultad de generar numeros aleatorios por una maquina, no es tan sencillo... ¿que algoritmo utilizará nuestro cerebro?
#46
Éstos comentarios que brindáis son mejor que catequesis. Gracias.
yo recuerdo hace 15 o 20 años que todo la aleatorio daba una risa tremenda
la solucion ideal es un generador de ruído analógico que puede ser algo tan sencillo como una bobina sintonizada o cualquier cosa que capte ruido electromagnetico (un sensor hall,etc) y un transistor amplificador.el valor puede ser un bit (0 si esta por debajo de un umbral y 1 si está por arriba)
Para aleatorio bueno bueno, el random del Windows media o de mi viejo Discman
Otra curiosidad que recordaré en una conversación y en ese mismo momento desecharé, mis amistades no son de esas
"Los números aleatorios son demasiado importante como para dejarlos al azar"
¿Con la seguridad de la PS3 no pasó algo parecido?
Intel tampoco se libró con sus Pentium por allá del noventa y pico con errores en coma flotante y en procesos de gran demanda de cálculos matemáticos se notaba la diferencia, aunque al usuario normal (doméstico) apenas le repercutía.
#51 Si, pero o tienes un brazo robótico o los movimientos ni han tenido exactamente la misma duración, ni el mismo ángulo exacto ni has recorrido la misma distancia.
Vamos, es que ni aunque lo intentes a posta!
En cualquier caso, no me lo estoy inventando yo:
http://lh4.ggpht.com/-rY9k2sAJx0g/TiaQpg5L8jI/AAAAAAAAAtQ/Q94ttsFIzLg/1_thumb32.png
No termino de entender por qué todos los resultados son impares...
#5 La fórmula es Xi+1 = A + B*Xi mod M con A=0, B=65539 = 2^16 + 3 y M 2^31
Sabemos que la semilla ( X0 ) havia de ser impar (por lo que parece si no era así el periodo de repeticion de la sequencia se acortaba enormemente, ( ¿algún matemàtico en la sala? )
Eso nos deja Xi+1= (2^16+3)*Xi mod M, supongamos que estamos generando el primer numero, usando la semilla X0 (recordemos, IMPAR)
(2^16+3)*X0 -> 2^16*X0 +3*X0 -> PAR*IMPAR + IMPAR*IMPAR -> PAR+IMPAR -> IMPAR.
El módulo seria (grosso modo) como restarle un numero par (2^31) , por lo que X1 seria impar, con el mismo razonamiento X2 tambien seria impar, X3 etc etc
#9 Bueno, basta con imaginar el caso extremo de elegir la semilla x0=0. Entonces con el mismo programa todos los xi serán iguales a 0. Con otras semillas tales como M/2, 3M/4, 5M/8... el periodo también se acorta bastante.
Básicamente lo que estás haciendo es simplificar la división, por poner un ejemplo con números pequeños, si tienes 56/128 es que es lo mismo que 7/16. Si eliges una semilla divisible por una potencia grande de 2, reduces bastante el número de restos posibles, y aunque el algoritmo estuviera mejor construido este hecho sería un fallo grave.
#9 Macho, vale que seas de ciencias y es de agradecer que te tomes la molestia en explicar lo de los números impares, pero ese "havia" es muy doloroso...
#42 Ops, pero en mi descargo, es una falta típica en los bilingües catalán-castellano al confundir la grafía de un idioma al otro.
Menos mal que no puse "canviar" que también es muy habitual, o tendrías que arrancarte los ojos y rebañar la cavidades con cucharilla
#5 Porque se trata del resto de la división de un número impar (es impar porque es producto de dos números impares) entre un número par.
xi+1 = 65539 · xi mod M
donde siempre se escoge una semilla x0 impar y donde M = 231.
Así, todos los xi son impares.
Creo que el C lo que hacia era calcular el nanosegundo en el que estabas y dividirlo entre el numero que quieras que se comprenda el aleatorio, asi no se repetia casi nunca, casi.
#24 el problema con eso es que si necesitas sacar numeros aleatorios seguidos, estarán muy fuertemente relacionados.
Por ejemplo, si sacas un numero aleatorio (microsegundo) y sacas otro justo despues, se diferenciarán en una cantidad que será constante (o casi) en cada ejecución. Si el primero te daba 10 y el segundo 12, cuando el primero te de 20 el segundo te dará 22, porque el tiempo que va a pasar desde una orden a otra va a ser prácticamente el mismo.
Por eso es mejor obtener la semilla con este método (coger milisegundos) para que varíe toda la secuencia. Los numeros sucesivos de dos secuencias con semilla diferente no guardan (o no deberían guardar) ninguna relación entre si, con lo que se consigue un resultado "mas aleatorio" :P. O también, pasar los milisegundos que obtienes por una función de entropía muy alta, de forma que la diferencia entre t1 y t2 no pueda relacionarse con la diferencia entre f(t1) y f(t2).
Y para acabar, como anécdota curiosa, algunos generadores de claves SSL te piden que muevas el ratón por la pantalla para "generate some randomness" y utilizan valores obtenidos de tu movimiento, que se supone que siempre será mucho más aleatorio que cualquier numero generado por el ordenador.
#47 discrepo, pedir a un usuario que mueva un ratón, así sin tener ni idea, calculo que repetirá muchísimas veces los mismos patrones. Acabo de hacerme una autoprueba y me sale hacer un:
- línea hacia las 8 en un reloj
- línea hacia las 4
- línea hacia las 12
que calculo que será el movimiento más cómodo para la muñeca siendo diestro y blabalbla (o no)
Es como aquello de pedir que te digan rápidamente una herramienta y un color...
HOYGAN I COMO METO ELINTERNET ENUN CEDE MANDENME UN COREO PERDONEM LAS DISCULPAS
A destacar también la pifia de sony, que a la hora de emplear el algoritmo de encriptación de los videojuegos de ps3, donde debía pasarse como parámetro un número aleatorio, utilizaron un número constante con todos los videojuegos. Esta metedura de pata permitía que al comparar 2 juegos cifrados, era factible "calcular" el videojuego sin cifrar. Esto es lo que permite en gran medida el pirateo de ps3 de hoy en día.