Comment introduire l’aléatoire ?

Nous allons voir quelles fonctions permettent de générer des nombres pseudo-aléatoires, nous verrons plus loin la raison du pseudo. Continuons sur l’exemple du feu de camp, l’intensité n’est jamais la même. Si on prend comme référence la valeur de PWM [1] employée pour piloter une DEL qui simulerait un feu de camp, elle oscillerait par exemple entre 100 et 255. Il nous faudrait avoir donc un nombre aléatoire entre 100 et 255.

La bibliothèque de base fournit cette fonction qui s’appelle random(x, y). Elle accepte deux arguments. Ces deux arguments déterminent l’intervalle dans lequel la fonction random va tirer un nombre entier aléatoire selon une distribution uniforme, c’est à dire que tous les nombres entiers de l’intervalle ont la même probabilité d’être tirés. Le premier argument donne la borne inférieure de l’intervalle et le deuxième donne la borne supérieure de l’intervalle. La borne supérieure est exclue.

Par exemple :
random(100,256)

va donner un nombre aléatoire compris entre 100 et 255.

Les nombres passés en argument et retournés par random sont des long, c’est à dire des nombres entiers signés sur 32 bits. La valeur minimum possible est donc -2147483648, environ -2 milliards et la valeur maximum possible est 2147483647, environ 2 milliards.

Une autre forme de la fonction random existe. Elle ne prend qu’un seul argument et retourne un nombre aléatoire compris entre 0 et l’argument moins un.

Vous trouverez d’autres exemples dans la documentation de référence du site officiel de l’Arduino.

Attention au piège !

Il faut bien garder à l’esprit que la fonction random(...) n’est pas déterministe. Un piège dans lequel on peut tomber est de comparer une durée écoulée à la valeur retournée par random(...) en pensant que cette durée sera tirée aléatoirement et uniformément. Par exemple, si on désire faire clignoter une DEL à un rythme aléatoire [2] en utilisant millis(), on serait tenté d’écrire :

void setup() {
  pinMode(13, OUTPUT);
}
 
unsigned long dateDernierChangement = 0;
 
void loop() {
  unsigned long dateCourante = millis();
  if (dateCourante - dateDernierChangement > random(500, 3000)) {
    dateDernierChangement = dateCourante;
    digitalWrite(13, ! digitalRead(13));
  }
}

Le résultat est un rythme de clignotement qui n’est pas du tout aléatoire mais avec un délai de changement d’état d’environ 500, c’est à dire la borne inférieure utilisée pour random(...). Que se passe-t-il ? random(...) n’est pas aléatoire ? on m’aurait menti ?

En réalité, le programme est faux. Le programme appelle random(...) un grand nombre de fois en très peu de temps car la durée d’exécution de loop est d’environ 90µs. Par conséquent en 50 ms, un peu plus de 550 appels à random(...) sont fait. On a par conséquent, du fait de la grande quantité de tirages, une forte probabilité de tirer un nombre proche de 500 avec pour résultat de rendre rapidement le test vrai.

Il faut donc procéder de la manière suivante :

unsigned long dateDernierChangement = 0;
unsigned long delaiAleatoire;
 
void setup() {
  pinMode(13, OUTPUT);
  delaiAleatoire = random(500, 3000);
}
 
void loop() {
  unsigned long dateCourante = millis();
  if (dateCourante - dateDernierChangement > delaiAleatoire) {
    dateDernierChangement = dateCourante;
    delaiAleatoire = random(500, 3000);
    digitalWrite(13, ! digitalRead(13));
  }
}

De cette manière le délai est tiré une seule fois et rangé dans la variable delaiAleatoire pour être ensuite utilisé. On obtient un rythme de clignotement qui est bien aléatoire avec des délais répartis uniformément dans l’intervalle [500 ; 3000[.

Les applications

Les applications sont diverses. On peut envisager des animations lumineuses simples comme un feu de camp, un braséro, un atelier de soudure à l’arc ou encore l’allumage et l’extinction de l’éclairage des maisons individuelles qui de plus est assujetti à l’heure simulée sur le réseau.

On peut également imaginer la génération d’itinéraires ou la simulation de retards sur le réseau de manière à éviter la répétition des circulations : quel train va démarrer ? sur quelle voie va-t-il arriver ? etc.

Chaque utilisation sera vue dans de futurs articles mais à titre d’exemple, voici une simulation de feu de camp. Le programme fait varier l’intensité d’une DEL branchée sur la sortie PWM 3, voir à ce propos « La PWM : Qu’est-ce que c’est ? (1) ». L’intensité varie d’une intensité initiale à une intensité finale, cette dernière étant aléatoire. La variation d’intensité est effectuée pendant une durée également aléatoire. On y retrouve également des techniques de gestion du temps vues dans « Comment gérer le temps dans un programme ? »

const byte pinDEL = 3;
 
void setup() {
}
 
byte intensiteDepart = 100;
byte intensiteArrivee;
float variationIntensite;
unsigned int dureeChangement;
unsigned long dateDebutChangement;
bool changementTermine = true;
 
void loop() {
  if (changementTermine) {
    // Calcule une nouvelle variation d'intensité lumineuse
    // tire aléatoirement une duree de changement en ms
    dureeChangement = random(20, 250);
    dateDebutChangement = millis();
    // tire aléatoirement une intensité cible
    intensiteArrivee = random(5, 200);
    // calcule la variation de l'intensité par unité de temps
    variationIntensite = (float)(intensiteArrivee - intensiteDepart) /
                         (float)dureeChangement;
    // lance la variation d'intensite
    changementTermine = false;
  }
  else {
    byte tempsEcoule = millis() - dateDebutChangement;
    if (tempsEcoule < dureeChangement) {
      // en cours de variation d'intensité
      byte intensite = variationIntensite * tempsEcoule + intensiteDepart;
      analogWrite(pinDEL, intensite);
    }
    else {
      changementTermine = true;
      intensiteDepart = intensiteArrivee;
    }
  }
}

Est-ce vraiment aléatoire ?

Le but est que la suite de nombre générées ait l’apparence de l’aléatoire. On pourrait faire passer à la suite une série de tests statistique mais ça serait un peu compliqué à mettre en œuvre et à expliquer. Une façon simple de procéder est de visualiser les nombres générés dans une matrice où chaque nombre a une coordonnée et où sa valeur est une couleur ou un niveau de gris. L’œil humain distinguera alors immédiatement une régularité dans la suite. Le générateur du logiciel Arduino produit un bon résultat comme on peut le voir sur la figure ci-dessous. 40000 nombres on été tirés et sont affichés dans une matrice 200x200.

Pourquoi un pseudo-aléatoire ?

Venons-en à un point important : le pseudo-aléatoire.

Le calcul du nombre que retourne random n’est en fait pas vraiment aléatoire. Il repose sur un algorithme qui génère une suite de nombres. Chaque nombre est issu d’un calcul impliquant les nombres générés préalablement. Si cette suite de nombre a des propriétés semblables à une suite de nombres aléatoires, elle est donc en réalité déterminée par la valeur d’initialisation. Par défaut, cette valeur est toujours la même. Par conséquent la suite de nombre sera toujours la même.

Ce n’est pas forcément génant. Dans le cas d’une simulation de feu de camp, le fait d’avoir systématiquement la même séquence à l’allumage n’est pas un problème. Ce qui nous intéresse pour cette application est que l’observation de l’animation lumineuse ne laisse pas voir de régularité. Par contre pour une circulation aléatoire des trains, il sera très agaçant d’observer exactement la même séquence à l’allumage du réseau.

Une fonction permet de changer cette valeur d’initialisation, il s’agit de la fonction randomSeed(...). Cette fonction est à appeler une fois dans setup(). Mais changer cette valeur d’initialisation avec un nombre fixe ne règle en rien le problème, il faut fournir une valeur d’initialisation du générateur qui soit raisonnablement aléatoire.

Une solution aisée est d’utiliser une broche analogique, A0 par exemple qui sera laissée en l’air. La conséquence est que cette broche va attraper des valeurs plus ou moins aléatoires au gré de l’environnement électromagnétique. La fonction analogRead(...) permet de lire cette valeur supposée changeante et retourne un nombre entier compris entre 0 et 1023. Cette méthode est recommandée dans la documentation de l’Arduino et reprise dans nombre d’articles sur le Web (Openclassroom, tutorials point, programming electronics). Malheureusement la valeur fournie par une lecture de la broche analogique n’est en rien aléatoire. Sur un Arduino Uno, 380000 appels à analogRead(...) produisent la répartition présentée à la figure suivante.

On voit que plus de 17% des valeurs sont des 0, que le maximum est d’environ 150 et que les tirages ne sont pas équiprobables, avec un pic aux alentour de 254.

C’est pire sur le Due. Un million de lectures de l’entrée analogique A0 retourne pour 2/3 des lectures la valeur 507 et pour 1/3 la valeur 508. Le fait de mettre un fil d’une douzaine de centimètre sur A0 pour obtenir un effet d’antenne élargit un peu la distribution. Il apparaît également que, lors d’une séquence d’appel de analogRead(...), la première valeur est située vers 830, du moins pour la température du micro-contrôleur au moment du test, et qu’au fur et à mesure de l’utilisation du convertisseur analogique numérique et de sa montée en température la valeur lue converge vers 507.

Conclusion : initialiser le générateur de nombres aléatoires avec analogRead(...) n’est pas viable. Il nous faut trouver un meilleur moyen.

Un meilleur randomSeed

Une première solution est de construire la valeur d’initialisation en effectuant plusieurs appels à analogRead(...) pour ne conserver que le bit de poids faible et de construire une valeur par concaténation de ces bits, voir l’article « Calculer avec l’Arduino (2) ». Par exemple pour construire une telle valeur sur un octet, on écrirait :

byte getSeed()
{
  byte seed = 0;
 
  for (byte i = 0; i < 8; i++) {
    seed = (seed << 1) | (analogRead(A0) & 1);
  }
  return seed;
}

De cette manière, une faible variation de la valeur retournée par analogRead(...) se traduit pas une variation certaine du bit de poids faible.

Voici la distribution des valeurs retournées par un million d’appels à getSeed().

C’est un peu mieux mais le grand nombre de lectures donnant 0 produit un grand nombre de seed également égaux à 0.

Une seconde solution est d’utiliser une méthode simple proposée par John Von Neumann dans un papier intitulé Various techniques used in connection with random digits et publié en 1951 dans Applied Math Series 12:36-38. Elle consiste à former des couples de deux bits successifs. Si les deux bits sont identiques, ils sont ignorés. Si les deux bits sont différents, alors le résultat est le premier des deux bits. Cette méthode élimine les biais. La fonction getSeed() devient donc :

byte getSeed()
{
  byte seed = 0;
  byte i = 8;
  while (i > 0) {
    byte firstBit = analogRead(A0) & 0x01;
    byte secondBit = analogRead(A0) & 0x01;
    if (firstBit != secondBit) {
      seed = (seed << 1) | firstBit;
      i--;
    }
  }
  return seed;
}

La distribution des valeurs retournées par un million d’appels à getSeed() est donnée dans la figure suivante.

Les deux pics situés au 1/3 et au 2/3 ne sont pas caractéristiques. Une seconde exécution du même programme produit la distribution suivante où ces deux pics sont absents.

On a donc bien en utilisant cette méthode une valeur d’initialisation satisfaisante.

On peut également noter que si vous avez omis de laisser l’entrée analogique employée libre, la valeur que retournera analogRead(...) sera constante et que, par conséquent, l’algorithme de Von Neumann ne terminera pas.

Pensez aussi à brancher sur cette entrée analogique un fil qui jouera le rôle d’une antenne et engendrera des valeurs plus dispersées. Ça améliorera la construction d’une bonne valeur d’initialisation pour le générateur de nombres aléatoires.