¿Puede un generador de números aleatorios producir resultados diferentes dados semillas idénticas?

10

El título lo resume. Estoy interesado en saber si existe un algoritmo capaz de producir una salida variable dada una entrada idéntica sin depender de otras fuentes de aleatoriedad como DateTime.Now o un número generado por un sensor de luz, etc. Además, el algoritmo no se puede ejecutar en secuencia, solo dos ejecuciones distintas y no relacionadas que producen resultados diferentes.

random CondiciónRacer
fuente
De lo que estás hablando es de un generador de números aleatorios, para ser específicos.
Marcel
La mayoría de los idiomas permiten la posibilidad de crear instancias de un generador de números aleatorios sin tener que especificar la semilla para que la semilla también sea "aleatoria". Hay una razón por la cual se usan semillas.
Neil
1
@Neil: en esos casos, todavía hay una semilla, es implícito, generalmente la hora del sistema.
Michael Borgwardt
@MichaelBorgwardt, simplemente dije que la semilla también sería aleatoria. Por supuesto, nada es realmente aleatorio, pero por lo general el tiempo del sistema proporciona una semilla decente, siempre y cuando no se genere una instancia de un generador de números aleatorios sin pasar una semilla, en cuyo caso puede obtener la misma semilla "aleatoria" dos veces.
Neil
Hay un área de investigación interesante en hardware inexacto, que tiene una inexactitud estadísticamente bien definida. El beneficio potencial es un menor uso de energía. Simplemente calcular 2.0 + 2.0en un sistema de este tipo no daría resultados idénticos. No necesita otra fuente de aleatoriedad.
MSalters

Respuestas:

15

Estoy interesado en saber si existe un algoritmo capaz de producir una salida variable dada una entrada idéntica sin depender de otras fuentes de aleatoriedad como DateTime.Now o un número generado por un sensor de luz, etc.

No, eso es fundamentalmente imposible, porque la definición misma de un algoritmo es que está bien definido y es determinista, es decir, dado que la misma entrada siempre producirá la misma salida. Hay algoritmos aleatorios, pero requieren aleatoriedad como entrada.

Además, el determinismo es el objetivo de diseño más importante del hardware de la computadora. Una CPU que no produce la misma salida dada la misma entrada sería completamente inútil para la mayoría de los propósitos.

Michael Borgwardt
fuente
14

No, un algoritmo de generación de números pseudo-aleatoria siempre producirá la misma salida dada la misma semilla (por lo tanto pseudo- RANDOM).

Me parece interesante que haya utilizado el término "algoritmo" en lugar de "programa". Esto excluye una cierta clase de respuestas afirmativas (errores de software en RAM, diferentes entrelazados de subprocesos en un RNG multiproceso, etc.). Si da por sentado que cada ejecución de su algoritmo toma la misma entrada en cada iteración está bien especificada sin aleatoriedad, generará la misma salida en cada ejecución.

Dicho esto, incluso cosas básicas como la temperatura de la CPU son lo suficientemente impredecibles como para actuar como fuente de entropía si se normalizan adecuadamente. Por lo tanto, no piense que esto implica que se puede predecir un generador de números aleatorios "criptográficamente seguro" si sabe a qué hora se ejecutó; muchos de ellos hacen uso de la alimentación de entropía generada por el sistema.

Brian
fuente
Algoritmo era la palabra correcta :) Estoy tratando específicamente de eliminar fuentes externas de entropía, fallas de memoria, orden de hilos, entradas impredecibles como una fuente de luz, etc. Creo que mi pregunta surge de mi falta de comprensión de algoritmos aleatorios y tal vez Podría haber hecho la pregunta más genérica. Realmente me pregunto si es posible crear alguna función que devuelva resultados diferentes con una entrada idéntica (incluidas todas las fuentes de entropía). Parece que la respuesta es no
ConditionRacer
7

¿Sabía que las personas trabajan muy duro para garantizar que, dada la misma semilla, se produzca la misma secuencia de números aleatorios cada vez? Esta es una propiedad deseable para cosas como la simulación de Monte Carlo, ya que significa que los resultados son completamente reproducibles. Si no especifica la semilla, se usará algo así como el tiempo, pero esa reproducibilidad exacta es realmente deseada.

Los únicos RNG en los que esto no es realmente deseado son los que se usan para la criptografía, y generalmente lo logran utilizando la fuente de números aleatorios del sistema operativo (que no es rebobinable en circunstancias normales y que puede usar hardware sofisticado) para proporcionar su semilla.

Compañeros de Donal
fuente
Sí, entiendo lo que estás diciendo. No estoy tratando de implementar nada nuevo, esto fue solo una curiosidad nocturna.
ConditionRacer
1

Supongo que si implementó el algoritmo en diferentes plataformas de hardware y utilizó técnicas como tomar los N bits medios de un entero, posiblemente podría obtener diferentes respuestas si la codificación del entero fuera diferente (grande / pequeño / medio-endiano). También es posible que se encuentre con problemas que se ejecutan en máquinas con FPU versus aquellos que no lo hacen si está manipulando números de punto flotante. Probablemente no sea un problema en las máquinas de escritorio, pero podría ser un problema en los teléfonos.

TMN
fuente