Perché le cifre 1, 2 e 3 appaiono così frequentemente usando la funzione C rand()?

Question

Quello che sto cercando di fare è di generare alcuni numeri casuali (non necessariamente singola cifra) come

29106 
7438 
5646 
4487 
9374 
28671 
92 
13941 
25226 
10076 

e poi contare il numero di cifre ottengo:

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 

Questo è il codice che ho sto 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)); 

} 

Se ho generare un gran numero di numeri casuali (1000000), questo è il risultato che ottengo:

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 

Si noti che 1, 2 e 3 hanno troppi riscontri. Ho provato a farlo più volte e ogni volta ottengo risultati molto simili.

Sto cercando di capire cosa potrebbe causare 1, 2 e 3 ad apparire molto più frequentemente di qualsiasi altra cifra.

---

Prendendo spunto da ciò che Matt Joiner e Pascal Cuoq sottolineato,

ho cambiato il codice per utilizzare

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

e questo è quello che ottengo (risultati analoghi su più piste):

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 

Quale può essere il motivo per cui 0, 1 e 2 sono preferiti?

---

Grazie a tutti. Utilizzando

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

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

ottengo

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 valore da 0 a RAND_MAX. RAND_MAX è impostato su INT_MAX sulla maggior parte delle piattaforme, che può essere 32767 o 2147483647.

Per l'esempio sopra riportato, sembra che RAND_MAX sia 32767. Ciò inserirà una frequenza insolitamente alta di 1, 2 e 3 per la cifra più significativa per i valori da 10000 a 32767. È possibile osservare che, in misura minore, anche i valori fino a 6 e 7 saranno leggermente favoriti.

Answer 2

Sembra legge di Benford - vedi http://en.wikipedia.org/wiki/Benford%27s_law, o in alternativa un non molto buona RNG.

Answer 3

Questo perché si generano numeri compresi tra 0 e RAND_MAX. I numeri generati sono equamente distribuiti (cioè circa la stessa probabilità per ciascun numero), tuttavia, le cifre 1,2,3 si verificano più spesso di altre in questo intervallo. Prova a generare tra 0 e 10, dove ogni cifra si verifica con la stessa probabilità e otterrai una buona distribuzione.

Answer 4

quanto riguarda la questione modificato,

Questo perché le cifre non sono ancora distribuiti in modo uniforme anche se si % 10000. Assumere RAND_MAX == 32767 e rand() è perfettamente uniforme.

Per ogni 10.000 numeri contando da 0, tutte le cifre appariranno in modo uniforme (4.000 ciascuna). Tuttavia, 32.767 non è divisibile per 10.000. Pertanto, questi 2.768 numeri forniranno più primi 0, 1 e 2 per il conteggio finale.

Il contributo esatto di questi 2.768 numeri sono:

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

aggiungendo 12.000 per i primi 30.000 numeri per il conteggio, poi dividere per il numero totale di cifre (4 × 32.768) dovrebbe darvi la distribuzione previsto :

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 

che è vicino a quello che si ottiene.

Se si desidera la distribuzione veramente uniforme cifre, è necessario rifiutare quei 2.768 numeri:

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

Quando si desidera generare valore casuale dalla gamma [0, x), invece di fare rand()%x, si dovrebbe applicare la formula x*((double)rand()/RAND_MAX), che ti fornirà valori casuali ben distribuiti.

Say, RAND_MAX è uguale a 15, quindi rand darà numeri interi da 0 a 15. Quando si utilizza operatore modulo per ottenere numeri casuali da [0, 10), valori [0,5] avrà frequenza superiore [6,9], perché 3 == 3%10 == 13%10.

Answer 6

Se ho capito cosa vuole l'OP (persona che pone la domanda), vogliono fare numeri casuali migliori.

rand() e random(), francamente, non producono numeri casuali molto buoni; entrambi fanno male quando vengono testati contro diehard e dieharder (due pacchetti per testare la qualità dei numeri casuali).

Il twister Mersenne è un popolare generatore di numeri casuali che è buono per praticamente tutto tranne i numeri casuali crittografici; supera tutti i test più difficili (er) con i colori volanti.

Se uno ha bisogno di numeri casuali crittografici (numeri che non possono essere indovinati, anche se qualcuno conosce quale particolare algoritmo crittografico viene usato), ci sono un certo numero di codici di flusso là fuori. Quello che mi piace usare è chiamato RadioGatún [32], e qui è una rappresentazione compatta C di esso:

/*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");}} 

Ci sono anche un sacco di altre veramente buoni generatori di numeri casuali là fuori.