rand() et srand()

Bonjour,

L'autre jour, j'ai eu un petit soucis avec ces deux fonctions.
En effet, il me fallait un nombre aléatoire compris entre 0 et 4 (pour un bête test, pas dans un gros programme donc).
J'ai donc un code du style :

Code:

---

1 2	srand(time(NULL)); int i = 4*rand()/((float)RAND_MAX);

---

... et je me retrouve toujours avec la même valeur de i !
Si par contre j'écris :

Code:

---

1 2 3 4 5

srand(time(NULL)); for (int i = 0; i < 20; ++i) { cout << (int)(4*rand()/((float)RAND_MAX)) << endl; }

---

... j'ai toujours le même nombre en premier, mais les autres changent d'une exécution à l'autre.

Si j'affiche juste rand() :

Code:

---

1 2 3

srand(time(NULL)); cout << rand() << endl return 0;

---

... ça me donne : 14010, 14039, 14066, ... Pas si aléatoire que ça :?

Je ne sais pas exactement comment fonctionnent rand() et srand(), mais je crois que srand() définit la première valeur de rand(), qui sert ensuite à calculer la suivante, et ainsi de suite.
J'aurai cru que la valeur donnée à srand() était un peu comme un indice dans un tableau de nombre aléatoires, mais il semblerai qu'il y ait une relation linéaire entre la valeur donnée à srand() et la première valeur de rand()...

C'est intentionnel ? (je ne trouve pas ça très malin, m'enfin il doit y avoir une raison)
Quelle valeur je devrais donner à srand() pour éviter ça ?

Merci d'avance pour vos conseils.

Edit : j'utilise gcc.

Ils sont dans la même fonction srand() et rand()? Si oui alors enléve srand(). Il ne doit être appelé qu'une fois dans le programme car il permet d'initialiser la graine du générateur de nombre pseudo aléatoire qu'est rand().

Pour plus de détail voir les entrées correspondantes dans la faq. (je crois que c'est dans la faq C)

Non non, ce n'est pas le problème. Essaye :

Code:

---

1 2 3 4 5 6

int main() { srand(time(NULL)); cout << rand() << endl; return 0; }

---

Même en attendant une ou deux secondes entre deux exécutions, on retrouve presque le même nombre.

Edit : après quelques tests, on vois que, si on a appelé srand(i), le premier rand() vaut (presque) : round(3.25*i)+38.

J'ai aussi la même chose :calim2:

Ce qu'il reste à faire, c'est de ne pas prendre en compte la première valeur donnée par rand()... ou alors, vu que c'est seulement entre 1 et 4, tu peux utiliser le modulo:

Code:

---

1 2 3 4 5

srand(time(NULL)); for (int i = 0; i < 20; ++i) { cout << (rand()%4)+1 << endl; }

---

Là tu n'aurais pas les mêmes valeurs de i pour deux exécutions successives (contrairement à la division)

C'est normal puisque tu relances le programme presque de suite la graine à peu changer. Quel programme se relancerait comme ça à 1 secondes d'intervalles ?

Citation:

---

Envoyé par Goten

C'est normal puisque tu relances le programme presque de suite la graine à peu changer. Quel programme se relancerait comme ça à 1 secondes d'intervalles ?

---

La graine change, d'accord, mais ce qui est étonnant c'est que la première valeur donnée par rand() est cette graine et non pas un nombre aléatoire généré à partir de la graine.

Citation:

---

Envoyé par Goten

Quel programme se relancerait comme ça à 1 secondes d'intervalles ?

---

Le mien :aie:
C'est juste un programme de test, mais ça reste embêtant...

@Dreambeliever : Oui, avec le modulo c'est nettement mieu :ccool:

Qu'en sait tu que c'est la graine? Moi j'en est aucune idée. (en fait je suis même sur que c'est pas la graine).


De toute façon si tu as besoin de générateur plus poussé tourne toi vers boost::random.

Citation:

---

Envoyé par Goten

Qu'en sait tu que c'est la graine? Moi j'en est aucune idée. (en fait je suis même sur que c'est pas la graine).

---

Bah alors il y a un gros problème: avec deux graines légèrement différentes, on obtient deux nombres aléatoires légèrement différents?

voilà un test:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <iostream> #include "windows.h"   using namespace std;   int main() { for (int i = 0; i < 5; i++) {   srand(time(NULL)); cout << rand() << endl; Sleep(1000); }   return 0; }

---

Citation:

---

1823
1826
1829
1832
1836

---

Si le chiffre ne correspond pas à la graine modulo quelque chose (modulo RAND_MAX?), je ne vois pas comment expliquer des valeurs si rapprochées?

Citation:

---

Envoyé par Kalith

Non non, ce n'est pas le problème. Essaye :

Code:

---

1 2 3 4 5 6

int main() { srand(time(NULL)); cout << rand() << endl; return 0; }

---

Même en attendant une ou deux secondes entre deux exécutions, on retrouve presque le même nombre.

---

Déjà, rand() renvoie un nombre PSEUDO-aléatoire... En initialisant avec la même valeur, tu retrouveras la même suite de chiffres (ne PAS tenter de l'utiliser en cryptographie, c'est très mauvais, cf. littérature dédiée).

De plus, "time" renvoie un nombre de SECONDES depuis le 01/01/1970 : il est donc tout à fait normal que tu aie des valeurs "proches" sur deux lancements consécutifs... Essaie plutôt d'initialiser avec le champ microsecondes de "gettimeofday" (Unix), ou de "GetTickCount" (Windows).

Sinon, voici un lien pour implémenter "gettimeofday" sur Windows, au besoin.
Dans l'autre sens, un autre lien pour implémenter "GetTickCount" sur Linux... :mrgreen:

Salut,
Effectivement, on aurait pu espérer que le générateur aie une plus grande sensibilité à la graine; en gros que le delta entre deux graines successives provoquent des écarts plus importants dans les valeur générées.
Si tu veux vraiment quelque chose d'aléatoire, alors tournes-toi vers de bibliothèques spécialisées. Et, comme le dit justement Goten, Boost.Random en est une : un tutoriel est d'ailleurs disponible sur le site.

[EDIT] : comme mentionné plus haut, je te conseille aussi de faire un petit tour sur la FAQ C dans la partie consacrée à rand/srand.

Citation:

---

Envoyé par Dreambeliever

Bah alors il y a un gros problème: avec deux graines légèrement différentes, on obtient deux nombres aléatoires légèrement différents?

voilà un test:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <iostream> #include "windows.h"   using namespace std;   int main() { for (int i = 0; i < 5; i++) {   srand(time(NULL)); cout << rand() << endl; Sleep(1000); }   return 0; }

---

Si le chiffre ne correspond pas à la graine modulo quelque chose (modulo RAND_MAX?), je ne vois pas comment expliquer des valeurs si rapprochées?

---

Ce que j'infirmais c'est que tu disais que c'est la valeur de la graine qu'on sortait dans le premier rand. Et non c'est la valeur ayant subit plusieurs opérations. (ça dépend de l'implémentation dans ton compilo).
Si oui c'est normal comme expliqué plus haut, relancé plusieurs fois le programme avec des intervalles très court donnera des nombres très proche. Mais je répéte qui a besoin d'un programme qui se relance toute les x secondes?

Ca me choque quand même...

En tout cas j'aurais appris qu'il vaut mieux commencer par écarter la première valeur de rand() générée, ce que je ne savais pas :ccool:

Citation:

---

Envoyé par Goten

Ce que j'infirmais c'est que tu disais que c'est la valeur de la graine qu'on sortait dans le premier rand.

---

D'où l'importance d'initialiser la génération avec une valeur elle-même quasi-aléatoire, via l'utilisation de timers à haute résolution... Et non pas l'exemple classique avec "time" qui devrait valoir le bûcher à tous ceux qui l'utilisent !!

Pour ma part, sur Windows, j'utilise systématiquement QueryPerformanceCounter (résolution de l'ordre de la nanoseconde en général) pour initialiser mes séquences aléatoires... Voire carrément en guise de générateur aléatoire, après application d'un modulo ! :mrgreen:

Mac LAK : Si tu veux du gros aléatoire, utilise carrément CryptGenRandom()...

Ou bien rand_s() sous Visual 2005, qui wrappe tout ça.

Citation:

---

Envoyé par Médinoc

Mac LAK : Si tu veux du gros aléatoire, utilise carrément CryptGenRandom()...

---

C'est plutôt du "petit aléatoire" que je veux en général, d'où l'utilisation du QueryPerformanceCounter modulo N : je veux surtout avoir des valeurs "aléatoires", mais rapidement avec le moins d'overhead possible (génération de valeurs de test habituellement). Je fais donc en général mon modulo sur une puissance de deux via un masque binaire... :mouarf:

Citation:

---

Envoyé par Médinoc

Ou bien rand_s() sous Visual 2005, qui wrappe tout ça.

---

Plutôt fan de Delphi, à titre perso... :mrgreen:

Citation:

---

Envoyé par 3DArchi

Effectivement, on aurait pu espérer que le générateur aie une plus grande sensibilité à la graine; en gros que le delta entre deux graines successives provoquent des écarts plus importants dans les valeur générées.

---

En fait, c'est le cas... à partir du troisième ou du quatrième appel à rand() (et même dans des librairies compliquées d'ailleurs). En général, il est toujours bon, (surtout si on utilise rand() sur plusieurs seed différentes), de l'initialiser avec faire plusieurs appels avant d'en utiliser les résultats, certaines implémentations de la librairie C le font.

Maintenant, ce n'est pas la bonne façon de faire. Les générateurs de nombres au hasard garantissent un certain niveau de "hasard" entre leurs appels successifs, mais rien du tout sur les corrélations entre deux séries distinctes. En fait deux séries distinctes issues d'un même générateur produiront les mêmes séries, mais avec un point de départ différent...

Dans le cas précis, le problème a deux origines:

1-l'implémentation de rand() selon gcc renvoie apparemment la racine passée à srand() lors du premier appel. C'est pas malin, mais il suffit de le savoir...

2- les racines passées n'étaient pas aléatoires du tout. Si je passe ma date de naissance, ca ne va pas marcher non plus, mais ce ne sera pas la faute de rand()

Francois

Citation:

---

Envoyé par fcharton

En fait, c'est le cas... à partir du troisième ou du quatrième appel à rand() (et même dans des librairies compliquées d'ailleurs).

---

On aurait pu espérer avoir une dispersion plus forte dès le premier tirage?

Citation:

---

Envoyé par fcharton

En général, il est toujours bon, si on utilise rand() dans un même programme, et, sur plusieurs seed différentes, de faire plusieurs appels à rand() avant d'en utiliser les résultats.

---

Intéressant. En fait, dans les projets où j'ai eu besoin d'aléatoire, celui-ci était toujours généré par du hardware avec tout un tas de traitement pour vérifier les propriétés du nombre tiré. En fait, je n'ai jamais vu rand utilisé dans un projet pro.

Mais dans un projet où l'aléatoire doit être reproductible, il faut un algorithme pseudo-aléatoire...

Typiquement, dans ces cas là, j'utilise time() (ou plus précis) pour obtenir la graine si elle n'est pas passée en paramètre, j'affiche ou loggue la graine, puis j'utilise rand().
Peut s'avérer très utile.

Citation:

---

Envoyé par 3DArchi

En fait, je n'ai jamais vu rand utilisé dans un projet pro.

---

Je l'ai souvent vu utiliser dans ma branche (traitement de données), quand on doit "mélanger" des enregistrements. Par exemple, des données d'enquête sont souvent présentées selon un ordre pas aléatoire (en fonction des enquêteurs qui les ont effectués, ou des sous échantillons qui constituent l'étude, ou de leur date de collecte). Pour éviter de "perpetuer" ces biais éventuels on peut vouloir mélanger les données, et rand(), rapide et toujours disponible, est un bon candidat.

Autre cas, des applis où l'on a besoin de vitesse plus que d'alea "pur". Des algorithmes de recherche, comme les algos génétiques, sont souvent de gros consommateurs de tirages au sort, mais où la parfaite uniformité du générateur n'a aucune importance. Les générateurs congruentiels (en fait, des formes plus simples que rand() même sont souvent des choix raisonnables, en raison de leur vitesse d'exécution.

En traitement de données, le pseudo aléatoire présente un autre avantage : à seed égale, le programme est parfaitement déterministe. C'est très important pour débuguer, ou pour n'avoir pas à expliquer au client pourquoi le même programme rend des résultats lègèrements différents d'une fois sur l'autre (c'est généralement assez cocasse...).

Ca dépend carrément du sujet, quoi...

Francois

Citation:

---

Envoyé par 3DArchi

Salut,
Effectivement, on aurait pu espérer que le générateur aie une plus grande sensibilité à la graine; en gros que le delta entre deux graines successives provoquent des écarts plus importants dans les valeur générées.

---

Ouaip, c'est exactement ce que je pensais.

Citation:

---

Envoyé par 3DArchi

Si tu veux vraiment quelque chose d'aléatoire...

---

He bien, que ça soit pseudo aléatoire ne me dérange pas tant que ça. Je code un jeu en ce moment : il me faut une part d'aléatoire, mais rien qui nécessite de faire intervenir l'artillerie lourde :)

Non, je vais simplement me souvenir de faire appel à rand() 4 ou 5 fois histoire d'être sûr (quitte à enfoncer le clou et utiliser un timer haute résolution pour srand()).

Merci en tout cas pour vos réponses !

De toute façon avoir des nombres réellement aléatoire demande de faire appel à des valeurs physique et donc à des périphériques dédiés ;).

Mais oui pour un jeux pas besoin de trop ce casser la tête, c'est pas pour la sécurité ni rien.

Citation:

---

Envoyé par Mac LAK

D'où l'importance d'initialiser la génération avec une valeur elle-même quasi-aléatoire, via l'utilisation de timers à haute résolution... Et non pas l'exemple classique avec "time" qui devrait valoir le bûcher à tous ceux qui l'utilisent !!

---

Ca dépends surtout de ce que tu as besoin : il y a de nombreux où l'initialisation via time(NULL) est amplement suffisante, d'autre où il faut passer par des éléments moins prévisible (typiquement le nombre de ticks ou une durée en nanoseconde), d'autre où il faut passer par des mécanismes encore plus complexe (hardware spécialisé, etc.) et même parfois on utilise une valeur fixe.

Il n'y a pas de bonne méthode dans l'absolu, juste des méthodes qui conviennent plus ou moins bien à un cas de figure donnée.

Citation:

---

Envoyé par 3DArchi

On aurait pu espérer avoir une dispersion plus forte dès le premier tirage?

---

Avec la plupart des implémentations de rand(), non, en fait...

Je ne suis pas certain si le standard le dit (mais en tout cas il le suggère à titre d'exemple), rand() est implémenté comme un générateur à congruences linéaires. A la base, les valeurs successives du générateur sont données, à partir de la racine, par une formule du type

x_n=a x_n-1 + b (mod c)

où c est typiquement une puissance de 2 moins 1 (le modulo est facile à calculer, et une puissance de 2 c'est pas bien du tout, parce les bits de poids faible sont alors périodiques de période très basse), et a et b sont choisis de manière à faire que le générateur parcoure toute la période (Knuth donne les détails, qui sont très intéressants).

Si l'on se donne trois générateurs, G0,G1,G2, initialisés par s, s+1 et s+2, les premières itérations vont donc être (modulo c)

s / s+1 / s+2
as+b / as+b +a / as+b+2a
a(as+b)+b / a(as+b)+b + a^2 / a(as+b)+b + 2a^2
...

comme tu peux le voir, à la première itération, les séries sont à 1 de distance, à la seconde, à a de distance, à la troisièème à a^2 et ainsi de suite.

En fait, la distance entre les séries sera toujours constante (G2(n)-G1(n)=G1(n)-G0(n) pour tout n), mais cela se verra de moins en moins (à cause du modulo)... (mais on en déduit facilement comment casser un système de cryptage fondé sur de telles méthodes...)

Donc, si on peut utiliser ce type de générateur pour du "petit hasard" (c'est à dire presque partout en fait), il ne faut utiliser qu'un générateur à la fois.

Francois

Citation:

---

Envoyé par gl

Ca dépends surtout de ce que tu as besoin : il y a de nombreux où l'initialisation via time(NULL) est amplement suffisante, d'autre où il faut passer par des éléments moins prévisible (typiquement le nombre de ticks ou une durée en nanoseconde), d'autre où il faut passer par des mécanismes encore plus complexe (hardware spécialisé, etc.) et même parfois on utilise une valeur fixe.

---

Le but est en général de générer un jeu de test, "aléatoire" mais sauvegardé pour pouvoir être rejoué (notamment s'il lève un bug !! :mrgreen). Au pire, je pourrais sauvegarder la valeur d'initialisation, donc.
L'autre cas est un générateur à peu près aléatoire censé simuler un environnement : dans ce cas, j'ai besoin au contraire de choses non-reproductibles et complètement imprévisibles afin de tester la robustesse et/ou les cas "rares" auxquels on n'aurait pas pensé "à la main".

Citation:

---

Envoyé par gl

Il n'y a pas de bonne méthode dans l'absolu, juste des méthodes qui conviennent plus ou moins bien à un cas de figure donnée.

---

La méthode que je donne est une des rares à ne pas être dépendante de l'implémentation de rand(), c'est surtout pour ça qu'elle est intéressante.

Citation:

---

Envoyé par Mac LAK

Le but est en général de générer un jeu de test, "aléatoire" mais sauvegardé pour pouvoir être rejoué (notamment s'il lève un bug !! :mrgreen). Au pire, je pourrais sauvegarder la valeur d'initialisation, donc.

---

C'est typiquement le cas de figure auquel je pensais en parlant de valeur fixe.

Citation:

---

Envoyé par Mac LAK

L'autre cas est un générateur à peu près aléatoire censé simuler un environnement : dans ce cas, j'ai besoin au contraire de choses non-reproductibles et complètement imprévisibles afin de tester la robustesse et/ou les cas "rares" auxquels on n'aurait pas pensé "à la main".

---

Je vois pourtant plusieurs autres cas, en vrac:

• Génération de padding plus ou moins aléatoire dans le but de gêner une éventuel compression des couches réseau basse.
• Tirage aléatoire du port côté client à utiliser.
• Simulation d'un simple tirage de dé.
• Génération d'un challenge crypto.

Et en cherchant, on pourrais en trouver bien d'autres. Toutes ces utilisations n'ont visiblement pas les même contraintes et donc pas forcément les mêmes solutions.

Citation:

---

Envoyé par Mac LAK

La méthode que je donne est une des rares à ne pas être dépendante de l'implémentation de rand(), c'est surtout pour ça qu'elle est intéressante.

---

Mais la disponibilité d'un timer haute résolution, ainsi que l'API à utiliser, est dépendante de la plate-forme utilisée, ce qui n'est pas forcément mieux.

Citation:

---

Envoyé par gl

C'est typiquement le cas de figure auquel je pensais en parlant de valeur fixe.

---

Sauf que... la séquence pseudo-aléatoire générée n'étant pas forcément (pour ne pas dire "jamais") la même suivant les plate-formes utilisées, sauvegarder le jeu généré est la seule manière "fiable".
Tu n'es même pas à l'abri d'un changement dans l'implémentation au prochain patch du compilateur, ce qui fait que de toutes façons, sauvegarder la graine et compter sur rand() pour rejouer la même séquence est mauvais... C'est d'ailleurs notamment pour ça qu'il ne faut JAMAIS l'utiliser en cryptographie, même en étant verrouillé sur une plate-forme donnée.

Citation:

---

Envoyé par gl

Mais la disponibilité d'un timer haute résolution, ainsi que l'API à utiliser, est dépendante de la plate-forme utilisée, ce qui n'est pas forcément mieux.

---

Ça, encore, c'est pas le problème majeur : un coup de #ifdef pour unifier tout ça et c'est bon, ou via l'utilisation d'une API d'abstraction (ACE, POCO, etc.). En général, j'ai jusqu'à 4 cibles différentes possibles pour le même code, donc ce genre de choses est déjà mis en "standard" depuis un moment.
Au pire, t'as toujours la possibilité de mettre un "#else" final utilisant "rand()+time(NULL)" comme graine, c'est toujours "moins pire" que "time(NULL)" tout seul... Mais je ne connais pas beaucoup de systèmes où il n'y a pas au moins un ticker à la milliseconde présent, et c'est même souvent beaucoup mieux encore en précision que la milliseconde. Microcontrôleurs inclus.

Citation:

---

Envoyé par Mac LAK

Sauf que... la séquence pseudo-aléatoire générée n'étant pas forcément (pour ne pas dire "jamais") la même suivant les plate-formes utilisées, sauvegarder le jeu généré est la seule manière "fiable".
Tu n'es même pas à l'abri d'un changement dans l'implémentation au prochain patch du compilateur, ce qui fait que de toutes façons, sauvegarder la graine et compter sur rand() pour rejouer la même séquence est mauvais... C'est d'ailleurs notamment pour ça qu'il ne faut JAMAIS l'utiliser en cryptographie, même en étant verrouillé sur une plate-forme donnée.

---

Par contre, si on fournit soi-même le générateur pseudo-aléatoire, il n'y a pas de problème (mais ça confirme qu'il ne faut pas utiliser rand()).

Citation:

---

Envoyé par Médinoc

Par contre, si on fournit soi-même le générateur pseudo-aléatoire, il n'y a pas de problème (mais ça confirme qu'il ne faut pas utiliser rand()).

---

Ah ça, je n'ai jamais prétendu (et je n'oserais pas le faire) qu'un générateur pseudo-aléatoire "maison" était mauvais pour faire de la cryptographie... Juste que "rand()" n'est pas un bon candidat à cet exercice. :mouarf:

Citation:

---

Envoyé par Mac LAK

Sauf que... la séquence pseudo-aléatoire générée n'étant pas forcément (pour ne pas dire "jamais") la même suivant les plate-formes utilisées, sauvegarder le jeu généré est la seule manière "fiable".
Tu n'es même pas à l'abri d'un changement dans l'implémentation au prochain patch du compilateur, ce qui fait que de toutes façons, sauvegarder la graine et compter sur rand() pour rejouer la même séquence est mauvais...

---

Tout à fait. Encore une fois ça dépends de ce que tu veux faire.

Citation:

---

Envoyé par Mac LAK

C'est d'ailleurs notamment pour ça qu'il ne faut JAMAIS l'utiliser en cryptographie, même en étant verrouillé sur une plate-forme donnée.

---

D'une manière générale, utiliser un simple rand() en cryptographie n'est pas une bonne idée.

Citation:

---

Envoyé par Mac LAK

Ça, encore, c'est pas le problème majeur : un coup de #ifdef pour unifier tout ça et c'est bon, ou via l'utilisation d'une API d'abstraction (ACE, POCO, etc.). En général, j'ai jusqu'à 4 cibles différentes possibles pour le même code, donc ce genre de choses est déjà mis en "standard" depuis un moment.
Au pire, t'as toujours la possibilité de mettre un "#else" final utilisant "rand()+time(NULL)" comme graine, c'est toujours "moins pire" que "time(NULL)" tout seul...

---

Tout à fait d'accord sur le principe.

Mais lorsque l'aléa fournie par time(NULL) est amplement suffisant pour le problème donné, est-ce vraiment la peine d'aller plus loin et de se compliquer inutilement la tâche ?

Je ne prétends pas que l'utilisation de time(NULL) suffit toujours. Il existe même de nombreux cas où ce n'est clairement pas suffisant.

Maintenant, si on se trouve dans un cas où cette solution convient, est-il pertinent de chercher autre chose ? Surtout s'il n'existe pas de solution immédiatement portable sur toutes les cibles concernées ?

Citation:

---

Envoyé par gl

Maintenant, si on se trouve dans un cas où cette solution convient, est-il pertinent de chercher autre chose ? Surtout s'il n'existe pas de solution immédiatement portable sur toutes les cibles concernées ?

---

Disons que c'est plutôt un excellent topic pour montrer du doigt cette faiblesse de srand(), expliquer pourquoi c'est une faiblesse, et comment la contourner quand on doit avoir "mieux"... :mrgreen:

Citation:

---

Envoyé par Mac LAK

Disons que c'est plutôt un excellent topic pour montrer du doigt cette faiblesse de srand(), expliquer pourquoi c'est une faiblesse, et comment la contourner quand on doit avoir "mieux"... :mrgreen:

---

Formuler comme ceci je ne peut qu'être d'accord.

Au passage pour le "mieux", une alternative qui me semble assez intéressante (bien que je n'ai pas encore eu trop le temps de jouer avec) lorsqu'elle est disponible, est boost.Random.