stackoverflow - implementación de rand()
rand_max c (11)
Estoy escribiendo algún código incrustado en C y necesito usar la función rand (). Desafortunadamente, rand () no es compatible con la biblioteca del controlador. Necesito una implementación simple que sea rápida, pero lo que es más importante, tiene poca sobrecarga de espacio, que produce números aleatorios de calidad relativamente alta. ¿Alguien sabe qué algoritmo usar o código de ejemplo?
EDITAR: Es para el procesamiento de imágenes, por lo que "calidad relativamente alta" significa una longitud de ciclo decente y buenas propiedades uniformes.
Aquí hay un enlace a una implementación ANSI C de algunos generadores de números aleatorios .
Echa un vistazo a esta colección de generadores de números aleatorios de George Marsaglia. Es un experto líder en la generación de números aleatorios, por lo que estaría seguro de usar cualquier cosa que él recomiende. Los generadores en esa lista son pequeños, algunos requieren solo un par de largos sin firmar como estado.
Los generadores de Marsaglia son definitivamente "de alta calidad" según sus estándares de larga duración y buena distribución uniforme. Pasan pruebas estadísticas rigurosas, aunque no lo harían para la criptografía.
Encontré esto: Generación de números aleatorios simple , por John D. Cook .
Debería ser fácil adaptarse a C, dado que solo son unas pocas líneas de código.
Edit: y podría aclarar lo que quiere decir con "relativamente alta calidad". ¿Está generando claves de cifrado para los códigos de lanzamiento nuclear o números aleatorios para un juego de póquer?
Hay un RNG simple llamado KISS , es un generador de números aleatorios de acuerdo con tres números.
/* Implementation of a 32-bit KISS generator which uses no multiply instructions */
static unsigned int x=123456789,y=234567891,z=345678912,w=456789123,c=0;
unsigned int JKISS32() {
int t;
y ^= (y<<5); y ^= (y>>7); y ^= (y<<22);
t = z+w+c; z = w; c = t < 0; w = t&2147483647;
x += 1411392427;
return x + y + w;
}
También hay un sitio web para probar RNG http://www.phy.duke.edu/~rgb/General/dieharder.php
He creado una colección de generadores de números aleatorios, " simplerandom ", que son compactos y adecuados para sistemas integrados. La colección está disponible en simplerandom y Python .
Busqué un montón de cosas simples y decentes que pude encontrar, y las puse juntas en un paquete pequeño. Incluyen varios generadores de Marsaglia (KISS, MWC, SHR3) y un par de LFSR de L''Ecuyer.
Todos los generadores devuelven un entero de 32 bits sin signo, y típicamente tienen un estado compuesto de 1 a 4 enteros sin signo de 32 bits.
Curiosamente, encontré algunos problemas con los generadores de Marsaglia, y he tratado de solucionar / mejorar todos esos problemas. Esos temas fueron:
- El generador SHR3 (componente del generador KISS de Marsaglia en 1999) se rompió.
- El MWC bajo de 16 bits tiene solo un período aproximado de 2 29.1 . Así que hice un MWC ligeramente mejorado, que otorga a los 16 bits bajos un período de 2 59.3 , que es el período general de este generador.
Descubrí algunos problemas con la siembra e intenté realizar procedimientos robustos de inicialización (inicialización), para que no se rompan si les das un valor de semilla "malo".
La solución estándar es utilizar un registro de desplazamiento de retroalimentación lineal .
Mejor aún, use múltiples registros de desplazamiento de retroalimentación lineal combinándolos juntos.
Suponiendo que sizeof(unsigned) == 4 :
unsigned t1 = 0, t2 = 0;
unsigned random()
{
unsigned b;
b = t1 ^ (t1 >> 2) ^ (t1 >> 6) ^ (t1 >> 7);
t1 = (t1 >> 1) | (~b << 31);
b = (t2 << 1) ^ (t2 << 2) ^ (t1 << 3) ^ (t2 << 4);
t2 = (t2 << 1) | (~b >> 31);
return t1 ^ t2;
}
Recomiendo el documento académico Dos implementaciones rápidas del generador de números aleatorios estándar mínimos de David Carta. Puedes encontrar PDF gratis a través de Google. También vale la pena leer el documento original sobre el generador de números aleatorios estándar mínimo.
El código de Carta proporciona números aleatorios rápidos y de alta calidad en máquinas de 32 bits. Para una evaluación más completa, ver el documento.
Tomaría uno de la biblioteca GNU C, la fuente está disponible para navegar en línea.
http://qa.coreboot.org/docs/libpayload/rand_8c-source.html
Pero si tiene alguna inquietud acerca de la calidad de los números aleatorios, probablemente debería buscar bibliotecas escritas más cuidadosamente. Es un tema importante y las implementaciones estándar de rand no son muy consideradas por los expertos.
Aquí hay otra posibilidad: http://www.boost.org/doc/libs/1_39_0/libs/random/index.html
(Si encuentra que tiene demasiadas opciones, siempre puede elegir una al azar).
Use el código C para LFSR113 de L''écuyer :
unsigned int lfsr113_Bits (void)
{
static unsigned int z1 = 12345, z2 = 12345, z3 = 12345, z4 = 12345;
unsigned int b;
b = ((z1 << 6) ^ z1) >> 13;
z1 = ((z1 & 4294967294U) << 18) ^ b;
b = ((z2 << 2) ^ z2) >> 27;
z2 = ((z2 & 4294967288U) << 2) ^ b;
b = ((z3 << 13) ^ z3) >> 21;
z3 = ((z3 & 4294967280U) << 7) ^ b;
b = ((z4 << 3) ^ z4) >> 12;
z4 = ((z4 & 4294967168U) << 13) ^ b;
return (z1 ^ z2 ^ z3 ^ z4);
}
Muy alta calidad y rápido. NO use rand () para nada. Es peor que inútil.
Un poco de Wikipedia:
- Fue diseñado para tener un período de 2 19937 - 1 (los creadores del algoritmo demostraron esta propiedad). En la práctica, hay pocas razones para usar un período mayor, ya que la mayoría de las aplicaciones no requieren 2 19937 combinaciones únicas (2 19937 es aproximadamente 4.3 × 10 6001 ; esto es muchos órdenes de magnitud más grande que el número estimado de partículas en el universo observable , que es 10 80 ).
- Tiene un orden muy alto de equidistribución dimensional (ver generador lineal congruente). Esto implica que hay una correlación serial despreciable entre los valores sucesivos en la secuencia de salida.
Pasa numerosas pruebas de aleatoriedad estadística, incluidas las pruebas de Diehard. Pasa la mayoría, pero no todas, de las pruebas de aleatoriedad de aplastamiento TestU01 aún más estrictas.
Código fuente para muchos idiomas disponibles en el enlace.