Nombres aléatoires

        

Un générateur de nombres pseudo-aléatoires est un algorithme implémenté par une fonction, qui retourne à chaque invocation une nouvelle valeur numérique, et telle que la suite des valeurs retournées ait de bonnes propriétés statistiques : ces propriétés permettent de supposer qu'il s'agit d'une suite de variables aléatoires indépendantes de loi uniforme dans un intervalle spécifié.

Ces nombres sont utilisés dans deux situations :

•   pour tester un programme quelconque, en lui soumettant comme données des << jeux de test >> générés aléatoirement, et en comparant le résultat calculé au résultat attendu
•   pour implémenter des algorithmes probabilistes, soit pour des problèmes numériques (intégration de Monte-Carlo), soit pour améliorer le comportement d'algorithmes par randomisation, soit pour donner un résultat avec une probabilité d'erreur (test de primalité), ou pour briser des symétries (élection d'un chef), par obstination.

La conception d'un générateur de nombres pseudo-aléatoires est délicate (ce n'est pas que ces algorithmes soient difficiles à écrire, c'est qu'il est difficile d'échapper à des régularités arithmétiques qui s'opposent à l'uniformité souhaitée). Dans la pratique, il est préférable d'utiliser un générateur fourni dans la bibliothèque standard : la fonction drand48 retourne un double dans l'intervalle [0,1[ et est déclarée dans math.h.

Pour obtenir un entier dans l'intervalle [a,b], on pourra définir :

int irand(int a, int b) {
  return a + (int)(drand48() * (b-a+1));
}

En particulier, on obtiendra un tirage à pile ou face en appelant irand(0,1).

Comme il n'y a rien d'aléatoire dans l'écriture de la fonction drand48, chaque exécution du programme verra la même suite générée. Si l'on doit faire des traitements statistiques portant sur les résultats de plusieurs exécutions, il est alors nécessaire d'obtenir une suite différente à chaque exécution, pour assurer l'indépendance des résultats. Il faut alors initialiser la graine (anglais seed ) du générateur, en appelant en début de programme la fonction srand48, qui prend en argument un long. Pour garantir une graine différente à chaque fois, l'usage est de recourir à l'horloge de la machine, avec la fonction time, à laquelle on passe NULL en argument, et qui est déclarée dans time.h :

 

  srand48(time(NULL));