rand() et srand()

Version imprimable

02/12/2012, 16h49
Thosbk

rand() et srand()
Bonjour tout le monde,

j'ai deux petites questions dont je ne trouve pas la réponse concernant la fonction rand() et srand().

J'ai bien compris que rand() est une suite pseudo aléatoire, et srand() permet de définir où le programme commence dans la séquence pseudo-alétoire. Mais il me reste deux petits points pas très clairs ... et j'aimerais vos lumières pour m'aider :-)

1) Si le nombre d'appelle à la fonction rand() dépasse RAND_MAX, il boucle et revient au début de la séquence ?

2) La séquence pseudo aléatoire dépend-elle de la machine, architecture, ou compilateur ?

3) Concernant la graine de départ de la séquence rand(). Si je regarde ceci:
Code:

1 2 3 4 srand(1); for (int j=1; j<4;j++) printf("random %d = %d\n", j, rand());
alors j'obtiens :
random 1 = 1804289383
random 2 = 846930886
random 3 = 1681692777

Si je prends le même code en mettant srand(2) à la place de srand(1), et en n'affichant que les deux premiers résultats, soit
Code:

1 2 3 4 srand(2); for (int j=2; j<4;j++) printf("random %d = %d\n", j, rand());
j'obtiens alors

random 2 = 1362961854
random 3 = 8891098

Je pensais pourtant obtenir les deux mêmes résultats qu'avec srand(1), comme si la suite partait du deuxième nombre pseudo-aléatoire de la séquence. C'est-à-dire :
random 2 = 846930886
random 3 = 1681692777

Mais ce n'est pas le cas, du coup je me posais une question très naïve. Je dois lancer des simulations de Monte Carlo en multi processus avec MPI/OpenMP. Plutôt que de choisir des graines dépendant du temps et du rand du processus, suffirait-il de choisir une graine du genre srand(MPI_rank) ? Je sens bien que c'est faux et ça sent l'entourloupe à plein nez, mais ça m'interroge quand même. :)

Merci beaucoup pour vos réponses et bonne fin de week end !
02/12/2012, 17h45
koala01
Citation:

Envoyé par Thosbk

1) Si le nombre d'appelle à la fonction rand() dépasse RAND_MAX, il boucle et revient au début de la séquence ?

En fait, on ne revient pas au début de la séquence, simplement, plus tu fait appel à rand, plus tu as de probabilité d'obtenir une valeur qui est déjà sortie, selon le paradoxe des anniversaires

Il n'est bien sur pas exclu que tu finisse par voir apparaitre une suite répétée si tu dépasse largement RAND_MAX appels à rand, cela dépendra essentiellement de l'algorithme implémenté par rand et surtout de la plage de valeurs que tu attends (le modulo de ton maximum admis fera beaucoup plus vite apparaitre une "suite logique" ;) );)

Citation:

2) La séquence pseudo aléatoire dépend-elle de la machine, architecture, ou compilateur ?

En fait cela dépend de l'algorithme implémenté par rand, et donc essentiellement du compilateur (en fait, de l'équipe qui a mis le compilateur au point), et, dans une autre mesure, de la plage de valeurs représentables par le type renvoyé par rand ;)
Citation:
3) Concernant la graine de départ de la séquence rand(). Si je regarde ceci:

Code:

1 2 3 4 srand(1); for (int j=1; j<4;j++) printf("random %d = %d\n", j, rand());

alors j'obtiens :
random 1 = 1804289383
random 2 = 846930886
random 3 = 1681692777

Si je prends le même code en mettant srand(2) à la place de srand(1), et en n'affichant que les deux premiers résultats, soit

Code:

1 2 3 4 srand(2); for (int j=2; j<4;j++) printf("random %d = %d\n", j, rand());

j'obtiens alors

random 2 = 1362961854
random 3 = 8891098

Je pensais pourtant obtenir les deux mêmes résultats qu'avec srand(1), comme si la suite partait du deuxième nombre pseudo-aléatoire de la séquence. C'est-à-dire :
random 2 = 846930886
random 3 = 1681692777

Mais ce n'est pas le cas, du coup je me posais une question très naïve. Je dois lancer des simulations de Monte Carlo en multi processus avec MPI/OpenMP. Plutôt que de choisir des graines dépendant du temps et du rand du processus, suffirait-il de choisir une graine du genre srand(MPI_rank) ? Je sens bien que c'est faux et ça sent l'entourloupe à plein nez, mais ça m'interroge quand même. :)

Merci beaucoup pour vos réponses et bonne fin de week end !
En fait, rand implémente un algorithme clair et précis.

Comme tout algorithme, le propre de celui qui est implémenté par rand, c'est la reproductivité : si tu le place dans une situation clairement définie (en utilisant toujours la même valeur de graine en l'occurence), tu obtiendras toujours un résultat équivalent.

Il n'y a que si tu le place dans une situation différente (en changeant la valeur de la graine en l'occurrence) que tu obtiendras un résultat différent ;)

C'est la raison pour laquelle, si tu veux que chaque exécution du code soit sensiblement différente de la précédente, que tu te basera sur la seule chose qui a de grandes chances d'être différente d'une exécution à l'autre : le temps système ;)

Ceci dit, il faut avouer que ce n'est pas tout à fait vrai, car tu reste limité par la plage de valeurs représentables par le type utilisé comme graine, mais étant donné le temps limité pendant lequel tu obtiendras une valeur identique (une seconde), et la grande plage de valeurs représentables, il faudrait soit beaucoup de chance (assez pour t'inciter à jouer à l'euromillion :D) soit beaucoup d'essais pour avoir une chance de voir apparaitre une suite identique à une de celles qui sont déjà passées ;)
02/12/2012, 18h04
Thosbk

Hello !

Merci beaucoup pour ta réponse !! Je vois un peu plus clair maintenant (et je ne connaissais pas le paradoxe des anniversaires :)).

En fait, je dois lancer un grand nombre de simulations avec une donnée initiale aléatoire à chaque lancement. En séquentiel, il "suffirait" de lancer rand() à chaque itération, sans trop se soucier de la graine. Mais j'aimerais le lancer en parallèle et je m'interrogeais du coup sur cette graine et la possibilité que (au moins) deux processus aient exactement la même suite aléatoire... Avec ce que tu me dis, je pense que je suis tranquille en utilisant le temps et le rang du processus.

Merci encore et bonne soirée !
02/12/2012, 21h28
koala01

Ceci dit, le paradoxe des anniversaires indique "simplement" qu'il faut sans doute beaucoup moins de "tirages" que ce que l'on crois de prime abord pour avoir de grandes chances d'avoir deux fois une valeur similaire (avec 28 personne dans la même pièce, tu a une probabilité très élevée qu'il y ait au moins deux personne ayant la meme date de naissance, alors qu'il y a 365 jours par an ;))

Cela ne veut absolument pas dire que tu obtiendras la même suite au niveau des tirages hein :question:

Ceci dit, comme tes essais l'ont sans doute mis en évidence, l'algorithme utilisé par rand s'arrange normalement pour assurer une très grande variation des séquences de tirage avec une petite variation de la graine (un peu comme l'algorithme MD5 s'arrange pour assurer une grande variation de la clé si tu viens à modifier un seul caractère de ce dont tu veux calculer la somme ;))

Par contre, le problème surviendra si tu veux placer une limite dans fourchette de valeurs que tu souhaite obtenir au final.

En effet, plus tu réduiras cette fourchette de valeurs, plus tu auras une chance d'obtenir rapidement une valeur qui a déjà été tirée (de par le paradoxe des anniversaires, justement ;)), avec, en prime, d'éventuels soucis en terme de distribution du tirage (certaines valeurs ayant d'avantage de chances que d'autres d'être tirée, du fait même de la diminution de la fourchette autorisée).

Mais donc, tu peux effectivement être rassuré : si le programme principal prend la valeur time et qu'il fournit comme graine cette valeur + N (ou N serait un numéro d'ordre de processus, tout simplement incrémenté), il faudrait déjà énormément de processus pour en trouver deux qui baseraient leur simulation sur des valeurs identiques ;)
02/12/2012, 23h03
Thosbk
Merci beaucoup !

Je vois bien plus clair, juste pour être au clair : la séquence pseudo-aléatoire rand(), possède plusieurs même résultat ? En particulier, si on appelle u_n cette séquence de nombre donné par rand(), alors il existe (au moins) deux entiers m et m' tels que u_m = u_m', mais sans pour autant que u_{m+1} = u_{m'+1} ?

Et il reste un point que je ne comprends en fait toujours pas trop. C'est comment fonctionne la graine, même si - si j'ai bien compris - tout cela dépend du compilateur et de l'implémentation de rand(). En fait, faire
Code:

1 2 3 srand(1); rand(); cout << rand();
ne donnera pas le même résultat que
Code:

1 2 srand(2); cout << rand();
même si les bouts de code sont mis l'un à la suite de l'autre dans le même programme... Je pensais avoir compris pourquoi mais en fait non. Je dois surement voir la fonction rand() de la mauvaise manière :)
Je l'imagine comme une suite mathématiques déterministe u_n = f(n) où chaque appelle à rand() incrémente le compteur "n" de 1 ...
03/12/2012, 09h22
transgohan

Vois le plutôt comme si pour chaque valeur différente passée à srand tu définissais une suite différente. ;)
03/12/2012, 09h26
MicBeastKiller

Si tu considères la suite donnée par récurrence :
u(n) = u(n-1) + 2; pour n >= 1.
Pour la graine u(0) = 1, tu obtiens u(1) = 3, u(2) = 5, ...
Pour la graine u(0) = 2, tu obtiens u(1) = 4, u(2) = 6, ...
Certes, c'est très simpliste et la fonction rand est beaucoup plus compliquée *, mais le principe est là.
* dans le sens où avec la même graine, tu auras peu (pas) de chance d'obtenir la même suite.
03/12/2012, 09h34
Thosbk

Oh ok !! Merci à tous et à toutes pour vos explications !!!