Cada idioma tiene una función aleatoria() o algo similar para generar un número pseudoaleatorio. Me pregunto qué sucede debajo para generar estos números. No estoy programando nada que haga que este conocimiento sea necesario, solo intento satisfacer mi propia curiosidad.¿cómo funciona el azar()?
Todo el primer capítulo del seminal de Donald Knuth trabajo Seminumerical Algorithms se ocupa del tema de la generación de números aleatorios. Realmente no creo que una respuesta SO vaya a estar cerca de describir los problemas involucrados. Leer el libro.
¿Ha actualizado el libro en las últimas décadas? Es probable que ya no sea la mejor fuente. –
Y su alternativa es ... ¿qué? –
No creo que haya cambiado mucho en los fundamentos de los números aleatorios en las últimas décadas, al menos no en la corriente principal. Uno siempre podría buscar trabajos de investigación teórica sobre generación aleatoria, pero recomendaría Knuth como un trampolín de todos modos. – Kena
El Wikipedia page es una buena referencia.
El algoritmo real utilizado dependerá del idioma y la implementación del idioma.
Para responder exactamente a su respuesta, la función aleatoria es proporcionada por el sistema operativo (generalmente).
Pero la forma en que el sistema operativo crea estos números aleatorios es un área especializada en ciencias de la computación. Ver, por ejemplo, la página wiki publicada en las respuestas anteriores.
No, la función aleatoria siempre es proporcionada por el sistema de idioma. Puede usar el sistema operativo para obtener algo de entropía, pero la función C rand() (por lo general) no lo hace. –
Tengo que estar de acuerdo con Neil, muchos sistemas operativos proporcionan API de números aleatorios y pseudoaleatorios, pero muchas bibliotecas estándar demostraron la implementación * por separado *. En cualquier caso, hasta que haya leído los documentos, debe suponer que todos son trabajos congruentes lineales que no son seguros para la ciencia, el secreto o cualquier cosa que involucre dinero. Los documentos confirmarán esto sobre algunos, luego se verificará cualquier reclamo hecho por los demás. – dmckee
random() es un generador de números pseudoaleatorio (PRNG). random() se implementa principalmente como un generador congruente lineal. Esta es una función de la forma X (n + 1) (aXn + c) módulo m. Xn es la secuencia de números pseudoaleatorios generados. La secuencia genarada de números es fácil de adivinar. Este algoritmo no puede usarse como PRNG criptográficamente seguro.
Wikipedia:Linear congruential generator
Y echar un vistazo a las pruebas acérrimos de PRNG PRNG Diehard Tests
Olvidó mencionar que los números aleatorios producidos por un LCG están en algún lugar entre mediocre y horrible. – starblue
Sí, tienes razón, pero para una generación de números aleatorios rápida y sucia está bien. ¿Conoces las pruebas estadísticas DIEHARD sobre PRNG? La mayoría de PRNG falla de alguna manera en estas pruebas. –
TestU01 de L'Ecuyer es también un buen marco de prueba en la actualidad. El único inconveniente es que está diseñado para encontrar fallas en casi todos los generadores :-) – Joey
Resulta ser sorprendentemente fácil de conseguir números pseudoaleatorios a mitad de camino-decente. Durante décadas, el estándar de oro era un algoritmo muy simple: mantener el estado x, se multiplica por constantes A (32x32 => 64 bits) a continuación, añadir constante B, a continuación, devolver los bajos de 32-bits, que también convertirse en el nuevo x. Si A y B se eligen cuidadosamente, esto realmente funciona bastante bien.
Los números pseudoaleatorios deben ser repetibles, también, para reproducir el comportamiento durante la depuración. Entonces, sembrar el generador (inicializando x con, por ejemplo, la hora del día) normalmente se evita durante la depuración.
En los últimos años, y con más ciclos de cálculo disponibles para quemar, los algoritmos más sofisticados están disponibles, algunos de ellos inventados desde la publicación de las demás bastante authoritive Seminumerical Algoritmos. Los sistemas operativos también están empezando a proporcionar hardware y bits de entropía derivados de la red para fines criptográficos especializados.
(a) un LCG * no * produce números pseudoaleatorios medianamente decentes, en realidad los resultados son bastante horribles a desastrosos, dependiendo de cómo elija el factor, sumand y módulo.(b) Mejores generadores no siempre significa que son más lentos. Por ejemplo, MT19937 es un excelente generador (aunque ahora reemplazado) que se ejecuta más rápido que la mayoría de las implementaciones LCG. (c) Si bien puede ayudar en la depuración cuando un PRNG produce salida repetible, es absolutamente obligatorio en las simulaciones. – Joey
Vuelva a leer la pregunta. Él no estaba pidiendo el mejor algoritmo, la pregunta era: ¿cómo funcionan? Sí, el twister Mersenne es un mejor algoritmo. Es lo que usa Ruby, y si la pregunta era "qué es lo mejor", podríamos haberlo discutido. Es interesante observar que algunas implementaciones de MT utilizan un LCRNG para la inicialización. – DigitalRoss
Claro, la pregunta pregunta cómo se hace, pero está diciendo que es fácil obtener números aleatorios decentes con un LCG, lo cual es simplemente incorrecto. En cuanto a la inicialización de MT, si se hace correctamente, esto es suficiente. Lo que importa es (a) que si usa múltiples RNG, sus * seeds * no tienen dependencias lineales y (b) sus generadores no introducen uno. MT19937 se ha concebido de forma que el método de inicialización recomendado no afecte a la calidad de la salida. – Joey
Una cosa que quizás desee examinar es la familia de dispositivos aleatorios disponibles en algunos sistemas operativos tipo Unix como Linux y Mac OSX. Por ejemplo, en Linux, el kernel reúne entropía de una variedad de fuentes en un grupo que luego usa para generar su generador de números pseudoaleatorio. La entropía puede provenir de una variedad de fuentes, la más notable es la inestabilidad del controlador del dispositivo por pulsaciones de teclas, eventos de red, actividad del disco duro y (sobre todo) movimientos del mouse. Aparte de esto, hay otras técnicas para reunir entropía, algunas de ellas incluso implementadas totalmente en hardware.Hay dos dispositivos de caracteres se puede obtener bytes aleatorios desde y en Linux, se comportan de la siguiente manera:
Tenga en cuenta que mientras que Mac OS X utiliza un método diferente para él es PRNG y por lo tanto no bloquea, mis puntos de referencia personales (hecho en la universidad) han demostrado que es cada tan ligeramente menos aleatorio que el núcleo de Linux. Ciertamente lo suficientemente bueno, sin embargo.
Entonces, en mis proyectos, cuando necesito aleatoriedad, generalmente voy a leer desde uno de los dispositivos aleatorios, al menos para la semilla de un algoritmo en mi programa.
'/ dev/urandom' todavía es un PRNG criptográficamente seguro. Esos están diseñados para que el estado del generador no pueda adivinarse fácilmente (a diferencia de los RNG reales que existen porque su estado no puede adivinarse). En cualquier caso, incluso para la gran mayoría de las aplicaciones que necesitan seguridad, '/ dev/urandom' es una buena opción. Definitivamente se divertirá cuando intente usar '/ dev/random' (y luego espere a que su aplicación termine), especialmente con múltiples procesos o usuarios en el mismo sistema :-) – Joey
Después de leer el artículo de wikipedia, ¿qué preguntas específicas tenía? http://en.wikipedia.org/wiki/Random_number_generation –
Algunos generadores de números aleatorios leen el caché de Internet Explorer y la carpeta temporal central de Windows en su perfil de usuario. Al leer 1KB de datos de cada archivo que encuentra, se crea un número notablemente aleatorio. –
+1 para una pregunta bien formada. -2 por ninguna investigación aparente de ningún tipo. –