Una respuesta reciente menciona el uso de los generadores de números aleatorios ( RNG ) Fortuna o Mersenne Twister para sembrar una simulación de Monte Carlo . No había oído hablar de Fortuna antes, así que lo busqué, parece que está destinado principalmente para uso criptográfico.
Actualmente uso un Mersenne Twister en el código de producción para sembrar un algoritmo K-Means.
¿Cuál (Fortuna o Mersenne Twister) se considera el mejor para aplicaciones de "siembra algorítmica" (por ejemplo, siembra Monte Carlo y K-Means)? ¿O es una "sacudida", es decir, usar la más conveniente.
Desde donde estoy sentado, "el mejor" debe proporcionar números aleatorios de la más alta calidad, operar rápidamente y (posiblemente) tener poca huella de memoria. De estos, la calidad es probablemente la más importante para la mayoría de nosotros.
fuente
RAND_MAX=32768valores posibles. Actualmente estoy usando MT para el simulador de trazado de rayos de Monte Carlo. Sin embargo, no veo la MT como un cuello de botella de rendimiento en mi generador de perfiles, probablemente porque estoy haciendo una generación "aleatoria" de cosas como direcciones de rayos como un preproceso . Por ejemplo, podría generar una matriz de 100,000 rayos al inicio, almacenarlos en una matriz y seleccionar aleatoriamente la posición de inicio de la matriz en tiempo de ejecución (ejecutando 10,000 rayos más o menos de la colección). Esto tiene una sobrecarga de memoria relativamente alta, a cambio de buenas distribuciones de números aleatorios.Respuestas:
Bueno, todo es una compensación de un tipo u otro. Para los generadores de números aleatorios, los agrupo en 3 categorías básicas:
Los PRNG congruentes lineales (el método generalmente implementado en la mayoría de las bibliotecas) están sólidamente en la categoría 1. Tanto Fortuna como Mersenne Twister están sólidamente en la categoría 2.
Para un artículo interesante sobre cómo arruinar un algoritmo de barajado puede costarle a su empresa / casino, le recomiendo este de 1999 . Debido a la rotura del enlace, las imágenes se han ido, pero la figura 4, aquella en la que traza el siguiente número fuera del PRNG contra el número anterior generado, es un conjunto de líneas paralelas.
Como señala JM, Fortuna es lenta. Como has señalado, Mersenne Twister es razonablemente rápido.
fuente
La opción predeterminada en la categoría "criptográfica" es Blum-Blum-Shub , creo. Como ya dice la página de Wikipedia, esto no es adecuado para simulaciones porque es demasiado lento.
Si está ejecutando en un sistema similar a Unix, también podría considerar obtener sus números aleatorios directamente de / dev / urandom , el servicio del sistema operativo que proporciona números aleatorios de buena calidad (aunque no necesariamente criptográficos). Dependiendo del sistema operativo particular que esté utilizando, esto puede usar el algoritmo Yarrow, del cual Fortuna es una variante. Pero el aspecto más interesante es que el sistema operativo tiene acceso a algunos números aleatorios verdaderos: el ruido térmico de los sensores de temperatura internos, por ejemplo. Por lo general, estos datos se mezclan en el grupo aleatorio siempre que estén disponibles para mantener los datos impredecibles.
Este concepto de mezclar al azar sugiere que podría ser posible obtener lo mejor de ambos mundos de la siguiente manera. Use un generador de números aleatorios más rápido y de calidad razonable, como Mersenne, como su RNG básico. Mantenga también un segundo generador de números aleatorios de mejor calidad, por ejemplo, Fortuna. Cada tantos números, digamos 25, ejecutan una iteración del mejor RNG y agregan el resultado al estado de su RNG básico. De esta manera obtendría un rendimiento bastante alto y resultados de calidad bastante alta. (Supongo que sería inútil para la criptografía, porque la fuerza de este generador compuesto podría ser la fuerza del enlace más débil. Pero para las simulaciones, donde normalmente no tienes un adversario malicioso, podría funcionar).
fuente
Quería intervenir para decir eso, recientemente he pasado por este proceso con una simulación y debo tener en cuenta que usar Fortuna no está fuera de discusión si es realmente necesario. En nuestro caso, nos preocupaba que la entropía de MT no fuera lo suficientemente alta, lo que se traduciría en nuestra simulación a un sesgo. Entonces, para nuestra simulación, usamos Fortuna sacando alrededor de 65 mil millones de números aleatorios de ese algo. El punto es que las computadoras son rápidas, si realmente lo necesitas puedes usarlo si tienes una razón. Si solo está haciendo algo como una integración de Monte Carlo, quédese con MT.
fuente
Creo que la respuesta depende en gran medida de la aplicación para la que vaya a utilizar el RNG. Sugeriría una cuarta categoría para la clasificación aproximada de Tangurena: "Bueno sin ganancia real".
Para muchas aplicaciones, puede que simplemente no importe, y un RNG de grado criptográfico adecuado puede simplemente ralentizar sus tareas sin ninguna ganancia proporcional de validez. Por ejemplo, gran parte de la investigación que hago solo requiere muchos, muchos millones de números que provienen aproximadamente de una distribución que especifico. Casi cualquier RNG servirá, así que todo lo que necesito es uno que no sea tan catastróficamente pobre como para no tener valor como un RNG. Cualquier otra cosa es simplemente ralentizar el trabajo innecesariamente. Tiendo a usar Mersenne Twister, pero eso es simplemente porque funciona lo suficientemente bien, tengo el código y es razonablemente rápido.
fuente