¿Cómo funcionan los generadores de números aleatorios?

23

Solo estaba reflexionando sobre la rand()función php , y pensando en cómo podría rehacerla, y salí completamente estupido.

¿Cómo funcionan los generadores de números aleatorios?

Korvin Szanto
fuente
2
Los generadores de números pseudoaleatorios usan una semilla, una tabla de constantes predefinidas y fórmulas matemáticas. Los generadores de números aleatorios reales usualmente usan ruido atmosférico. Puede obtener fácilmente números aleatorios de lectura / desarrollo / aleatorio.
derecha el
¿Se garantiza que el ruido atmosférico sea aleatorio?
14
function rand() { return 4; /* determined by die roll - guaranteed to be random */ }
Neil
3
Alguien tiene que hacer esto: xkcd.com/221 ;)
Valera Kolupaev

Respuestas:

7

Los generadores de números aleatorios (RNG) realmente están generando números pseudoaleatorios, ya que es imposible generar realmente un número aleatorio REAL. Las únicas cosas realmente verdaderamente aleatorias son los actos de Dios, como los rayos.

Este artículo de Wikipedia podría ayudarlo en la explicación: http://en.wikipedia.org/wiki/Random_number_generators


Por lo que entiendo, básicamente hay dos partes de un RNG: la semilla, y luego el número aleatorio elegido de esa semilla. Cuando siembras el RNG, le estás dando un equivalente a un punto de partida. Ese punto de partida tiene un montón de números que están "dentro" de los cuales el programa elige. En PHP, puede usar srand () para "mezclar" las semillas, por lo que casi siempre obtiene una respuesta diferente. Luego puede usar rand (min, max) para ir a la semilla y elegir un número entre min y max, inclusive.


¡ADVERTENCIA, POSIBLE ANÁLISIS DE QUESOS A CONTINUACIÓN!

Piense en cada 'semilla' como un cofre de hielo, y luego los números aleatorios como cubitos de hielo. Digamos que tienes 1000 cofres de hielo y cada cofre tiene 1000 cubitos de hielo adentro. En la feria del condado, elegirán una caja de hielo para comenzar a usar para bebidas, y solo pueden usar un cubo de hielo. Sin embargo, solo necesitan cubitos de hielo de más de 1 pulgada cúbica. Entonces elegirán un cofre al azar entre esos 1000 cofres, y luego elegirán un cubo de hielo dentro de ese cofre al azar. Si funciona para el tamaño que desean, lo usan. Si no es así, lo vuelven a colocar en el cofre con los demás. Si quieren que sea un poco más divertido, cambian los cofres de antemano por olvido total, ¡si quieres!

En cuanto a cómo PHP realmente elige físicamente la semilla y el número aleatorio, no tengo suficiente conocimiento para eso (¡eso es probablemente lo que más te preguntabas!). No intentaría rehacer la función rand (); para la mayoría de las aplicaciones basadas en web que creará, rand () debería ser suficiente para cualquier número aleatorio que necesite.

También consulte los generadores congruentes lineales, esto podría ser más de lo que está buscando si desea los detalles sucios: http://en.wikipedia.org/wiki/Linear_congruential_generator

¡Espero que esto ayude!


fuente
77
¿Cómo serían los actos de godser aleatorio en lo más mínimo? Además de eso, el rayo tampoco es aleatorio, sigue un camino determinado por varias condiciones. Además, el intérprete que genera el número es esencialmente irrelevante.
77
Estoy usando actos de Dios en el sentido legal: en.wikipedia.org/wiki/Act_of_God Se consideran aleatorios ya que están más allá del control humano aparente.
44
Entonces, esencialmente, no hay nada que sea aleatorio. Pero eso requeriría que cada evento aparentemente aleatorio sea influenciado, lo que no funciona cuando llegas al principio de los tiempos ... Parece que voy a tomar algunas clases de filosofía = D
66
@Korvin, hasta donde sabemos, los fenómenos cuánticos como la desintegración radiactiva o la emisión de un fotón por un átomo excitado son realmente aleatorios. Sin embargo, los matemáticos y filósofos argumentan lo que significa ser genuinamente aleatorio. Y aunque la gente común piensa que lanzar una moneda es bastante aleatorio, los magos ágiles del escenario ( news.stanford.edu/pr/2004/diaconis-69.html ) pueden obtener regularmente 10 caras en 10 lanzamientos .
Charles E. Grant
1
@Charles: un lanzamiento de moneda ni siquiera es cara / cruz binaria, en realidad es cara / cruz / borde, por lo que un mago de escenario realmente bueno podría hacer que no caiga cara ni cruz. * 8 ')
Mark Booth
18

Por lo general, no son realmente aleatorios, pero se llaman pseudoaleatorios porque generan una secuencia numérica que parece aleatoria. Esto se hace con algunas fórmulas matemáticas interesantes. Uno de los más comunes es el generador congruencial lineal .

Los números pseudoaleatorios tienen una propiedad útil que los números aleatorios verdaderos no tienen: si usa la misma semilla al comenzar, obtendrá una secuencia idéntica. Esto puede ser muy útil para las pruebas.

Mark Ransom
fuente
Si entiendo su segunda declaración correctamente: random(5332)¿siempre será igual a random(5332)?
2
@Korvin, no, quiero decir que si llamas srand(5332), el próximo número que devuelva randsiempre será el mismo.
Mark Ransom
3
"parece aleatorio" -> tiene las mismas propiedades estadísticas que los números verdaderamente aleatorios.
+1 para el enlace LGC Wikipedia, esta tiene una excelente animación de por qué los PRNG simples tienen serias limitaciones al hacer simulaciones multidimansionales de Monte-Carlo.
Mark Booth
4

¿Estás pidiendo pseudoaleatorio o aleatorio? Otros respondieron sobre pseudoaleatorio, déjenme hablar sobre Random.

Había (¿hay?) Generadores de números aleatorios reales basados ​​en hardware en venta. Se basaban en un chip con una pequeña radio que medía el ruido blanco de la radiación del espacio profundo, o una pequeña muestra radiactiva que medía los períodos entre su descomposición. El problema con ellos era el ancho de banda: la cantidad de entropía que podían generar no era muy alta, por lo que se usaban para semillas de algoritmos pseudoaleatorios. Se utilizaron en sistemas bancarios, de alta seguridad y similares.

OTOH, si conoces a algún desarrollador de sistemas integrados, se reirán de ellos. Para fines comunes en la programación de un microcontrolador, leer 4 bits bajos de cualquier convertidor analógico-digital de 16 bits con un pin flotante (sin conexión) producirá un ruido aleatorio perfectamente bueno, con un ancho de banda más que suficiente (cuanto más corto sea el período de sondeo, más " ruidoso "la lectura), y más fácil que escribir la rutina RNG real. Y teniendo en cuenta que los ADC se encuentran comúnmente implementados en silicio de microcontroladores, comúnmente implementados y a menudo implementados con 8 canales de los cuales necesita quizás 5 para su aplicación, es prácticamente gratis.

E incluso si no tiene un ADC, un par de elementos conectados a un pin GPIO digital producirá un ruido bastante bueno. En embebido, el ruido está siempre presente (y se combate constantemente), por lo que es muy fácil obtener cierta aleatoriedad.

SF.
fuente
2

Hay muchas formas de intentar emular una secuencia de números "aleatoria". Su primera parada debería ser leer sobre generadores congruenciales lineales , seguro. Así es como funcionan los generadores de números aleatorios más básicos, y apuesto a que es cómo funciona la función rand () de PHP.

La siguiente pregunta más interesante para reflexionar es ¿cómo se siembra a sí misma? ¿hora? ¿Dirección IP? etc.


fuente
La semilla es lo que me confunde, no puedo pensar en nada que pueda sembrar la función sin algún tipo de patrón, e incluso si no es así, ¡qué causa que se genere la semilla aleatoria en primer lugar!
3
Creo que una marca de tiempo a menudo se usa como semilla inicial cuando en realidad no se proporciona ninguna de otra fuente. En el antiguo BASIC, RANDOMIZE TIMERera un idioma común, y "lo suficientemente bueno" para la mayoría de los propósitos (no criptográficos). Según man 3 srand , la biblioteca GNU C utiliza una semilla fija de 1 hasta que se reinicia el PRNG.
un CVn
1

En primer lugar, prácticamente todas las rand()funciones no proporcionan una aleatoriedad verdadera, sino que proporcionan los llamados números pseudoaleatorios.

Entonces, ¿cómo funcionan los generadores de números pseudoaleatorios? Básicamente, de la misma manera que funciona el cifrado: tiene una función (un hash) que toma alguna entrada y produce una salida de una manera tan compleja que es imposible que la salida adivine la entrada o viceversa. Es decir, cada cifrador se puede utilizar para crear un generador pseudoaleatorio bastante bueno. Sin embargo, aunque en principio podría usar cualquier generador pseudoaleatorio para realizar el cifrado, la mayoría de los generadores de números pseudoaleatorios se desarrollan principalmente para la velocidad, no para la seguridad criptográfica, por lo que no les darán dolores de cabeza a los piratas informáticos.

Para un generador pseudoaleatorio, la función hash se aplica a algún estado interno oculto del generador, y su salida se utiliza para a) modificar ese estado interno, yb) para calcular la salida de la rand()función. La próxima invocación de rand()utilizará ese estado interno modificado y, por lo tanto, producirá un resultado diferente. Cuanto mejor sea la función hash, menos fácilmente se distinguirán los resultados de los números aleatorios verdaderos.


De hecho, las computadoras hoy en día tienen acceso a números aleatorios reales: provienen de la fluctuación en el tiempo de las interrupciones producidas por dispositivos externos. Linux utiliza estos valores de pequeña incertidumbre para agitar constantemente un "grupo de entropía", que es solo unos pocos kilobytes de estado interno. Los hash criptográficos basados ​​en este grupo de entropía están disponibles a través de los dispositivos /dev/randomy /dev/urandom. Entonces, el acceso a algunos números aleatorios realmente buenos es tan simple como abrir uno de estos dos dispositivos y leer algunos bytes de ellos.

cmaster - restablecer monica
fuente
-2

Los números aleatorios son números generados por el proceso cuya salida es impredecible. es decir, no podemos decir cuál será la próxima salida. Podemos tomar un ejemplo simple de resultado de los dados. Lo que se generará cuando lancemos un dado es impredecible.

Hay dos tipos de números aleatorios 1. Números aleatorios verdaderos 2. Números pseudoaleatorios.

Cómo se generan los números aleatorios

Badal
fuente
1
Utilice el formato de cotización para resaltar qué partes de la respuesta son suyas y cuáles provienen de la fuente que cita. Si toda su respuesta es copiar / pegar desde una fuente externa, no es una buena respuesta aquí.
Mat
esto no parece ofrecer nada sustancial sobre los puntos hechos y explicados en las 6 respuestas anteriores
mosquito