rand_max - Cómo generar un número entero al azar dentro de un rango
random number in c between 1 and 100 (10)
¿No solo lo harías?
srand(time(NULL));
int r = ( rand() % 6 ) + 1;
% es el operador de módulo. Básicamente se dividirá por 6 y devolverá el resto ... de 0 a 5
Este es un seguimiento 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 voy a hacer esto?
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
Aquí hay una fórmula si conoce los valores máximo y mínimo de un rango, y desea generar números incluidos dentro del rango:
r = (rand() % (max + 1 - min)) + min
Como se dijo antes, el módulo no es suficiente porque sesga la distribución. Aquí está mi código que enmascara bits y los usa para asegurar que la distribución no sea sesgada.
static uint32_t randomInRange(uint32_t a,uint32_t b) {
uint32_t v;
uint32_t range;
uint32_t upper;
uint32_t lower;
uint32_t mask;
if(a == b) {
return a;
}
if(a > b) {
upper = a;
lower = b;
} else {
upper = b;
lower = a;
}
range = upper - lower;
mask = 0;
//XXX calculate range with log and mask? nah, too lazy :).
while(1) {
if(mask >= range) {
break;
}
mask = (mask << 1) | 1;
}
while(1) {
v = rand() & mask;
if(v <= range) {
return lower + v;
}
}
}
El siguiente código simple le permite ver la distribución:
int main() {
unsigned long long int i;
unsigned int n = 10;
unsigned int numbers[n];
for (i = 0; i < n; i++) {
numbers[i] = 0;
}
for (i = 0 ; i < 10000000 ; i++){
uint32_t rand = random_in_range(0,n - 1);
if(rand >= n){
printf("bug: rand out of range %u/n",(unsigned int)rand);
return 1;
}
numbers[rand] += 1;
}
for(i = 0; i < n; i++) {
printf("%u: %u/n",i,numbers[i]);
}
}
Para aquellos que entienden el problema del sesgo pero no soportan el tiempo de ejecución impredecible de los métodos basados en el rechazo, esta serie produce un entero aleatorio sesgado menos progresivo en el intervalo [0, n-1] :
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 alta precisión de puntos fijos de i * log_2(RAND_MAX + 1) bits (donde i es el número de iteraciones) y realizando una multiplicación larga por n .
Cuando el número de bits es suficientemente grande en comparación con n , el sesgo se vuelve inconmensurablemente pequeño.
No importa si RAND_MAX + 1 es menor que n (como en esta pregunta ), o si no tiene una potencia de dos, pero se debe tener cuidado para evitar el desbordamiento de enteros si RAND_MAX * n es grande.
Para evitar el sesgo del módulo (sugerido en otras respuestas), siempre puede usar:
arc4random_uniform(MAX-MIN)+MIN
Donde "MAX" es el límite superior y "MIN" es límite inferior. Por ejemplo, para números entre 10 y 20:
arc4random_uniform(20-10)+10
arc4random_uniform(10)+10
Solución simple y mejor que usar "rand ()% N".
Si bien Ryan tiene razón, la solución puede ser mucho más sencilla en función de lo que se sabe sobre la fuente de la aleatoriedad. Para volver a establecer el problema:
- Existe una fuente de aleatoriedad que da salida a números enteros en el rango
[0, MAX)con distribución uniforme. - El objetivo es producir números enteros aleatorios distribuidos uniformemente en el rango
[rmin, rmax]donde0 <= 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 rigamarole, y la división de módulo simple basta (como output = rnd.next() % (rmax+1) , si rmin == 0 ), y produce números aleatorios que se distribuyen uniformemente "suficiente", y sin ninguna pérdida de velocidad. El factor clave es la fuente de aleatoriedad (es decir, niños, no intentes 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, con una fuente criptográficamente fuerte que produjera bytes aleatorios (basados 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 cercano al uniforme que necesito para mi propósito (tiro justo de dados, generación de 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): Intel Digital Random Number Generator y un código de muestra que produce números aleatorios de 64 bits (sin firmar).
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).
Siguiendo la respuesta de @Ryan Reich, pensé en ofrecer mi versión limpia. La primera verificación de límites no es necesaria dado el segundo control de límites, y lo he hecho iterativo en lugar de recursivo. Devuelve valores en el rango [min, max], donde max >= min y 1+max-min < RAND_MAX .
unsigned int rand_interval(unsigned int min, unsigned int max)
{
int r;
const unsigned int range = 1 + max - min;
const unsigned int buckets = RAND_MAX / range;
const unsigned int limit = buckets * range;
/* Create equal size 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. */
do
{
r = rand();
} while (r >= limit);
return min + (r / buckets);
}
Todas las respuestas hasta ahora son matemáticamente incorrectas. El retorno de rand() % N no da un número uniformemente en el rango [0, N) menos que N divida la longitud del intervalo en el que regresa rand() (es decir, es una potencia de 2). Además, uno no tiene idea de si los módulos de rand() son independientes: es posible que vayan 0, 1, 2, ... , que es uniforme pero no muy aleatorio. La única suposición que parece razonable es que rand() emite una distribución de Poisson: cualquier dos subintervalos no superpuestos del mismo tamaño son igualmente probables e independientes. Para un conjunto finito de valores, esto implica una distribución uniforme y también garantiza que los valores de rand() estén muy dispersos.
Esto significa que la única forma correcta de cambiar el rango de rand() es dividirlo en cuadros; por ejemplo, si RAND_MAX == 11 y desea un rango de 1..6 , debe asignar {0,1} a 1, {2,3} a 2, y así sucesivamente. Estos son intervalos disjuntos, de igual tamaño y, por lo tanto, se distribuyen de manera uniforme e independiente.
La sugerencia de utilizar la división de punto flotante es matemáticamente plausible pero, en principio, adolece de problemas de redondeo. Quizás el double es lo suficientemente alto como para hacer que funcione; talvez no. No lo sé y no quiero tener que resolverlo; en cualquier caso, la respuesta depende del sistema.
La forma correcta es usar la aritmética de enteros. Es decir, desea algo como lo siguiente:
#include <stdlib.h> // For random(), RAND_MAX
// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
unsigned long
// max <= RAND_MAX < ULONG_MAX, so this is okay.
num_bins = (unsigned long) max + 1,
num_rand = (unsigned long) RAND_MAX + 1,
bin_size = num_rand / num_bins,
defect = num_rand % num_bins;
long x;
do {
x = random();
}
// This is carefully written not to overflow
while (num_rand - defect <= (unsigned long)x);
// Truncated division is intentional
return x/bin_size;
}
El ciclo es necesario para obtener una distribución perfectamente uniforme. Por ejemplo, si le dan números aleatorios de 0 a 2 y quiere solo los de 0 a 1, simplemente sigue tirando hasta que no obtenga un 2; no es difícil comprobar que esto da 0 o 1 con la misma probabilidad. Este método también se describe en el enlace que negamos en su respuesta, aunque codificado de manera diferente. Estoy usando random() lugar de rand() ya que tiene una mejor distribución (como lo señala la página man para rand() ).
Si desea obtener valores aleatorios fuera del rango predeterminado [0, RAND_MAX] , entonces tiene que hacer algo complicado. Quizás el más conveniente es definir una función random_extended() que extrae n bits (usando random_at_most() ) y devuelve en [0, 2**n) , y luego aplicar random_at_most() con random_extended() en lugar de random() (y 2**n - 1 en lugar de RAND_MAX ) para extraer un valor aleatorio menor que 2**n , suponiendo que tiene un tipo numérico que puede contener dicho valor. Finalmente, por supuesto, puede obtener valores en [min, max] usando min + random_at_most(max - min) , incluidos los valores negativos.
unsigned int
randr(unsigned int min, unsigned int max)
{
double scaled = (double)rand()/RAND_MAX;
return (max - min +1)*scaled + min;
}
Vea here para otras opciones.