Les nombres aléatoires: la fonction rand() en C

On a souvent besoin de nombres aléatoires pour différentes applications (bien entendu, les contraintes ne sont pas les mêmes d'une application à l'autre).

Si on prend l'exemple d'un lecteur MP3 qui doit trouver une piste aléatoirement et celui d'un programme de cryptographie qui doit générer une clé, on remarque que les besoins ne sont pas les mêmes : dans le premier cas, il n'est pas important que le prochain chiffre puisse être déduit du ou des précédents, alors que dans le second cas, c'est critique.

Il faut bien comprendre que le vrai aléatoire n'existe pas, à part d'un point de vue physique.

[modifier] La fonction srand

• Domaines d'application : cette fonction peut être utilisée pour des applications non critiques comme pour un lecteur mp3, la génération d'un terrain, etc.
• Simplicité de mise en œuvre : facile.
• Utilisation : le header contient les définitions de srand(), de rand() et de la constante RAND_MAX. RAND_MAX vaut au minimum 32767.

#include <stdlib.h>

• Fonction d'initialisation :

void srand(unsigned int);

Le paramètre à mettre doit être changeant d'une exécution à l'autre pour éviter de démarrer la suite toujours au même endroit. En général, on utilise l'heure courante.

Pour bénéficier de l'effet 'pseudo-aléatoire', cette fonction doit être appelée une seule fois dans tout le programme. Par exemple, lors du démarrage, c'est à dire dans les premiers instructions de main().

• Fonction qui donne un nombre aléatoire :

int rand();

Les nombres en sortie sont des nombres compris entre 0 et RAND_MAX.

• Pour obtenir des nombres entiers compris entre a et b :(b-a doit être inférieur ou égal à RAND_MAX.

int r;
 r = a + (int) ((double) rand() * (b - a + 1) / (RAND_MAX+1));

Attention, cette fonction n'est pas équiprobable. Si vous voulez une fonction équiprobable, utilisez plutôt cette méthode :

• Décomposez le nombre en puissances de 2 (par exemple : 11 = 2^0 + 2^1 + 2^3)
• Appliquez la méthode pour les puissances de 2 décrites ci-dessous.

Donc dans notre cas, on obtiendra:

int r;
 r = rand() & 1 + rand() & 3 + rand() & 7;

• Pour obtenir des nombres réels inclus entre a et b non compris :

double r;
 r = a + ((double) rand() * (b - a) / (RAND_MAX+1));

Pour obtenir plus de précisions il est conseillé de faire

r = a + ((double) rand() / (RAND_MAX + 1)) * ((double) rand() / (RAND_MAX + 1)) * (b - a)

ou

r = a + ((double) (rand() + rand() << 16) / ((double) (RAND_MAX + 1) * (RAND_MAX + 1))) * (b - a);

• Pour obtenir des nombres réels inclus entre a et b compris :

double r;
 r = a + ((double) rand() * (b - a) / RAND_MAX);

• Cas particulier des nombres entiers puissance de 2 : si b-a=2ⁿ alors cette solution est applicable.

int r;
 r = a + rand &((1 << n) - 1);

(1<<n)-1=2n-1 : cette constante peut être calculée avant la compilation.

Ne surtout pas utiliser le modulo pour générer des entiers aléatoires.

[modifier] Exemple

#include <time.h>               /* time */
#include <stdlib.h>             /* srand rand */
 
int main (void)
{
   int entier;
   double virgule;
   srand (time (NULL));         /* Initialisation du générateur */
   virgule = (double) rand () / (RAND_MAX+1);
   /* Génération d'un nombre entre [0;1[ avec un précision de 1/RAND_MAX */
   virgule *= 3;                /* Le nombre est compris entre [0;3[ */
   virgule += 1;                /* Le nombre est compris entre [1;4[ */
   entier = (int) virgule;      /* le nombre est soit 1 2 ou 3 */
   /* Je viens de décomposer les formules écrites ci-dessus */
   /* Maintenant le cas particulier des puissances de 2 */
   /* On veut générer un nombre entre 1 et 5 */
   /* 5-1=4=2^2 */
   entier = 1 + rand () & ((1 << 2) - 1);
   /* ou entier=1+rand()& 3; */
   return 0;
}

[modifier] Création de sa propre fonction d'aléatoire

• Domaines d'application : applications sensibles.
• Simplicité de mise en oeuvre : difficile.
• Dans ce cas, la meilleure solution est d'utiliser des sondes externes de température, pression, voltage, etc. En combinant bien différents paramètres physiques on peut obtenir des résultats satisfaisants. On peut ajouter aussi l'heure, le temps que met un paquet pour nous revenir de tel ou tel site, ou même le temps que met l'ordinateur à faire une boucle for.

Bien évidemment, il faut prendre les chiffres les moins significatifs. Par exemple, si on prend la sonde de température du PC il faudra prendre les 2 chiffres après la virgule.

Ce genre d'algorithme est long à mettre en place car il doit gérer des entrées / sorties supplémentaires.

[modifier] Pseudo aléatoire

• Domaines d'application : applications demandant un minimum de securité.
• Simplicité de mise en oeuvre : moyen.

Le pseudo aléatoire est un générateur de nombre aléatoire calculés (rand() en est un).

De nombreaux algorithmes peuvent être utilisés : on peut prendre par exemple la période de la divison de deux nombres premiers.

Mais une chose reste : il y a toujours une phase d'initialisation pour ce type de générateurs. Ça paraît paradoxal, il faut des nombres à peu près aléatoires pour en calculer d'autres :-).

[modifier] Conclusion

Plusieurs solutions existent pour générer des nombres aléatoires. La plus simple est rand(), et elle convient sûrement à la plupart des besoins. De toute facon c'est sûrement la seule chose que vous recherchez : comment fonctionnent rand() et srand() :-p.