• Facile

Ce cours est visible gratuitement en ligne.

Vous pouvez être accompagné et mentoré par un professeur particulier par visioconférence sur ce cours.

J'ai tout compris !

Fabriquez votre propre fonction "rand"

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Comment faire pour avoir des nombres aléatoires ?

Oui mais imaginons que nous n'avons pas accès à rand, comment faire (imaginons que nous devions recoder toutes les bibliothèques C suite à un crash massif de machines) ? Et puis pourquoi faut-il initialiser avec un time() si c'est aléatoire ?

Heu ... tu me poses une colle là !

Dans ce tuto, vous allez découvrir tout ce qui se cache derrière rand.
Vous n'avez besoin d'aucune connaissance particulière pour lire ce tuto (pas même avoir déjà utilisé rand). Les exemples seront en C++, mais sont évidemment transposables à tous les langages. Vous aurez un petit cadeau à la fin du tutoriel : une classe Aleatoire qui produit des nombres aléatoires comme une grande !

Note : ne vous attendez pas à écrire plein de code super compliqué dans ce tuto ; l'ensemble du code final ne dépassera pas les 40 lignes. Le but ici est de bien comprendre ce qu'on fait et pourquoi on le fait.

L'aléatoire... vraiment aléatoire ?

Que de la poudre aux yeux !

Eh oui, je vais commencer fort en vous assénant d'entrée cette vérité troublante : aucun algorithme de calcul ne peut produire des nombres de façon aléatoire. En effet, par définition, l'aléatoire ne peut pas être calculé par un quelconque algorithme. Vous allez me dire qu'après tout, ça semble logique, mais il fallait le démontrer : monsieur Per Martin-Löf l'a fait en 1966.

Quoi ? Mais tu nous a roulés alors ! Le tuto est déjà fini ?

Non, ne vous inquiétez pas, c'est loin d'être fini ! On ne peut effectivement pas générer un nombre parfaitement aléatoire, mais on peut quand même s'en approcher. On appelle alors les nombres créés des nombres pseudo-aléatoires. On a l'impression que les nombres générés sont aléatoires, mais si on fait une étude approfondie, on peut se rendre compte qu'ils suivent un certain mécanisme. C'est ce que l'on va voir dans ce tuto.

J'entends déjà quelques esprits retors me demander si on ne peut quand même pas produire des nombres de façon purement aléatoire ; en fait vous connaissez déjà la réponse : c'est oui. Lancez un dé : vous venez de réaliser une expérience purement aléatoire ; mais pour l'utiliser en informatique, ce n'est guère commode, vous en conviendrez (bien que certains l'aient fait). C'est pourquoi nous allons effectuer un bref survol de ces méthodes purement aléatoires.

Des moyens purement aléatoires

L'accumulation d'entropie

Ne vous enfuyez pas en courant ! Le nom est un peu pédant, mais l'idée est fort simple. L'entropie, on peut traduire ce mot simplement par "désordre". Donc cette méthode consiste à attendre qu'un nombre d'événements aléatoires (le mouvement de la souris, les temps d'accès mémoire, les connexions reçues sur un port réseau...) suffisamment élevé se produise pour pouvoir donner un nombre. Cette méthode n'est à priori pas de très bonne qualité, pour deux raisons :

  • les évènements considérés ne sont que moyennement aléatoires (en effet, on clique toujours sur les mêmes boutons) ;

  • cette méthode est relativement lente ! Si on attend un mouvement de souris et que l'utilisateur ne se sert que du clavier, on peut attendre longtemps avant d'avoir un nombre quelconque !

C'est pourquoi on ne l'utilise pas "brut de décoffrage", mais enveloppée dans des algorithmes tels que Yarrow ou Fortuna (entre autres) en cryptologie ; il est en effet très dur pour un pirate de prévoir les nombres générés. Comme l'indiquent les articles mis en lien, son implémentation dans une optique de cryptologie est assez complexe !

Les méthodes physiques

On peut aussi utiliser des méthodes physiques pour produire des nombres aléatoires. Effectivement, il existe des phénomènes qui sont parfaitement aléatoires : les variations d'une résistance électrique, la présence d'un photon à un endroit donné... Toute la difficulté de ces méthodes est de ne pas trop perturber le système pour qu'il conserve son caractère aléatoire sans être biaisé (déformé) lors de la mesure de la valeur. Par exemple, si pour mesurer une variation de résistance (qui sera évidemment minime), on utilise un voltmètre qui introduit une faible résistance dans le circuit, la mesure sera faussée !

Pour avoir un exemple concret, Toshiba a dévoilé en février 2008 la sortie d'un circuit générateur de nombres aléatoires très compact (1200 micromètres²) produisant 2Mbits aléatoires par seconde. Pour vous faire une idée, cela correspond à environ 62500 entiers sur la plupart des machines ; autant dire que c'est ridiculement faible par rapport à un appel à la fonction rand qui en génère beaucoup plus, en beaucoup moins de temps ! Ceci dit, les nombres trouvés avec rand ne sont que pseudo-aléatoires, donc de moins bonne qualité.

Un avant goût historique : la méthode des carrés médians

Von Neuman, l'un des pères de l'informatique moderne, introduisit cet algorithme en 1946. On considère que c'est la première méthode algorithmique destinée à générer automatiquement des nombres aléatoires. Vous allez voir, son fonctionnement n'est pas très compliqué, mais nous allons déjà voir apparaître des choses intéressantes.

Le principe est le suivant : on prend un nombre, par exemple 35, que l'on met au carré. Dans notre cas nous avons 35x35=1225. En suite, on prend les chiffres du milieu, ici 22. Puis on recommence ; on met 22 au carré : 22x22 = 484, que l'on peut écrire 0484. Nous obtenons un nouveau nombre : 48 ... La suite des nombres générées sera donc : 35, 22 et 48.

Évidemment, en pratique, on ne se contente pas de prendre des nombres à 2 chiffres, mais le principe est le même. L'implémentation de cette méthode n'est pas très compliquée ... à condition de réfléchir en base 2 et de se servir des opérateurs bits à bits. Ceci étant complètement en dehors de ce que je veux vous expliquer, je vous renvoie au tuto de 1337833K sur le sujet.

Nous allons cependant continuer à la main les calculs :

35 22 48 30 90 10 ...

Et là on s'arrête ! Eh oui, vu qu'on connaît nos tables de multiplications : 10x10=0100 ; on prend les chiffres du milieu, on retombe sur 10 et on n'en bougera plus. Pas très aléatoire comme méthode ! C'est encore pire si l'on part de 84 :

84 05 02 00 00 00 00 00

Von Neumann était bien évidement conscient de ces problèmes (parce qu'il y en a en fait plusieurs) mais craignait d'en introduire d'autres en modifiant l'algorithme. Vous l'aurez compris, cette méthode est limitée et assez délicate à utiliser ; c'est pourquoi peu de temps après, Lehmer introduisit une nouvelle méthode ...

Une méthode... puissante !

À la découverte de la méthode

L'une des méthodes les plus utilisées actuellement est la méthode des congruences linéaires.

Là encore, des grands mots pour quelque chose de pas si compliqué que ça ! Décortiquons ensemble cette expression barbare.
Congruence : dans notre cas, cela se réfère à ce qui a rapport avec le reste de la division entière (vous savez, le signe '%' qui ne sert à rien ?).
Linéaire : en simplifiant, cela revient à dire que l'on ne fait que des opérations de type addition et multiplication. Le type d'opération "mise au carré" et "logarithme" n'existe pas (ce n'est pas très grave si vous ne comprenez pas cette phrase, c'est juste pour la culture).

De façon plus concrète, voici une formule permettant de calculer une suite de nombres aléatoires :

nouveau_nombre= (a*ancien_nombre + b) % m

Pour traduire cela avec des mots, ça donne : pour trouver le nouveau nombre aléatoire, il faut :
1. Prendre celui que l'on vient de calculer, le multiplier par a puis ajouter b ;
2. Si le nombre obtenu est plus grand que m, lui enlever m jusqu'à ce qu'il soit plus petit.

:euh:

Rien ne vous choque ? Pas un petit problème de variable non définie ? Ah si quand même ! La formule dit qu'il faut prendre le nombre que l'on vient de calculer, mais si on n'a encore rien calculé, on prend quoi ? C'est là un sujet épineux dont on pourrait débattre longtemps, mais nous n'allons pas nous étendre sur ce sujet. En général, comme première valeur, on prend le timestamp ; cette première valeur s'appelle la graine (seed en anglais).

Cela vous explique pourquoi, en C, vous devez initialiser rand par srand (qui doit vouloir dire seedrand), en passant en argument le timestamp actuel ! Si vous ne le faites pas, la suite de nombres générée est toujours la même... c'est fâcheux pour un jeu de hasard...

Un premier code

Maintenant que vous avez la théorie, je vous propose de coder votre propre générateur aléatoire. L'exercice consiste à écrire un programme (tout dans le main, on s'embêtera plus tard avec des jolies structures) qui affiche 15 nombres aléatoires.
Vous devez réfléchir comment coder la formule que j'ai donnée au-dessus (pour les valeurs de a, b et m, mettez un peu au hasard pour l'instant, en bidouillant pour que ça marche mieux si besoin, mais gardez-les relativement petits).

Attention, prêts ? C'est parti !

#include <iostream>
#include <ctime>
using namespace std;

main(){
	unsigned int a=3,b=3,m=5;              // Définition des valeurs
	unsigned int nombre = time(NULL);    // Définition de la graine
	for(int i=0;i<15;i++){
		nombre = (a*nombre+ b) % m;  // Calcul effectif
		cout<<nombre<<" ";            // Affichage
	}
}

Voilà, je pense que ça ne présentait pas de grandes difficultés ; si oui, déroulez le programme sur papier (par exemple 1e boucle : nombre=10, nombre*a=30..., 2e boucle : nombre =..., ) en ayant la "formule" donnée plus haut sous les yeux. Pour ceux qui ont utilisé un tableau pour stocker toutes les valeurs, ce n'était pas utile, et je dirais même une erreur. Là, ça va, il n'y avait que 15 nombres à générer. Mais imaginez deux secondes que vous produisiez des nombres pour une application qui demande des milliards de nombres aléatoires ? La mémoire ne sera jamais assez grande pour conserver tous ces nombres !

Maximisons la période !

Maintenant, analysons la sortie de ce programme :

4 0 3 2 4 0 3 2 4 0 3 2 4 0 3

J'avais pris m = 5, donc logiquement, toutes mes valeurs sont entre 0 et 4 (inclus).
On peut déjà constater 2 choses :

  • les nombres suivent une certaine séquence qui se répète (ici 4,0,3,2). Quelles que soient les valeurs que l'on prend pour a, b et m, nous aurons toujours ce comportement ; cela peut paraître gênant, vu que le générateur n'est du coup plus du tout aléatoire. En pratique m est très grand, donc la séquence est également très longue ;

  • il manque un nombre dans la séquence : 1 ; le générateur est donc clairement faussé ! En effet, pour un générateur produisant des nombres entre 0 et 4, on doit s'attendre à une moyenne de 2 ; ici, si on fait le calcul, on a (0+2+3+4)/4 = 2.25 comme moyenne !

Cela m'amène à vous parler de la période. La période correspond à la longueur de la séquence générée; dans notre exemple, la période est de 4. Evidemment, plus cette période est grande, meilleur est le générateur.
Dans le cas de cette méthode, on dit que la période est maximale si elle est égale à m. Vous remarquerez facilement qu'avec cette méthode, chaque nombre n'est "visité" qu'une fois au plus ; si le calcul "repasse" par le même nombre, cela signifie qu'on a fait le tour de la séquence.
Avoir une période maximale signifie donc que tous les nombres entre 0 et m-1 (inclus) sont "visités" une seule fois. Si la période est maximale, la moyenne des nombres sortis sera de (m-1)/2 (je ne ferai pas le calcul précis ici, mais on peut voir "intuitivement" que ça marche), on a donc un bon argument en faveur de la validité du générateur.

Au passage, vous remarquerez que si la première valeur générée est 1, toutes les valeurs suivantes seront les mêmes (= 1) ! On voit donc clairement ici une limite de ce générateur.

Ok ! Donc pour avoir une période maximale, il suffit que je teste des valeurs a, b et m et que je regarde si tous les chiffres sont "visités" ?

On pourrait faire comme ça... Mais ça serait trèèèèèèèès long si m est très grand (ce qui est le cas en pratique). Heureusement des gens très intelligents ont réfléchi au problème et nous ont donné un critère pour que la période soit maximale. Ce critère s'écrit sous la forme de trois conditions.

La période est maximale si et seulement si :

  • b et m sont premiers entre eux ;

  • si m est un multiple de 4, alors a%4 = 1 ;

  • pour tous les nombres premiers p diviseurs de m, on a a%p =1 .

Mais la 2e condition, elle ne sert à rien ! Ce n'est qu'un cas particulier de la 3e !

Erreur ! La troisième nous parle des diviseurs premiers de m. La deuxième est effective si 4 est un diviseur de m. Mais 4 n'est pas premier (eh oui 4=2*2).

Si vous n'avez absolument jamais entendu parler de nombres premiers, ne vous attardez pas dessus, retenez juste qu'il suffit de vérifier certaines conditions sur a, b et m pour avoir une période maximale.
Pour les autres qui en savent un peu plus, essayez vraiment de voir à quoi ces conditions correspondent, et tentez de montrer que les valeurs que l'on a prises au-dessus ne donnent pas une période maximale.
Pour les très forts en arithmétique, vous pouvez essayer de démontrer ce résultat (sans aller voir la démo sur Wikipédia ou équivalent, cela va sans dire...).

Si vous voulez voir comment vérifier effectivement ce critère, jetez un coup d'oeil au QCM, la correction est assez complète.

Maintenant, nous pouvons former un générateur à période maximale. Par exemple les valeurs : a=5, b=3, m=8 vérifient les 3 conditions ci-dessus et produisent la sortie suivante (c'est exactement le même programme, il suffit de changer les valeurs dans la première ligne du main) :

0 3 2 5 4 7 6 1 0 3 2 5 4 7 6 1

Tous les chiffres sont bien parcourus, la période est maximale, YOUHOU !!! Nous avons notre premier générateur aléatoire efficace !!!

Mais attendez, ce n'est pas fini ! Les nombres que nous utilisons là sont très petits. Quand on veut utiliser des nombres plus grands, d'autres problèmes apparaissent.

Minimisons la corrélation !

Encore un mot compliqué, mais comme d'hab, une signification pas bien sorcière : la corrélation entre deux nombres aléatoires peut être vue comme la capacité, connaissant un nombre, de déterminer le second.

Un exemple pour comprendre : on prend a=230 +1, b=3 et m=231. La sortie donne un truc du genre :

1073741832 1073741835 14 17 1073741844 1073741847 26 29 1073741856 1073741859 38 41

Si on fait attention, on remarque qu'on passe d'une valeur à l'autre en ajoutant 3 (écrivez à la main ce que ça donne, vous verrez). Les nombres sont donc fortement corrélés.

Il va donc falloir encore une fois trouver des critères qui nous permettent d'avoir une faible corrélation. Et encore une fois, on dit merci aux matheux :

  • m doit être le plus grand possible (en général, on veut profiter de tous les entiers disponibles, donc on prend 232-1 ou 231). C'est un truc qui nous arrange bien car cela permet d'avoir une période très longue ;

  • b doit être "petit" par rapport à a et m ;

  • a doit être proche de la racine carrée de m.

Dans l'exemple que j'ai pris juste au-dessus (a=230 +1, b=3 et m=231), a est très éloigné de la racine de m ; grâce à ce critère, nous aurions pu voir immédiatement que ce générateur était pourri !

Quelques bons générateurs

Voilà, maintenant, vous savez pratiquement tout sur les générateurs congruentiels linéaires.
Donc pour résumer, pour avoir un bon générateur, il faut avoir une période maximale et il faut que les coefficients respectent quelques règles. Si vous oubliez une des conditions, le générateur sera médiocre.

Je vais terminer cette partie en vous invitant à aller voir quelques "bons" générateurs utilisés par certaines librairies (j'ai choisi l'article anglais car l'article français est beaucoup moins bien fait) : article anglais sur les générateurs congruentiels linéaires sur Wikipédia (le coefficient que j'ai appelé 'b' est appelé 'c' dans cet article).

Une classe Aleatoire

Dans cette partie, nous allons mettre en pratique ce que nous avons appris. Comme je l'annonce depuis le début, nous allons tous ensemble construire cette classe Aleatoire.

Je vais être assez spécial vu que je vais vous demander de faire un générateur "paramétrable". Je veux que n'importe qui puisse définir un générateur congruentiel linéaire en testant différentes valeurs. Je veux en plus que cette classe soit indépendante, dans la mesure où elle devra elle-même initialiser la graine.

Essayez de la faire par vous-mêmes, il n'y a aucun "piège" particulier. Il s'agit juste de mettre dans une classe le code que l'on a tapé dans le main un peu plus haut.

Voici une correction possible.

Le fichier Aleatoire.h :

#ifndef _ALEATOIRE_H
#define _ALEATOIRE_H
#include <ctime>
class Aleatoire{
    private :
        unsigned int m_a,m_b,m_m; // Les coefficients du générateur
        unsigned int m_nombre;  // le nombre actuel généré
        
    public :
        Aleatoire(unsigned int a=16807,
                  unsigned int b=0,
                  unsigned int m=0x7FFFFFFF);
            // par défaut, le générateur prendra les valeurs du 
            // compilateur Apple CarbonLib
        int generer();
};

#endif

Et le fichier Aleatoire.cpp :

#include "aleatoire.h"

Aleatoire::Aleatoire(unsigned int a, 
                     unsigned int b, 
                     unsigned int m) : m_a(a),m_b(b),m_m(m){
    m_nombre = time(NULL);
}

int Aleatoire::generer(){
    m_nombre = (m_a*m_nombre + m_b) % m_m;
    return m_nombre;
}

Et voilà ! Une classe toute simple, prête à l'emploi !

Un petit main pour l'utiliser :

#include <cstdlib>
#include <iostream>
#include "aleatoire.h"
using namespace std;

int main(int argc, char *argv[])
{
    Aleatoire a(3,3,5);
    for(int i=0;i<15;i++){
        cout << a.generer()<<" ";
    }
    return 0;
}

Maintenant, vous pouvez tester très facilement les différents paramètres grâce au constructeur. Si vous voulez un générateur fonctionnel, laissez les paramètres par défaut.

Voilà, le tuto est fini ; voici quelques pistes pour approfondir le sujet !

Pour commencer, vous pouvez consulter l'article sur les générateurs de nombres pseudo-aléatoires.

Vous pouvez ensuite améliorer la classe Aleatoire (des pistes sur ce tuto):

  • créer une méthode generer(int min,int max) qui génère un nombre entre min et max ;

  • créer une méthode double genererDouble() qui génère un nombre réel entre 0 et 1 ;

  • vérifier que les coefficients donnent bien une période maximale (attention, ça demande un peu plus de temps que les deux autres améliorations).

Si vous êtes en Terminale S (ou que vous savez ce qu'est une loi), vous pouvez aussi regarder comment générer une loi aléatoire comme la loi normale, binomiale, de Poisson... et aussi une loi quelconque ! (Pour ça, voir la méthode du rejet et la méthode de l'inverse.) Ces méthodes se basent sur la génération de nombres qu'on fait ici (c'est-à-dire la loi uniforme), vous verrez. C'est par contre un peu plus poussé en maths (une piste ici) !

Si vous voulez aller vraiment plus loin (en dessous de bac +1 en maths, s'abstenir), vous pouvez essayer de comprendre la méthode de Mersen Twister qui permet d'avoir une génération encore meilleure.

Si vous voulez des applications de ce que l'on a fait, vous pouvez aller voir mon tuto sur la méthode de Monte Carlo qui est très utilisée en physique nucléaire.

Exemple de certificat de réussite
Exemple de certificat de réussite