¿"N*(rand()/RAND_MAX)" hace una distribución de números aleatoria sesgada?

random numbers

Question

Me gustaría encontrar una forma no asimilada para obtener números aleatorios en C (aunque a lo sumo lo usaré para valores de 0-20, y más probablemente solo de 0-8). He visto esta fórmula, pero después de ejecutar algunas pruebas no estoy seguro de si está sesgada o no. ¿Alguna ayuda?

Aquí está la función completa utilizada:

int randNum()
{
return 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
}

Lo sembré usando:

unsigned int iseed = (unsigned int)time(NULL);
srand (iseed);

El que se sugiere a continuación se niega a trabajar para mí lo intenté

int greek;
for (j=0; j<50000; j++)
{
greek =rand_lim(5);
printf("%d, " greek);
greek =(int) (NUM * (rand() / (RAND_MAX + 1.0)));
int togo=number[greek];
number[greek]=togo+1;
}

y deja de funcionar y me da el mismo número 50000 veces cuando comento printf.

Answer 1

Sí, está sesgado, a menos que su RAND_MAX sea un múltiplo de 10.

Si tomas los números de 0 a RAND_MAX e intentas dividirlos en 10 pilas, realmente solo tienes tres posibilidades:

1. RAND_MAX es un múltiplo de 10, y las pilas salen incluso.
2. RAND_MAX no es un múltiplo de 10, y las pilas salen desiguales.
3. Primero lo divide en grupos desiguales, pero tira todos los "extras" que lo harían desigual.

Raramente tiene control sobre RAND_MAX, y a menudo es un número primo de todos modos. Eso realmente solo deja 2 y 3 como posibilidades.

La tercera opción se ve más o menos así: [Editar: después de pensarlo un momento, lo he revisado para producir números en el rango 0 ... (límite-1), para que coincida con la forma en que funcionan la mayoría de las cosas en C y C ++. Esto también simplifica el código (un poquito).

int rand_lim(int limit) {
/* return a random number in the range [0..limit)
*/
int divisor = RAND_MAX/limit;
int retval;
do {
retval = rand() / divisor;
} while (retval == limit);
return retval;
}

Para cualquiera que cuestione si este método podría dejar algún sesgo, también escribí una versión bastante diferente, puramente para probar. Este utiliza un generador decididamente no aleatorio con un rango muy limitado, por lo que podemos simplemente iterar a través de cada número en el rango. Se parece a esto:

#include <stdlib.h>
#include <stdio.h>
#define MAX 1009
int next_val() {
// just return consecutive numbers
static int v=0;
return v++;
}
int lim(int limit) {
int divisor = MAX/limit;
int retval;
do {
retval = next_val() / divisor;
} while (retval == limit);
return retval;
}
#define LIMIT 10
int main() {
// we''ll allocate extra space at the end of the array:
int buckets[LIMIT+2] = {0};
int i;
for (i=0; i<MAX; i++)
++buckets[lim(LIMIT)];
// and print one beyond what *should* be generated
for (i=0; i<LIMIT+1; i++)
printf("%2d: %d/n", i, buckets[i]);
}

Entonces, comenzamos con números del 0 al 1009 (1009 es primo, por lo que no será un múltiplo exacto de cualquier rango que elijamos). Entonces, estamos comenzando con 1009 números, y dividiéndolo en 10 cubos. Eso debería dar 100 en cada cubo, y los 9 sobrantes (por así decirlo) son "comidos" por el ciclo do / while. Como está escrito en este momento, asigna e imprime un cubo extra. Cuando lo ejecuto, obtengo exactamente 100 en cada uno de los cubos 0..9 y 0 en el cubo 10. Si hago un comentario sobre el ciclo do / while, veo 100 en cada uno de 0..9 y 9 en el cubo 10 .

Solo para estar seguro, volví a ejecutar la prueba con varios otros números tanto para el rango producido (números primos usados ​​en su mayoría) como para el número de cubos. Hasta ahora, no he podido obtener resultados asimétricos para ningún rango (siempre que el ciclo do / while esté habilitado, por supuesto).

Otro detalle: hay una razón por la que utilicé la división en lugar del resto en este algoritmo. Con una buena (o incluso decente) implementación de rand() es irrelevante, pero cuando fijas números a un rango usando división, mantienes los bits superiores de la entrada. Cuando lo haces con el resto, mantienes los bits más bajos de la entrada. Como ocurre, con un típico generador de números pseudoaleatorios congruente lineal, los bits más bajos tienden a ser menos aleatorios que los bits superiores. Una implementación razonable arrojará una cantidad de los bits menos significativos ya, haciendo que esto sea irrelevante. Por otro lado, hay algunas implementaciones bastante rand de rand alrededor, y con la mayoría de ellas, se obtiene una mejor calidad de salida al usar división en lugar de resto.

También debo señalar que hay generadores que hacen más o menos lo contrario: los bits más bajos son más aleatorios que los bits superiores. Al menos en mi experiencia, estos son bastante poco comunes. Eso con el cual los bits superiores son más aleatorios es considerablemente más común.