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

Question 1

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?

Question 2

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

Question 3

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).

Question 4

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

Question 5

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.

¿Ha sido útil esta solución?