Discussion :

[Kalith]

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.

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 !

[Goten]

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.

[gl]

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.

[Invité]

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

[Mac LAK]

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".

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.

[gl]

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.

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.

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.

[Mac LAK]

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.

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.

[Médinoc]

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()).

[Mac LAK]

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.

[gl]

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.

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.

Ç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 ?

[Mac LAK]

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"...

[gl]

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"...

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.