Discussion :

[reanon]

Bonjour à tous,

Je suis dans le portage d'un projet C/C++ de Windows vers OS X. En de nombreux endroits j'utilise la fonction C standard rand(). Mon problème est que je m'aperçois qu'à partir du même seed, la séquence pseudo-aléatoire générée sous Mac est différente de celle générée sous Windows... Ce qui m'a très étonné, car je pensais que c'était supposé être stable et indépendant de la plateforme.

Le problème est qu'à certains endroits j'ai absolument besoin d'obtenir la même séquence à partir d'un seed connu.

Par exemple, en compilant ça (avec GCC dans les deux cas) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
 
int main ()
{
  srand (3);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  printf ("%d\n", rand()%100);
  return 0;
}

J'obtiens cette sortie sous Windows 7 x64 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
48
96
94
91
31
77
2
3
17
68
9

Et celle-ci sous OS X 10.8 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
21
47
25
27
43
16
32
40
75
33
73

Les séquences sont stables sous chaque OS (j'obtiens toujours la même séquence à partir du même seed), mais différentes d'un OS à l'autre ; ce que je pensais pas, n'ayant pas développé en cross-platform jusque-là.

Alors, est-ce le comportement normal ou pas ? Si non, quelle pourrait être la cause ? Si oui, comment faire pour être assuré de la même séquence partout (une lib ou classe spécialisée peut-être ; mais pas de lib généraliste genre Boost pour uniquement un RNG please) ?

[jo_link_noir]

L'implémentation est dépendante et sur mon système la séquence est encore différente ^^.

Boost.random est très bien en tant que lib, pourquoi sans passer ? Sinon en utilisant le C++11 plusieurs générateurs de nombre aléatoire existe dans le standard: http://en.cppreference.com/w/cpp/numeric/random. Les même que dans boost...

[Emmanuel Deloget]

Bonjour à tous,

Je suis dans le portage d'un projet C/C++ de Windows vers OS X. En de nombreux endroits j'utilise la fonction C standard rand(). Mon problème est que je m'aperçois qu'à partir du même seed, la séquence pseudo-aléatoire générée sous Mac est différente de celle générée sous Windows... Ce qui m'a très étonné, car je pensais que c'était supposé être stable et indépendant de la plateforme.

Non, pas du tout. Le standard dit juste que les valeurs générées sont entre 0 et RAND_MAX avec une période de 2^32. RAND_MAX n'est même pas défini dans la norme, et l'algorithme exact utilisé ne l'est pas non plus. Du coup, chaque libc y vas de sa propre implémentation et de sa propre valeur de RAND_MAX. Il y a à peu près 0% de chance que deux libc aient la même implémentation, condition nécessaire pour obtenir la même séquence.

Le problème est qu'à certains endroits j'ai absolument besoin d'obtenir la même séquence à partir d'un seed connu.

Utilise ta propre fonction rand, ou utilise les fonctionnalités offertes par C++11. L'idée est de ne pas dépendre de la libc du système pour obtenir tes valeurs. Coder une fonction rand() n'est pas compliqué - le net est rempli d'exemple. Voir http://en.wikipedia.org/wiki/Linear_...tial_generator ou http://rosettacode.org/wiki/Linear_c...tial_generator pour plus d'information sur le sujet.

[reanon]

Merci pour ces pistes

J'excluais Boost parce que le projet est assez conséquent et n'utilise pas du tout Boost (et comme il s'agit d'un portage, je ne vais pas tout réécrire). Je ne voudrais donc pas ajouter une grosse lib pour n'utiliser qu'une classe par exemple. Par ailleurs, j'avoue ne connaitre Boost que de réputation mais ne jamais l'avoir utilisé. De fait, je ne sais pas si le Boost.random dont tu me parles est une lib indépendante dans la collection des libs Boost ou vient forcément avec l'ensemble Boost au total. Peux-tu m'en dire plus.


En fait, sachant que j'ai aussi des endroits du code où ça peut bien être une séquence imprévisible, je peux vivre avec srand/rand à ces endroits. Mais c'est uniquement pour les quelques cas où j'ai besoin d'une séquence fixe à partir d'un seed connu que je voudrais implémenter autre chose... De fait, ma question serait : quelle est la solution la plus light (sans ajout de grosse lib) pour ces cas ?

Ajout : ta réponse est arrivée pendant que j'écrivais la mienne, Emmanuel... Mais je dois partir là, tout de suite. Je la lirai et y réagirai donc un peu plus tard

Non, pas du tout. Le standard dit juste que les valeurs générées sont entre 0 et RAND_MAX avec une période de 2^32. RAND_MAX n'est même pas défini dans la norme, et l'algorithme exact utilisé ne l'est pas non plus. Du coup, chaque libc y vas de sa propre implémentation et de sa propre valeur de RAND_MAX. Il y a à peu près 0% de chance que deux libc aient la même implémentation, condition nécessaire pour obtenir la même séquence.

Ma supposition venait de ce qui est écrit sur http://www.cplusplus.com/reference/cstdlib/srand/, je cite : "Two different initializations with the same seed will generate the same succession of results in subsequent calls to rand." Mais effectivement, il ne parlent pas de même séquences sur différentes plateformes.

Utilise ta propre fonction rand, ou utilise les fonctionnalités offertes par C++11. L'idée est de ne pas dépendre de la libc du système pour obtenir tes valeurs. Coder une fonction rand() n'est pas compliqué - le net est rempli d'exemple. Voir http://en.wikipedia.org/wiki/Linear_...tial_generator ou http://rosettacode.org/wiki/Linear_c...tial_generator pour plus d'information sur le sujet.

Oui, à ce stade, ça me parait être le plus light.

Je crois que j'ai de la lecture Merci à vous deux.

[JolyLoic]

Plutôt qu'utiliser un truc choppé sur le net, as-tu vérifié si ton compilateur ne définissait pas le header<random> du C++11 qui offre les garanties que tu souhaites ? S'il n'est pas trop vieux, ça devrait être le cas.

[reanon]

En terme d'assurance de solidité, oui, bien sûr, tu as complètement raison, Loïc. Mais étant dans du cross-platform, je n'utilise pas un compilateur mais plusieurs... Et sachant que je pourrais aussi aborder des OS's que je ne connais pas d'emblée (par exemple, je ne suis pas utilisateur Apple et n'y vais que parce que le public visé par ce projet en est largement équipé), ces compilateurs peuvent toujours être remplacés par un autre en cours de développement ; selon les besoins. Je préfèrerais être compiler-independent.

Actuellement, j'utilise GCC partout (TDM64-MinGW 4.7 sous Windows et FSF GCC 4.7 sous OS X) et il y a effectivement peu de chance que j'aille vers plus ancien, mais on ne sait jamais... Je préfèrerais un code qui compile (quasi) partout.

Je viendrai dire la solution que j'ai retenue une fois choisie et mise en oeuvre (ça peut toujours servir à quelqu'un un jour ou un autre).

[oodini]

Exiger en 2014 un compilateur C++11 ne me paraît pas totalement délirant.
D'autant plus qu'on parle de C++14...

[reanon]

Mais je ne rejette rien, oodini. Je réfléchis simplement à voix haute en laissant décanter le sujet (avec toutes les contradictions intermédiaires qu'engendre un raisonnement live, de fait).

[white_tentacle]

Coder un générateur aléatoire avec (par exemple) un brave registre à décalage, ça se fait très simplement, et ça te garantiras effectivement une reproductibilité de la séquence.

Le support du C++11, sur certaines architectures embarquées, c’est malheureusement encore loin.

[reanon]

Mon projet est à ce stade pour PC/Mac, white_tentacle. Mais sait-on jamais... Bref, après réflexion et quoique pas réfractaire au C++11 par principe (ici mon choix n'est que pragmatique), j'ai décidé de simplement régler mon problème sans déborder du sujet (mon projet n'étant pour l'instant pas compilé en std C++11)

De même, je n'ai aucune envie de repartir d'un algorithme et d'implémenter ma solution (mon projet est suffisamment prenant comme ça et l'aspect PRNG portable est nécessaire mais connexe).

J'ai donc cherché des solutions clé en main et ces deux là m'inspirent :
- prng.c de Pen Pfaff : http://benpfaff.org/writings/clc/random.html
- random.cpp de James Grimbleby : http://myweb.tiscali.co.uk/jgrimbleby/random.htm

Si vous avez un avis sur ces deux implémentations, n'hésitez pas bien sûr
Bonne nuit

[Emmanuel Deloget]

Très honnêtement, c'est compliqué pour ton besoin. Tu as besoin d'une fonction qui remplace rand(). rand() est (le plus souvent) un générateur linéaire congruentiel.

La formule à utiliser est simple, et le code l'est tout autant.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
namespace rnddetails 
{
   const std::uint32_t modulus = M;
   const std::uint32_t multiplier = A;
   const std::uint32_t offset = B;
 
   std::uint32_t current_state = SEED;
 
   uint32_t adapt_range(uint32_t input)
   {
       // exemple ; le code réel varie selon les valeurs de M, A et B
       // cf. http://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use
       // attention : tous les bits n'ont pas la même qualité de random. 
       return (input >> 14) & 0xffff; // pour renvoyer des valeurs entre 0 et 65535 
   }
}
 
uint32_t random()
{
   using namesapce rnddetails = rd:
   rd::current_state = ((std::uint64_t)rd::multiplier * rd::current_state + rd::offset) % rd::modulus;
   return rd::adapt_range(rd::current_state);
}
 
void random_reseed(uint32_t seed)
{
   using namesapce rnddetails = rd:
   rd::current_state = seed;
}

Ce n'est pas plus complique que ça. Ensuite, il faut choisir de bonnes valeurs pour M, A et B. SEED est une valeur quelconque (on peut prendre 0, sauf si B == 0, auquel cas ça se complique sévèrement).

Wikipedia donne un certain nombre de constantes (http://en.wikipedia.org/wiki/Linear_..._in_common_use).

[reanon]

Merci Emmanuel, mais je n'ai pas dit que le sujet était compliqué (je n'en sais fichtre rien), mais que ne le connaissant pas et n'ayant pas de temps de me pencher dessus, je préférais une solution clé en main (et si elle est copyrightée, tant mieux : ça engage toujours). M'enfin, quand on sait, c'est souvent simple, mais quand on ne sait pas, il manque le discernement... Et franchement, sur les PRNG, je ne l'ai pas (et ne souhaite pas introduire de pièce hasardeuse dans mon projet) Cela dit, ton code est utile à mon éducation, mais je ne peux pas le valider pour entrer dans mon projet (j'aurais envie de dire : fais une page, signe là et je viendrais alors télécharger chez toi avec crédit à la clé dans ma about-box)

J'ai essayé les deux PRNG indiqués dans l'un de mes précédents post et les ai abandonnés (l'un présentait une ambiguité de précédence d'opérateurs - et à moins de comprendre ce que l'auteur voulait faire, j'ai préféré m'abstenir -, et l'autre étant en C et ne compilant pas d'emblée est passé à la trappe).

Tenant compte de vos commentaires (dont celui d'Emmanuel me disant que ma première sélection était trop compliquée), j'ai finalement sélectionné, mis en oeuvre, testé et adopté l'implémentation de type Mersenne Twister par Paul Gresham ; référencée parmi les implémentations listées sur cette page : http://www.math.sci.hiroshima-u.ac.j...NG/c-lang.html

Résolu, donc. Merci pour vos éclairages divers et variés