Cómo generar un número entero aleatorio dentro de un rango

3 minutos de lectura

avatar de usuario
jamie keeling

Esta es una continuación de una pregunta publicada anteriormente:

¿Cómo generar un número aleatorio en C?

Deseo poder generar un número aleatorio dentro de un rango particular, como 1 a 6 para imitar los lados de un dado.

¿Cómo haría para hacer esto?

  • si observa la segunda respuesta a la pregunta a la que se refiere, tiene la respuesta. al azar() % 6.

    –Mats Fredriksson

    24 de marzo de 2010 a las 16:58

  • No entendí cómo funcionaba, así que decidí hacer una pregunta separada para mayor claridad.

    – Jamie Keeling

    24 de marzo de 2010 a las 17:29

  • Pensamiento aleatorio: si encuestó a una muestra representativa aleatoria de programadores, encontraría que un número aleatorio de ellos está pensando aleatoriamente en formas de generar números aleatoriamente. Teniendo en cuenta que el Universo se rige por leyes precisas y predecibles, ¿no es interesante que intentemos generar cosas de forma más aleatoria? Preguntas como esta siempre tienden a sacar a relucir los carteles de más de 10k.

    – Armstrongest

    24 de marzo de 2010 a las 19:00


  • @Mats rand() % 6 puede devolver un 0. No es bueno para un dado.

    – nuevo123456

    5 de marzo de 2011 a las 19:33

  • ¿Puede marcar stackoverflow.com/a/6852396/419 como la respuesta aceptada en lugar de la respuesta que enlaza con ella 🙂 Gracias.

    – Kev

    27 de junio de 2012 a las 13:15

avatar de usuario
sattar

Aquí hay una fórmula si conoce los valores máximo y mínimo de un rango, y desea generar números inclusive entre el rango:

r = (rand() % (max + 1 - min)) + min

  • Como se señaló en la respuesta de Ryan, esto produce un resultado sesgado.

    – David Wolever

    10 de julio de 2014 a las 19:04

  • Resultado sesgado, potencial int desbordar con max+1-min.

    – chux – Reincorporar a Monica

    30 de diciembre de 2014 a las 21:28

  • esto funciona solo con enteros mínimos y máximos. Si el mínimo y el máximo son flotantes, no es posible realizar la operación %

    – Francesco Taioli

    11 de marzo de 2018 a las 18:16


  • Tenga en cuenta que esto se atascará en un bucle infinito si el rango> = RAND_MAX. Preguntame como lo se :/

    – el JPster

    23 de julio de 2013 a las 13:44

  • Tenga en cuenta que está comparando un int con un int sin signo (r> = límite). El problema se resuelve fácilmente haciendo limit un int (y opcionalmente bucket también) desde RAND_MAX / range < INT_MAX y buckets * range <= RAND_MAX. EDITAR: he enviado y editado la propuesta.

    – rrrrrrrrrrrrrrrr

    3 de enero de 2017 a las 10:51


  • la solución de @Ryan Reich aún me brinda una mejor distribución (menos sesgada)

    – Vladímir

    28 de junio de 2017 a las 18:20

avatar de usuario
Ratón

Si bien Ryan tiene razón, la solución puede ser mucho más simple según lo que se sabe sobre la fuente de la aleatoriedad. Para reformular el problema:

  • Hay una fuente de aleatoriedad, que genera números enteros en el rango [0, MAX) with uniform distribution.
  • The goal is to produce uniformly distributed random integer numbers in range [rmin, rmax] donde 0 <= rmin < rmax < MAX.

En mi experiencia, si el número de contenedores (o “cajas”) es significativamente menor que el rango de los números originales, y la fuente original es criptográficamente fuerte – no hay necesidad de pasar por todo ese galimatías, y bastaría con una simple división de módulo (como output = rnd.next() % (rmax+1)Si rmin == 0), y producir números aleatorios que se distribuyen uniformemente “suficientemente”, y sin pérdida de velocidad. El factor clave es la fuente de aleatoriedad (es decir, niños, no intenten esto en casa con rand()).

Aquí hay un ejemplo/prueba de cómo funciona en la práctica. Quería generar números aleatorios del 1 al 22, teniendo una fuente criptográficamente sólida que produjera bytes aleatorios (basado en Intel RDRAND). Los resultados son:

Rnd distribution test (22 boxes, numbers of entries in each box):     
 1: 409443    4.55%
 2: 408736    4.54%
 3: 408557    4.54%
 4: 409125    4.55%
 5: 408812    4.54%
 6: 409418    4.55%
 7: 408365    4.54%
 8: 407992    4.53%
 9: 409262    4.55%
10: 408112    4.53%
11: 409995    4.56%
12: 409810    4.55%
13: 409638    4.55%
14: 408905    4.54%
15: 408484    4.54%
16: 408211    4.54%
17: 409773    4.55%
18: 409597    4.55%
19: 409727    4.55%
20: 409062    4.55%
21: 409634    4.55%
22: 409342    4.55%   
total: 100.00%

Esto es lo más uniforme que necesito para mi propósito (lanzamiento de dados justo, generar libros de códigos criptográficamente fuertes para máquinas de cifrado de la Segunda Guerra Mundial como http://users.telenet.be/d.rijmenants/en/kl-7sim.htm, etc). La salida no muestra ningún sesgo apreciable.

Aquí está la fuente del generador de números aleatorios criptográficamente fuerte (verdadero):
Generador de números aleatorios digitales de Intel
y un código de muestra que produce números aleatorios de 64 bits (sin signo).

int rdrand64_step(unsigned long long int *therand)
{
  unsigned long long int foo;
  int cf_error_status;

  asm("rdrand %%rax; \
        mov $1,%%edx; \
        cmovae %%rax,%%rdx; \
        mov %%edx,%1; \
        mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx");
        *therand = foo;
  return cf_error_status;
}

Lo compilé en Mac OS X con clang-6.0.1 (directo) y con gcc-4.8.3 usando el indicador “-Wa,q” (porque GAS no admite estas nuevas instrucciones).

  • Compilado con gcc randu.c -o randu -Wa,q (GCC 5.3.1 en Ubuntu 16) o clang randu.c -o randu (Clang 3.8.0) funciona, pero vuelca el núcleo en tiempo de ejecución con Illegal instruction (core dumped). ¿Algunas ideas?

    – gato

    11 mayo 2016 a las 11:06

  • Primero, no sé si su CPU realmente admite la instrucción RDRAND. Su sistema operativo es bastante reciente, pero es posible que la CPU no lo sea. En segundo lugar (pero esto es menos probable): no tengo idea de qué tipo de ensamblador incluye Ubuntu (y Ubuntu tiende a estar bastante al revés, actualizando paquetes). Consulte el sitio de Intel al que me referí para conocer las formas de probar si su CPU es compatible con RDRAND.

    – Ratón

    7 de junio de 2016 a las 8:34


  • Efectivamente tienes buenos puntos. Lo que todavía no puedo entender es qué tiene de malo rand(). Intenté algunas pruebas y publiqué esta pregunta, pero todavía no puedo encontrar una respuesta definitiva.

    – mi radio

    20 de junio de 2018 a las 7:43

Aquí hay un algoritmo ligeramente más simple que la solución de Ryan Reich:

/// Begin and end are *inclusive*; => [begin, end]
uint32_t getRandInterval(uint32_t begin, uint32_t end) {
    uint32_t range = (end - begin) + 1;
    uint32_t limit = ((uint64_t)RAND_MAX + 1) - (((uint64_t)RAND_MAX + 1) % range);

    /* Imagine range-sized buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    uint32_t randVal = rand();
    while (randVal >= limit) randVal = rand();

    /// Return the position you hit in the bucket + begin as random number
    return (randVal % range) + begin;
}

Example (RAND_MAX := 16, begin := 2, end := 7)
    => range := 6  (1 + end - begin)
    => limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range)

The limit is always a multiple of the range,
so we can split it into range-sized buckets:
    Possible-rand-output: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
    Buckets:             [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X]
    Buckets + begin:     [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X]

1st call to rand() => 13
    → 13 is not in the bucket-range anymore (>= limit), while-condition is true
        → retry...
2nd call to rand() => 7
    → 7 is in the bucket-range (< limit), while-condition is false
        → Get the corresponding bucket-value 1 (randVal % range) and add begin
    => 3

  • Compilado con gcc randu.c -o randu -Wa,q (GCC 5.3.1 en Ubuntu 16) o clang randu.c -o randu (Clang 3.8.0) funciona, pero vuelca el núcleo en tiempo de ejecución con Illegal instruction (core dumped). ¿Algunas ideas?

    – gato

    11 mayo 2016 a las 11:06

  • Primero, no sé si su CPU realmente admite la instrucción RDRAND. Su sistema operativo es bastante reciente, pero es posible que la CPU no lo sea. En segundo lugar (pero esto es menos probable): no tengo idea de qué tipo de ensamblador incluye Ubuntu (y Ubuntu tiende a estar bastante al revés, actualizando paquetes). Consulte el sitio de Intel al que me referí para conocer las formas de probar si su CPU es compatible con RDRAND.

    – Ratón

    7 de junio de 2016 a las 8:34


  • Efectivamente tienes buenos puntos. Lo que todavía no puedo entender es qué tiene de malo rand(). Intenté algunas pruebas y publiqué esta pregunta, pero todavía no puedo encontrar una respuesta definitiva.

    – mi radio

    20 de junio de 2018 a las 7:43

avatar de usuario
Comunidad

Para aquellos que entienden el problema del sesgo pero no pueden soportar el tiempo de ejecución impredecible de los métodos basados ​​en el rechazo, esta serie produce un entero aleatorio progresivamente menos sesgado en el [0, n-1] intervalo:

r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...

Lo hace sintetizando un número aleatorio de punto fijo de alta precisión de i * log_2(RAND_MAX + 1) bits (donde i es el número de iteraciones) y realizando una larga multiplicación por n.

Cuando el número de bits es lo suficientemente grande en comparación con nel sesgo se vuelve inmensamente pequeño.

no importa si RAND_MAX + 1 es menos que n (como en esta pregunta), o si no es una potencia de dos, pero se debe tener cuidado para evitar el desbordamiento de enteros si RAND_MAX * n es largo.

  • RAND_MAX es seguido INT_MAXasi que RAND_MAX + 1 –> UB (como INT_MIN)

    – chux – Reincorporar a Monica

    30 de diciembre de 2014 a las 21:30

  • @chux a eso me refiero con “se debe tener cuidado para evitar el desbordamiento de enteros si RAND_MAX * n es grande”. Debe hacer arreglos para usar los tipos apropiados para sus requisitos.

    – sh1

    31 de diciembre de 2014 a las 5:42

  • @chux “RAND_MAX es seguido INT_MAX“Sí, ¡pero solo en sistemas de 16 bits! Cualquier arquitectura razonablemente moderna pondrá INT_MAX a 2^32 / 2 y RAND_MAX en 2^16 / 2. ¿Es esta una suposición incorrecta?

    – gato

    10 de mayo de 2016 a las 1:28


  • @cat Probado hoy 2 32 bits int compiladores, encontré RAND_MAX == 32767 en uno y RAND_MAX == 2147483647 en otro. Mi experiencia general (décadas) es que RAND_MAX == INT_MAX más a menudo. Así que no estoy de acuerdo con que una arquitectura razonablemente moderna de 32 bits sin duda tendrá un RAND_MAX en 2^16 / 2. Dado que la especificación C permite 32767 <= RAND_MAX <= INT_MAXCodifico eso de todos modos en lugar de una tendencia.

    – chux – Reincorporar a Monica

    10 mayo 2016 a las 14:13


  • Todavía cubierto por “se debe tener cuidado para evitar el desbordamiento de enteros”.

    – sh1

    12 de mayo de 2016 a las 6:35

¿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