¿Por qué los dígitos 1, 2 y 3 aparecen con tanta frecuencia usando la función C rand()?

Question

Lo que estoy tratando de hacer es generar algunos números aleatorios (no necesariamente de un solo dígito) como

29106 
7438 
5646 
4487 
9374 
28671 
92 
13941 
25226 
10076 

y luego contar el número de dígitos consigo:

count[0] =  3 Percentage = 6.82 
count[1] =  5 Percentage = 11.36 
count[2] =  6 Percentage = 13.64 
count[3] =  3 Percentage = 6.82 
count[4] =  6 Percentage = 13.64 
count[5] =  2 Percentage = 4.55 
count[6] =  7 Percentage = 15.91 
count[7] =  5 Percentage = 11.36 
count[8] =  3 Percentage = 6.82 
count[9] =  4 Percentage = 9.09 

Este es el código que estoy usando:

#include <stdio.h> 
#include <time.h> 
#include <stdlib.h> 

int main() { 

    int i; 
    srand(time(NULL)); 
    FILE* fp = fopen("random.txt", "w");  
    // for(i = 0; i < 10; i++) 
    for(i = 0; i < 1000000; i++) 
     fprintf(fp, "%d\n", rand()); 
    fclose(fp); 

    int dummy; 
    long count[10] = {0,0,0,0,0,0,0,0,0,0}; 
    fp = fopen("random.txt", "r"); 
    while(!feof(fp)) { 
     fscanf(fp, "%1d", &dummy); 
     count[dummy]++;     
    } 
    fclose(fp); 

    long sum = 0; 
    for(i = 0; i < 10; i++) 
     sum += count[i]; 

    for(i = 0; i < 10; i++) 
     printf("count[%d] = %7ld Percentage = %5.2f\n", 
      i, count[i], ((float)(100 * count[i])/sum)); 

} 

Si genero una gran cantidad de números aleatorios (1000000), esto es el resultado me sale:

count[0] = 387432 Percentage = 8.31 
count[1] = 728339 Percentage = 15.63 
count[2] = 720880 Percentage = 15.47 
count[3] = 475982 Percentage = 10.21 
count[4] = 392678 Percentage = 8.43 
count[5] = 392683 Percentage = 8.43 
count[6] = 392456 Percentage = 8.42 
count[7] = 391599 Percentage = 8.40 
count[8] = 388795 Percentage = 8.34 
count[9] = 389501 Percentage = 8.36 

Tenga en cuenta que 1, 2 y 3 tienen demasiados golpes. He intentado ejecutar esto varias veces y cada vez obtengo resultados muy similares.

Estoy tratando de entender qué podría causar que 1, 2 y 3 aparezcan con mucha más frecuencia que cualquier otro dígito.

---

Tomando indicio de lo que Matt Joiner y Pascal Cuoq señalaron,

he cambiado el código para utilizar

for(i = 0; i < 1000000; i++) 
    fprintf(fp, "%04d\n", rand() % 10000); 
// pretty prints 0 
// generates numbers in range 0000 to 9999 

y esto es lo que me pasa (resultados similares en múltiples carreras):

count[0] = 422947 Percentage = 10.57 
count[1] = 423222 Percentage = 10.58 
count[2] = 414699 Percentage = 10.37 
count[3] = 391604 Percentage = 9.79 
count[4] = 392640 Percentage = 9.82 
count[5] = 392928 Percentage = 9.82 
count[6] = 392737 Percentage = 9.82 
count[7] = 392634 Percentage = 9.82 
count[8] = 388238 Percentage = 9.71 
count[9] = 388352 Percentage = 9.71 

¿Cuál es la razón por la que 0, 1 y 2 son los preferidos?

---

Gracias a todos. Usando

int rand2(){ 
    int num = rand(); 
    return (num > 30000? rand2():num);  
} 

    fprintf(fp, "%04d\n", rand2() % 10000); 

consigo

count[0] = 399629 Percentage = 9.99 
count[1] = 399897 Percentage = 10.00 
count[2] = 400162 Percentage = 10.00 
count[3] = 400412 Percentage = 10.01 
count[4] = 399863 Percentage = 10.00 
count[5] = 400756 Percentage = 10.02 
count[6] = 399980 Percentage = 10.00 
count[7] = 400055 Percentage = 10.00 
count[8] = 399143 Percentage = 9.98 
count[9] = 400104 Percentage = 10.00 

Answer 1

rand() genera un valor entre 0 y RAND_MAX. RAND_MAX se establece en INT_MAX en la mayoría de las plataformas, que pueden ser 32767 o 2147483647.

Para su ejemplo anterior, parece que RAND_MAX es 32767. Esto colocará una frecuencia inusualmente alta de 1, 2 y 3 para el dígito más significativo para los valores de 10000 a 32767. Puede observar que, en menor grado, los valores hasta 6 y 7 también serán ligeramente favorecidos.

Answer 2

Parece que la Ley de Benford - ver http://en.wikipedia.org/wiki/Benford%27s_law, o alternativamente un generador de números aleatorios no es muy bueno.

Answer 3

Eso es porque usted genera números entre 0 y RAND_MAX. Los números generados están distribuidos uniformemente (es decir, aproximadamente la misma probabilidad para cada número), sin embargo, los dígitos 1,2,3 ocurren más a menudo que otros en este rango. Intente generar entre 0 y 10, donde cada dígito aparece con la misma probabilidad y obtendrá una buena distribución.

Answer 4

En cuanto a la cuestión editado,

Esto se debe a que las cifras aún no están distribuidos de manera uniforme incluso si % 10000. Supongamos RAND_MAX == 32767, y rand() es perfectamente uniforme.

Por cada 10,000 números contados desde 0, todos los dígitos aparecerán uniformemente (4,000 cada uno). Sin embargo, 32.767 no es divisible por 10.000. Por lo tanto, estos números 2,768 proporcionarán más líderes 0, 1 y 2 al recuento final.

La contribución exacta de estos 2.768 números son:

digits count 
0  1857 
1  1857 
2  1625 
3  857 
4  857 
5  857 
6  855 
7  815 
8  746 
9  746 

añadiendo 12.000 para los 30.000 números iniciales para el recuento, y se divide por el número total de dígitos (4 × 32.768) le proporcionará la distribución esperada :

number probability (%) 
0  10.5721 
1  10.5721 
2  10.3951 
3  9.80911 
4  9.80911 
5  9.80911 
6  9.80759 
7  9.77707 
8  9.72443 
9  9.72443 

que está cerca de lo que obtienes.

Si desea distribución verdaderamente uniforme dígitos, es necesario rechazan esos 2.768 números:

int rand_4digits() { 
    const int RAND_MAX_4_DIGITS = RAND_MAX - RAND_MAX % 10000; 
    int res; 
    do { 
    res = rand(); 
    } while (res >= RAND_MAX_4_DIGITS); 
    return res % 10000; 
} 

Answer 5

Cuando se desea generar valor aleatorio de la gama [0, x), en lugar de hacer rand()%x, se debe aplicar la fórmula x*((double)rand()/RAND_MAX), que le dará valores aleatorios muy bien distribuidos.

Say, RAND_MAX es igual a 15, por lo rand le dará números enteros de 0 a 15. Cuando se utiliza el operador de módulo para obtener números aleatorios de [0, 10), los valores [0,5] tendrá una frecuencia mayor que [6,9], porque 3 == 3%10 == 13%10.

Answer 6

Si entiendo lo que quiere el OP (persona que hace la pregunta), quieren hacer mejores números al azar.

rand() y al azar(), francamente, no hacen números aleatorios muy buenos; a los dos les va mal cuando se prueban contra diehard y dieharder (dos paquetes para probar la calidad de los números aleatorios).

El Twister de Mersenne es un popular generador de números aleatorios que es bueno para casi todo, excepto para números aleatorios cripto-fuertes; pasa todas las pruebas de diehard (er) con gran éxito.

Si se necesitan números aleatorios criptográficos (números que no se pueden adivinar, incluso si alguien sabe qué algoritmo cripto-fuerte particular se está usando), hay una cantidad de cifrados de flujo. El que más me gusta usar se llama RadioGatún [32], y aquí es una representación compacta C de la misma:

/*Placed in the public domain by Sam Trenholme*/ 
#include <stdint.h> 
#include <stdio.h> 
#define p uint32_t 
#define f(a) for(c=0;c<a;c++) 
#define n f(3){b[c*13]^=s[c];a[16+c]^=s[c];}k(a,b 
k(p *a,p *b){p A[19],x,y,r,q[3],c,i;f(3){q[c]=b[c 
*13+12];}for(i=12;i;i--){f(3){b[c*13+i]=b[c*13+i- 
1];}}f(3){b[c*13]=q[c];}f(12){i=c+1+((c%3)*13);b[ 
i]^=a[c+1];}f(19){y=(c*7)%19;r=((c*c+c)/2)%32;x=a 
[y]^(a[(y+1)%19]|(~a[(y+2)%19]));A[c]=(x>>r)|(x<< 
(32-r));}f(19){a[c]=A[c]^A[(c+1)%19]^A[(c+4)%19]; 
}a[0]^=1;f(3){a[c+13]^=q[c];}}l(p *a,p *b,char *v 
){p s[3],q,c,r,x,d=0;for(;;){f(3){s[c]=0;}for(r=0 
;r<3;r++){for(q=0;q<4;q++){if(!(x=*v&255)){d=x=1; 
}v++;s[r]|=x<<(q*8);if(d){n);return;}}}n);}}main(
int j,char **h){p a[39],b[39],c,e,g;if(j==2){f(39 
){a[c]=b[c]=0;}l(a,b,h[1]);f(16){k(a,b);}f(4){k(a 
,b);for(j=1;j<3;++j){g=a[j];for(e=4;e;e--){printf 
("%02x",g&255);g>>=8;}}}printf("\n");}} 

También hay un montón de otros buenos generadores de números aleatorios que hay.