¿Por qué se considera malo el uso de rand()? [duplicar]
El uso de rand()generalmente está mal visto a pesar de usar una semilla vía srand(). ¿Por qué sería ese el caso? ¿Qué mejores alternativas hay disponibles?
Hay dos partes en esta historia.
Generador de números pseudoaleatorios
Primero, randes un generador de números pseudoaleatorios . Esto significa que depende de una semilla. Para una semilla determinada, siempre dará la misma secuencia (suponiendo la misma implementación). Esto lo hace no adecuado para determinadas aplicaciones en las que la seguridad es una gran preocupación. Pero esto no es específico de rand. Es un problema con cualquier generador pseudoaleatorio. Y ciertamente hay muchas clases de problemas en los que un generador pseudoaleatorio es aceptable. Un verdadero generador aleatorio tiene sus propios problemas (eficiencia, implementación, entropía), por lo que para problemas que no están relacionados con la seguridad, la mayoría de las veces se utiliza un generador pseudoaleatorio.
Deficiencias de la biblioteca aleatoria de C y calidad de implementación
Entonces analizó su problema y concluyó que un generador pseudoaleatorio es la solución. Y aquí llegamos a los problemas reales con la biblioteca aleatoria de C (que incluye randy srand) que son específicos de ella y la hacen obsoleta (también conocida como: las razones por las que nunca deberías usar randla biblioteca aleatoria de C).
Un problema es que tiene un estado global (establecido por
srand). Esto hace que sea imposible utilizar varios motores aleatorios al mismo tiempo. También complica enormemente las tareas multiproceso.El problema más visible es que carece de motor de distribución :
randte da un número en intervalo[0 RAND_MAX]. Es uniforme en este intervalo, lo que significa que cada número en este intervalo tiene la misma probabilidad de aparecer. Pero la mayoría de las veces necesitas un número aleatorio en un intervalo específico. Digamos[0, 1017]. Una fórmula comúnmente utilizada (e ingenua) esrand() % 1018. Pero el problema con esto es que, a menos queRAND_MAXsea un múltiplo exacto de1018usted, no obtendrá una distribución uniforme.Otro problema es la calidad de la implementación de
rand. Hay otras respuestas aquí que explican esto mejor que yo, así que léalas.
C++
En C++ moderno, definitivamente deberías usar la biblioteca de C++, <random>que viene con múltiples motores aleatorios bien definidos y varias distribuciones para tipos de números enteros y de punto flotante.
Ninguna de las respuestas aquí explica la verdadera razón de ser rand() malo .
rand()es un generador de números pseudoaleatorios (PRNG) , pero esto no significa que deba ser malo. En realidad, existen PRNG muy buenos, que son estadísticamente difíciles o imposibles de distinguir de los verdaderos números aleatorios.
rand()está completamente definido en su implementación, pero históricamente se implementa como un Generador Lineal Congruencial (LCG) , que suele ser una clase de PRNG rápida, pero notoriamente mala. Los bits inferiores de estos generadores tienen una aleatoriedad estadística mucho menor que los bits superiores y los números generados pueden producir estructuras reticulares y/o planas visibles (el mejor ejemplo de esto es el famoso RANDU PRNG). Algunas implementaciones intentan reducir el problema de los bits inferiores desplazando los bits hacia la derecha en una cantidad predefinida; sin embargo, este tipo de solución también reduce el rango de salida.
Aún así, hay ejemplos notables de LCG excelentes, como los generadores congruentes lineales multiplicativos de 64 y 128 bits de L'Ecuyer presentados en Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure, Pierre L'Ecuyer, 1999 .
La regla general es que no te confíes rand(), utiliza tu propio generador de números pseudoaleatorios que se ajuste a tus necesidades y requisitos de uso.
Lo malo de rand/ srandes que rand...
- Utiliza un algoritmo no especificado para la secuencia de números que genera, aún
- permite que ese algoritmo se inicialice para
srandlograr una "aleatoriedad" repetible.
Estos dos puntos, tomados en conjunto, obstaculizan la capacidad de las implementaciones para mejorar la randimplementación de (por ejemplo, usar un generador criptográfico de números aleatorios [RNG] o un algoritmo "mejor" para producir números pseudoaleatorios). Por ejemplo, JavaScript Math.randomy FreeBSD arc4randomno tienen este problema, ya que no permiten que las aplicaciones los generen para una "aleatoriedad" repetible; es exactamente por esta razón que el motor JavaScript V8 pudo cambiar su Math.randomimplementación a una variante de xorshift128+while. preservando la compatibilidad con versiones anteriores. (Por otro lado, permitir que las aplicaciones proporcionen datos adicionales para complementar la "aleatoriedad", como en BCryptGenRandom, es menos problemático; aun así, esto generalmente se ve solo en RNG criptográficos).
También:
- El hecho de que el algoritmo y el procedimiento de inicialización de
randysrandno estén especificados significa que ni siquiera la "aleatoriedad" reproducible está garantizada entre implementacionesrand/ , entre versiones de la misma biblioteca estándar , entre sistemas operativos, etc.srand - Si
srandno se llama antesrand,randse comporta de manera similar como sisrand(1)se llamara por primera vez. En la práctica, esto significa querandsolo se puede implementar como un generador de números pseudoaleatorios (PRNG) en lugar de un RNG no determinista, y querandel algoritmo PRNG no puede diferir en una implementación determinada, ya sea que la aplicación llamesrando no.
EDITAR (8 de julio de 2020):
Hay una cosa más importante que es mala acerca de randy srand. randNada en el estándar C para estas funciones especifica una distribución particular que deben seguir los "números pseudoaleatorios" entregados , incluida la distribución uniforme o incluso una distribución que se aproxima a la distribución uniforme. uniform_int_distributionCompare esto con las clases y de C++ uniform_real_distribution, así como con los algoritmos generadores pseudoaleatorios específicos especificados por C++, como linear_congruential_enginey mt19937.
EDITAR (comenzado el 12 de diciembre de 2020):
Otra cosa mala de randand srand: srandrequiere una semilla que sólo puede ser del tamaño de un unsigned. unsigneddebe ser de al menos 16 bits y, en la mayoría de las implementaciones convencionales de C, unsignedes de 16 o 32 bits dependiendo del modelo de datos de la implementación (en particular, no de 64 bits, incluso si la implementación de C adopta un modelo de datos de 64 bits). Por lo tanto, no se pueden seleccionar más de 2^N secuencias diferentes de números de esta manera (donde N es el número de bits en un unsigned), incluso si el algoritmo subyacente implementado por randpuede producir muchas más secuencias diferentes que esa (digamos, 2^128 o incluso 2^19937 como en C++ mt19937).
En primer lugar, srand()no recibe una semilla, sino que pone una semilla. La siembra es parte del uso de cualquier generador de números pseudoaleatorios (PRNG). Cuando se siembra, la secuencia de números que el PRNG produce a partir de esa semilla es estrictamente determinista porque (¿la mayoría?) Las computadoras no tienen medios para generar números aleatorios verdaderos. Cambiar su PRNG no impedirá que la secuencia sea repetible desde la semilla y, de hecho, esto es algo bueno porque la capacidad de producir la misma secuencia de números pseudoaleatorios suele ser útil.
Entonces, si todos los PRNG comparten esta característica, ¿ rand()por qué se rand()considera malo? Bueno, todo se reduce a la parte "psuedo" del pseudoaleatorio. Sabemos que un PRNG no puede ser verdaderamente aleatorio, pero queremos que se comporte lo más parecido posible a un verdadero generador de números aleatorios, y existen varias pruebas que se pueden aplicar para verificar qué tan similar es una secuencia PRNG a una secuencia aleatoria verdadera. . Aunque su implementación no está especificada por el estándar, rand()en todos los compiladores comúnmente utilizados se utiliza un método de generación muy antiguo adecuado para hardware muy débil, y los resultados que produce son bastante pobres en estas pruebas. Desde entonces se han creado muchos mejores generadores de números aleatorios y es mejor elegir uno que se adapte a sus necesidades en lugar de confiar en uno de mala calidad que probablemente proporcione rand().
Cuál es adecuado para sus propósitos depende de lo que esté haciendo; por ejemplo, puede necesitar calidad criptográfica o generación multidimensional, pero para muchos usos en los que simplemente desea que las cosas sean uniformemente aleatorias, de generación rápida y no haya dinero disponible. la línea basada en la calidad de los resultados es probable que desee el generador xoroshiro128+ . Alternativamente, puede usar uno de los métodos en el <random>encabezado de C++, pero los generadores ofrecidos no son de última generación y ahora hay muchos mejores disponibles; sin embargo, siguen siendo lo suficientemente buenos para la mayoría de los propósitos y bastante convenientes.
Si hay dinero en juego (por ejemplo, para barajar cartas en un casino en línea, etc.), o necesita calidad criptográfica, debe investigar cuidadosamente los generadores adecuados y asegurarse de que se adapten exactamente a sus necesidades específicas.
