implementación de rand()

7 minutos de lectura

avatar de usuario
rlbond

Estoy escribiendo un 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, que tenga poca sobrecarga de espacio, que produzca números aleatorios de calidad relativamente alta. ¿Alguien sabe qué algoritmo usar o código de muestra?

EDITAR: es para el procesamiento de imágenes, por lo que “calidad relativamente alta” significa una duración de ciclo decente y buenas propiedades uniformes.

  • ¿Qué estás buscando, más específicamente? ¿Necesitas una duración de ciclo larga? ¿Qué tan grandes son los números de los que estamos hablando (16 bits, 32 bits, lo que sea)? ¿Qué tan aleatorios tienen que ser? Por “sobrecarga de espacio”, ¿se refiere a limitaciones de ROM, limitaciones de RAM o ambas?

    –David Thornley

    22 de julio de 2009 a las 18:51

  • Si tiene un SysTick o algo más que se puede usar para contar el tiempo desde el encendido hasta la hora actual, puede usar ese contador como semilla para algunos de los generadores aleatorios que se muestran a continuación.

    – Avra

    2 de julio de 2012 a las 8:36


  • Aquí hay una implementación de la Tornado de Mersenne en una clase de C++

    – bobobobo

    3 de agosto de 2015 a las 10:54

avatar de usuario
Juan D. Cook

Mira esto colección de generadores de números aleatorios de Jorge Marsaglia. Es un destacado experto en la generación de números aleatorios, por lo que estaría seguro de usar cualquier cosa que 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 estrictas pruebas estadísticas, aunque no servirían para la criptografía.

  • Gracias por la referencia a eso. Investigué un poco y encontré “KISS: un poco demasiado simple”, de Greg Rose que (a) advierte contra valores de semilla “malos” en MWC y (b) arroja dudas sobre el generador SHR3. Esta publicación de 2003 de Marsaglia da un SHR3 ligeramente diferente que soluciona los problemas que tenía el anterior. Estaría feliz de usar el generador de estilo KISS, siempre y cuando verifique y evite las semillas “malas”, y me asegure de estar usando el mejor generador SHR3.

    –Craig McQueen

    20 de enero de 2011 a las 2:06


  • Marsaglia hizo importantes contribuciones en los años 90 a los PRNG, sin embargo, hoy probablemente miraría a L’Ecuyer o Matsumoto, creo. Dicho esto, si el OP no realiza una simulación importante en sus dispositivos integrados, supongo que la mayoría de los buenos generadores anteriores también se pueden usar 🙂

    – joey

    26 de enero de 2011 a las 1:13

  • @Joey: Los generadores KISS de Marsaglia aún funcionan bien en L´Ecuyer´s TestU01 Pruebas RNGsuperando pruebas que incluso algunos RNG propios de L’Ecuyer como LFSR113 fallar.

    –Craig McQueen

    20 de febrero de 2011 a las 22:50

Utilizar el codigo c por 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.

  • Tenga en cuenta que asume un int de 32 bits, que puede no ser apropiado para una plataforma integrada.

    – tomlogic

    7 de junio de 2011 a las 17:49

  • ¿Por qué exactamente esto es aleatorio?

    – yo yo

    2 de mayo de 2013 a las 1:52

  • yo yo, depende de lo que entiendas por aleatorio. Los LFSR RNG se basan en una recurrencia matemática bien definida con un período conocido y buenas propiedades estadísticas (aleatoriedad percibida). A menos que esté tomando entropía de algún fenómeno físico (por ejemplo, ruido de línea), cualquier RNG que use será igualmente pseudoaleatorio. (Los RNG criptográficamente seguros son más complejos pero siguen siendo pseudoaleatorios). El Mersenne Twister más fuerte es un GFSR torcido, por lo que está relacionado con el anterior, y el Xorshift más débil es un caso especial de LFSR. Sin embargo, los RNG de CMWC pueden ser más rápidos y más fuertes que cualquiera de esos.

    – Mike S.

    18 de julio de 2013 a las 22:22

  • @me me: es pseudoaleatorio, las variables estáticas contienen valores iniciales. Siempre devuelve la misma secuencia de números.

    – k3a

    19 de julio de 2015 a las 13:31

  • Probablemente sea un error poner la semilla como estática en la respuesta, pero esto parece prometedor, solo asegúrese de proporcionar la semilla externamente. Lo intentaré. En cuanto a 32 bits, la fuente real usa uint32_t en lugar de int sin firmar, por lo que tampoco debería ser un problema.

    – AlexKven

    18 de agosto de 2018 a las 16:33


Aquí hay un enlace a un ANSI C implementación de algunos generadores de números aleatorios.

avatar de usuario
craig mcqueen

Hice una colección de generadores de números aleatorios, “simplealeatorio“, que son compactos y adecuados para sistemas integrados. La colección está disponible en C y Pitón.

Busqué un montón de simples y decentes que pude encontrar, y los junté en un paquete pequeño. Incluyen varios generadores Marsaglia (KISS, MWC, SHR3), y un par de L’Ecuyer LFSR.

Todos los generadores devuelven un entero de 32 bits sin signo y normalmente tienen un estado formado por 1 a 4 enteros de 32 bits sin signo.

Curiosamente, encontré algunos problemas con los generadores Marsaglia y traté de solucionar/mejorar todos esos problemas. Esos problemas fueron:

  • El generador SHR3 (componente del generador KISS de 1999 de Marsaglia) estaba averiado.
  • MWC low 16 bits tiene solo aproximadamente 229.1 período. Así que hice un MWC ligeramente mejorado, que le da a los 16 bits bajos un 259.3 período, que es el período total de este generador.

Descubrí algunos problemas con la inicialización y traté de crear procedimientos sólidos de inicialización (inicialización), para que no se rompan si les das un valor de inicialización “malo”.

avatar de usuario
norman ramsey

Recomiendo el trabajo académico. Dos implementaciones rápidas del generador de números aleatorios estándar mínimo por David Carta. Puede encontrar PDF gratis a través de Google. También vale la pena leer el artículo original sobre el generador de números aleatorios estándar mínimo.

El código de Carta brinda números aleatorios rápidos y de alta calidad en máquinas de 32 bits. Para una evaluación más completa, consulte el documento.

avatar de usuario
Yongyi Chen

Tornado de Mersenne

Un poco de Wikipedia:

  • Fue diseñado para tener un período de 219937 − 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 219937 combinaciones únicas (219937 es aproximadamente 4.3 × 106001; esto es muchos órdenes de magnitud mayor que el número estimado de partículas en el universo observable, que es 1080).
  • Tiene un orden muy alto de equidistribución dimensional (ver generador lineal congruente). Esto implica que existe una correlación serial insignificante entre valores sucesivos en la secuencia de salida.
  • Pasa numerosas pruebas de aleatoriedad estadística, incluidas las pruebas Diehard. Supera la mayoría de las pruebas de aleatoriedad TestU01 Crush, aún más estrictas, pero no todas.

  • código fuente para muchos idiomas disponibles en el enlace.

avatar de usuario
Daniel Earwicker

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 preocupación sobre la calidad de los números aleatorios, probablemente debería mirar bibliotecas matemáticamente escritas con más cuidado. Es un gran tema y el estándar. rand las implementaciones no son muy pensadas 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).

  • los rand.c El enlace del código fuente parece roto. Pruebe el repositorio git para rand.c y random.c

    –Craig McQueen

    14 de febrero de 2011 a las 1:05

  • Tenga en cuenta que el código estará bajo la GPL o LGPL. Conozca siempre la licencia de sus fuentes.

    – davenpcj

    17 abr 2013 a las 23:56

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad