PDA

Visualizza la versione completa : Linguaggio C Apparenti anomalie in generazione numeri random


Gandalf73
06-11-2015, 23:28
Carissimi,
mi sono imbattuto in una stranezza che mi ha fatto perdere non poco tempo nella costruzione di un banale programmino per la generazione di numeri casuali interi compresi in un intervallo chiuso [a,b].

Come si sa possono essere ottenuti in due modi:

a) int casuale = (int) (b-a+1)*(rand()/(double)(RAND_MAX+1.0)) + a;

b) int casuale = rand()%(b-a+1) + a;

Ambedue i metodi sono validi ma se b è un divisore di RAND_MAX,la seconda metodologia porterebbe ad una distribuzione statistica non molto uniforme e di conseguenza è preferibile utilizzare la a).
Fin qui tutto ok.
Supposta l'inizializzazione del seme con srand(time(0));
ho lanciato le due righe di codice con entrambe le formulazioni.
Ebbene ad ogni run del programmino la prima forma ha sempre generato lo stesso numero la seconda no (se avessi aspettato un'ora il numero sarebbe uscito diverso).
Mi sono chiesto il perchè andando a piazzare delle stampe per capire dove fosse l'inghippo.
Ebbene il numero generato ad ogni lancio del programma con il primo metodo era ovviamente sempre diverso ma molto simile e la differenza sempre minore del centinaio (lo start della generazione è "quasi" il medesimo se i lanci sono ravvicinati).
Come dire ad ogni lancio il refresh del seme genera numeri di partenza vicini
Dividere quindi tale numero per (RAND_MAX +1.0) porta ad un decimale le cui cifre possono differire solo a partire dalla seconda,terza o quarta cifra decimale. Ecco spiegato il motivo del perchè gli interi in output risultavano uguali essendo interi.
Se invece frapponessi al primo metodo una rand() di "inizializzazione",il problema non si porrebbe e di conseguenza il numero generato nella successiva rand() risulterebbe totalmente "scorrelato" dalla prima, con conseguente risultato diverso ad ogni lancio dell'intero programma stesso (basta utilizzare per l'output il risultato della seconda rand()).
Nel modo b) invece non rilevo nessuna apparente difformità.
In soldoni per intervalli di generazione piccoli con estremo superiore non divisore di RAND_MAX è bene usare il secondo tipo, per altri il primo a meno che si abbia l'accortezza di inizializzare la randomizzazione con una generazione "inutilizzabile" in quanto in caso di run ravvicinati del programma la metodologia di scelta per il seme porta al primo numero del lotto molto simile tra due avvii distinti del software.
Mi chiedo se qualcuno sia giunto alle mia mia stessa analisi e/o si sia imbattuto in identiche problematiche arrivando a conclusioni diverse
Un saluto
A.

ps spero di essere stato abbastanza chiaro nell'esposizione

MItaly
07-11-2015, 00:19
Come dire ad ogni lancio il refresh del seme genera numeri di partenza vicini

Non mi torna per niente. rand() è normalmente implementato con un LCG, che è fatto in modo tale per cui anche seed diversi di molto poco generano numeri estremamente diversi. Posta il programma di prova che esibisce il problema (oltre a nome e versione del compilatore), probabilmente c'è qualche altra gabola.

Gandalf73
07-11-2015, 19:13
Innanzitutto grazie infinite per la risposta.
Spero sia di utilità per molti questo caso che si sta analizzando.



#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void main(void){
int a,b,risultato[8];
srand(time(0));
/* prototipo generatore numeri random INTERI compresi in un intervallo di INTERI */
printf("inserisci estremo a\n");
scanf("%d",&a);
printf("inserisci estremo b\n");
scanf("%d",&b);
/*prima modalità di calcolo*/
risultato= (int) (b-a+1)*(rand()/(double)(RAND_MAX+1.0)) + a;
printf("ecco il risultato con il primo modo %d\n",risultato);
/*seconda modalità*/
printf("ecco il risultato con il secondo modo %d\n",risultato2);
int risultato2 = a + rand()%(b-a+1);
}



Il compilatore usato è il TDM-GCC 4.9.9.2
Come si nota se non si inserisce una rand() di "inizializzazione" il numero generato con la prima modalità,
ad ogni esecuzione del ".exe" esce sempre uguale salvo il rilanciarlo dopo un po di tempo (dopo un'ora per es.).
Mi sono spinto ancora più in là facendo riempire un arrai da 10 elementi.
Ebbene le randomizzazioni in quel caso danno veramente l'idea della casualità.
Tutto ciò provato con gli estremi [4,20].
Da lì..le conclusioni esposte sopra.
A me sembra appunto un problema nella inizializzazione "interna" al compilatore.
A questo punto è divenuta una questione di principio capire dove si annida l'inguacchio.
Un saluto e grazie a quanti volessero cimentarsi nella soluzione.
A.

Gandalf73
08-11-2015, 19:08
Ops scusate per il secondo modo ho inserito la stampa prima del calcolo.
Ovviamente non è per quello che non funziona.
L'ho riprovato un'altra volta...ma niente.va egregiamente solo anteponendo una rand() non utilizzata prima della rand effettiva utile per il calcolo.
Mah...

brancomat
09-11-2015, 09:36
... sui sacri testi ci sono centinaia di generatori random molto robusti e affidabili, e trovi codice e snippet già pronti quasi ovunque...
i generatori dei compilatori, spesso, non sono un granche

MItaly
10-11-2015, 02:08
Dunque, ho spulciato un po' in giro, e apparentemente il problema sta nella CRT Microsoft (che MinGW sfrutta per un po' di roba, tra cui appunto la srand/rand). Per come è implementata la srand nel runtime Microsoft, il primo numero generato da rand() ha una dipendenza molto stretta dal seed; stampando semplicemente il primo valore restituito da rand() in run successive (=> i seed differiscono solo di 1) ottengo


27250
27253
27256
27260
27263

e non siamo i primi (http://stackoverflow.com/questions/6668282/srandtimenull-generating-similar-results) a notare il problema. Dato che il primo metodo rimappa in maniera lineare il range della rand sul range desiderato, questa scarsa casualità del primo estratto si nota anche sul numero che ne derivi (mentre è "nascosta" dal modulo nel secondo metodo).

Ergo, puoi fare due cose:
- scartare il risultato della prima rand(), visto che dalle successive va avanti giusto;
- come suggerisce brancomat, puoi recuperare un altro generatore di numeri casuali; se ti basta un LCG puoi rubacchiare una qualunque implementazione più robusta (già quella di glibc è molto meglio - tra l'altro, ha un RAND_MAX molto più alto e un periodo molto più lungo rispetto a quello della CRT Microsoft), oppure, se hai necessità di numeri casuali "di alta qualità", puoi tirare fuori le armi pesanti e usare, ad esempio, il classico Mersenne Twister (si trovano diverse implementazioni free in giro).

Gandalf73
14-11-2015, 02:55
Mi scuso per il ritardo nella risposta ma spero siano graditi ugualmente i miei ringraziamenti. La prima cosa è che...ci avevo visto giusto!La mia osservazione non era peregrina.Vale a dire le prove che avevo fatto erano corrette.
Per quanto riguarda l'uso,se la rand () che utilizza la CRT "difettosa" verrà usata per riempire un array...il problema non si pone.L'imperfezione arriva solo ed esclusivamente quando si genera un solo numero.
Se vi volete sbizzarrire qui lo si vede palese il "baco".



#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void main(void){
int a,b;
srand(time(0));
/* prototipo generatore numeri random INTERI compresi in un intervallo di INTERI */
printf("inserisci estremo a\n");
scanf("%d",&a);
printf("inserisci estremo b\n");
scanf("%d",&b);
double prova = (double) (RAND_MAX+1.0);
int numero = rand();
printf("ecco il primo numero estratto %d\n",numero);
int ris1= (int) (b-a+1)*(numero/(double)(RAND_MAX+1.0)) + a;
printf("estrazione adattata con il primo rand %d\n",ris1);
int num2 = rand();
printf("ecco il secondo numero estratto %d\n",num2);
int ris2 =(double)(num2/prova)*(b-a+1);
printf("estrazione adattata con il secondo rand %d\n",ris2);
int risultato2= rand()%(b-a+1)+a;
printf("ecco il numero estratto con divisione in modulo %d\n",risultato2);
}


Volevo invece farvi due domande:

1) in ambiente Linux visto che non si usano le CRT (o meglio il Gcc ha altre librerie per il run-time) il problema non dovrebbe presentarsi corretto?
2) avrei un quesito su Virtual Box,in che area lo posso postare?

Grazie ancora a tutti per la pazienza
Un saluto
A.

Loading