Les ordinateurs sont des machines déterministes, même si on peut parfois en douter ! Ils sont ainsi très mauvais au jeu des valeurs aléatoires, comme nous, mais pour d’autres raisons (trop de rigidité pour les premiers, trop de poids de l’inconscient pour les seconds). Peut-on se fier à Random ? Comment l’utiliser ? Peut-on mieux faire ? Nous allons voir cela …
L’aléatoire
C’est une notion … complexe.
Il ne faut d’ailleurs pas confondre l’aléatoire et le chaos qui est un autre concept. En informatique ce qu’on cherche le plus souvent c’est la génération de nombres aléatoires sans trop se poser de questions… ce qui n’est pas malin !
Mais supposons que nous ayons un tel groupe de nombres aléatoires. Une fois cela en poche on peut tout aussi bien générer des couleurs aléatoires ou des chaînes de caractères ayant cette propriété et c’est ce qui intéresse l’informaticien quand il pense “nombre aléatoire”. En matière de programmation on pourrait ainsi affirmer “ici tout est nombre !” car on sait transformer les nombres en n’importe quoi, musique, image…l’inverse étant vrai (c’est même à cela qu’on doit l’essor du “digital”).
Beaucoup de définitions savantes ont été données au fil du temps à cette notion d’aléatoire.
Mais au final nous en sommes revenus…
Ce que nous appelons “aléatoire” est en réalité une forme de “complexité” puisque la prédiction n’est pas possible. Kolmogorov nous a expliqué ce qu’il entendait par la “complexité aléatoire” qu’il a réduit a sa plus simple expression, la taille du programme nécessaire pour reproduire un contenu, une information. Plus le programme est court et moins l’objet est complexe. Lorsque le programme le plus court consiste à simplement recopier la donnée cela indique que sa complexité est maximale et que rien ne permet de simplifier, de compresser l’information véhiculée.
Complexité et nombre aléatoires sont deux choses différentes, mais un nombre réellement aléatoire est par définition complexe car rien ne permet d’en prédire ou d’en calculer les chiffres. Il n’y a pas de programme plus court que celui qui consiste à le recopier.
D’ailleurs un “nombre aléatoire” qu’est-ce que cela veut dire ? Un nombre peut-il être “aléatoire” comme il peut être pair ou premier ? Non bien sûr, un “nombre aléatoire” est une forme d’abus de langage. C’est une série de nombres qui peut l’être. Un nombre tout seul ne peut être qualifié d’aléatoire. Il faut donc entendre par “nombre aléatoire” un élément d’une série aléatoire de nombres. La complexité se jugera ainsi sur la série et non sur un seul nombre. Mais on peut aussi considérer un nombre comme une série de chiffres et tenter de juger de sa complexité sous cet angle.
Les nombres peuvent parfois être très grands, voire infini, et même ne présenter aucune régularité tout en étant peu complexe ! Prenez le cas de Pi par exemple. Il présente une infinité de décimales, aucun schéma répétitif n’a pu être détecté bref ça semble être du lourd niveau complexité, et bien non.. Car face à l’infini de sa taille, on peut opposer un très court programme qui calcule Pi. Cela peut demander du temps, mais cela prouve que Pi n’est pas complexe puisqu’on peut le “compresser” en quelques lignes de programmation… Certes calculer les décimales va être long, mais cela ne change rien à la faible complexité de Pi. Oui l’infini c’est long, surtout vers la fin, mais ce n’est pas un critère de complexité.
En théorie de l’information on est même allé encore plus loin. Il ne s’agit même plus d’écrire un programme pour reproduire une donnée et d’en jauger la taille par rapport à celle-ci, il suffit d’utiliser … Zip !
La complexité aléatoire d’une information peut se mesurer ainsi à la taille du fichier produit par Zip (entendez un programme de compression réputé efficace peu importe son nom)…
Prenez deux cents pages A4 remplies d’espaces (ASCII 32), prenez 7Zip… le fichier final sera largement plus petit que le document original c’est une évidence (si vous en doutez, faites le test !). En revanche prenez le même document de 200 pages contenant toutes les décimales de Pi que vous pourrez y placer… le fichier compressé final ne sera pas plus petit que votre document original (un simple fichier texte sans artifice).
La nature aléatoire d’une donnée peut se mesurer à sa complexité interne, et cette complexité peut se calculer soit en écrivant un programme qui reproduit la donnée, soit tout simplement en essayant de zipper la donnée ! Pour être totalement précis la complexité de Komogorov est parfaitement définie mais elle n’est pas calculable (au sens mathématique, pas par ignorance). Mais ne nous écartons pas trop du fil aléatoire de cet article…
La nature aléatoire d’un nombre et sa complexité restent des notions différentes mais elles peuvent donc se rejoindre au moins pour juger de la qualité des données.
Il faut aussi savoir séparer la complexité aléatoire de la complexité organisée. Une information peut très bien avoir une complexité organisée élevée mais un complexité aléatoire faible ou l’inverse ou les deux ou aucune… L’exemple de Pi plus haut montre qu’il n’est pas désordonné, sa structure nous est cachée et nous apparait aléatoire mais il existe une organisation forte puisqu’on peut résoudre son infinité à un calcul de quelques lignes. Pi a une haute complexité organisée mais une faible complexité aléatoire (puisqu’on peut prédire avec précision la valeur de n’importe quelle décimale). C’est un fait troublant car en même temps la suite de chiffres de Pi est selon toute évidence aléatoire ! Mais rassurez-vous même pour les spécialistes la séparation entre complexité organisée et complexité aléatoire n’est pas forcément évidente à faire tout le temps.
Les générateurs de nombres aléatoires se “mesurent” d’ailleurs plutôt à l’aide d’outils statistiques. Car tout dépend de ce qu’on cherche, la complexité ou une certaine distribution ce qui n’a rien à voir bien entendu. Le générateur aléatoire le plus sobre qu’on puisse vouloir est celui où tous les nombres ont une équiprobabilité d’apparaître. La moyenne est idéalement de Max/2 avec une grande variance. Mais on peut aussi vouloir utiliser des “nombres aléatoires” suivant une distribution particulière comme celle d’une courbe de Gauss ou de n’importe quelle fonction.
La non prédictibilité et la complexité ne font pas bon ménage… Car plus on veut suivre une loi de distribution plus on introduit un biais fort dans le tirage qui est de moins en moins aléatoire… Par exemple des tirages aléatoires suivant une loi de répartition normale permettent avec certitude d’écarter de nombreuses valeurs (celles qui n’appartiennent pas à l’aire de la fonction).
Il y a de fait une confusion à éviter entre la complexité d’un tirage au sort et sa loi de distribution qui trahit certaines caractéristiques de l’ensemble ce qui rend les données prévisibles. Prévisible != Aléatoire…
Ordinateurs et nombres aléatoires
Un ordinateur étant une machine déterministe (même si certains bogues peuvent parfois nous en faire douter !) l’aléatoire est totalement hors du champ de ses possibilités, quelle que soit sa taille, sa puissance, sa mémoire ou la présence d’un coprocesseur mathématique (dont on ne parle plus depuis quelques années puisque systématiquement intégré aux CPU ce qui ne fut pas le cas pendant longtemps).
Au mieux, il produira une suite de nombres “pseudo aléatoires” répondant à certains critères (c’est à dire simulant au plus proche certaines courbes ou lois comme celle de Poisson ou d’autres formes de distribution).
Les nombres aléatoires ne peuvent ainsi être générés qu’en s’appuyant sur des phénomènes physiques eux-mêmes réputés aléatoires comme les phénomènes quantiques. C’est pour cela que pour générer des vraies séries de nombres aléatoires sur un ordinateur il faut absolument utiliser un hardware spécifique. Il en existe de différentes nature selon le degré de précision dans l’aléatoire qu’on désire (s’il est possible de parler de précision ici). Ces boitiers qui peuvent se brancher sur un port USB par exemple, utilisent des phénomènes quantiques qu’ils amplifient et numérisent pour obtenir des nombres : bruit thermique d’une résistance par exemple.
Donc hors de ces hardwares, parler de nombres aléatoires avec un ordinateur est un abus de langage dans le meilleur des cas et une hérésie mathématique dans le pire…
.NET et Random
Tout le monde la connaît cette classe du framework, c’est le moyen le plus simple d’obtenir des nombres pseudo aléatoires sous .NET.
Mais de ce que j’ai toujours pu constater lorsque j’audite du code, cette classe est mal utilisée dans la grande majorité des cas. Cela était vrai il y a des années, cela reste vrai aujourd’hui. Tout comme la compréhension des bases de données rationnelles (Formes Normales, loi de Codd…) semble restée bloquée à l’ère de DBase II, la compréhension de Random n’a pas évoluée en 10 ans.
Il y a par exemples des erreurs classiques qui montrent cette méconnaissance des principes fondamentaux de Random.
La première consiste à vouloir initialiser l’instance avec l’heure courante comme pour augmenter la nature aléatoire des données qui seront générées. C’est une bévue. La classe Random utilise déjà l’horloge comme graine si on n’utilise son constructeur par défaut…
Inutile donc d’écrire
var r = new Random(DateTime.Now.Millisecond);
Cela ne sert à rien.
Autre erreur classique, multiplier les instances pour des tirages différents en espérant gagner “en aléatoire”…
Le pire que j’ai pu voir dans ce style est une série de Random instanciées l’une derrière l’autre. Si les créations sont réellement à la suite ou peu espacées il y a toutes les chances qu’elles soient initialisées avec la même heure qui a une résolution de 20 ms environ ! Et toutes les instances de Random produiront alors …. exactement la même série de nombres !
Une seule instance suffit
Il ne sert donc à rien de multiplier les instances de Random dans une application en espérant avoir “plus” d’aléatoire au final. Bien au contraire on risque d’obtenir, comme l’exemple ci-dessus le démontre, une uniformité qui n’a vraiment plus rien d’aléatoire, même “pseudo” !
Si les exigences mathématiques sont assez faibles on peut parfaitement se contenter de Random. Mais alors, le plus malin consiste à créer une seule instance pour toute l’application. On s’assure bien ainsi que chaque run de l’application se basera sur une série différence et surtout qu’au sein de l’application tous les nombres sembleront bien être aléatoires...
Je vous passe l’exemple d’une classe statique déclarant une instance de Random et exposant des méthodes statiques calquant les méthodes principales de cette dernière. C’est enfantin.
Bref, la façon la plus simple d’avoir réellement des nombres pseudo aléatoires dans une application est de n’utiliser qu’une seule instance centralisée de Random. La classe n’est pas garantie “thread safe” donc si vous l’utiliser dans un contexte multithread le mieux est soit d’avoir une instance par thread. L’idée de créer un wrapper statique utilisant des locks pourrait être séduisante pour certains mais franchement je vous le déconseille, cela créera un goulet d’étranglement écroulant en partie l’avantage du multithreading.
Complexité, aléatoire et Random
C’est ici que les deux histoires se rejoignent…
Random génère toujours la même séquence pour la même graine, ce qui n’est déjà pas très aléatoire comme fonctionnement. De plus les séries produites - puisque dépendantes de la graine - sont forcément issues d’un processus calculatoire tout à fait prédictible pour un spécialiste. Utiliser Random pour des opérations sensibles notamment touchant à la sécurité serait ainsi une grave erreur…
Pour cela il existe le namespace System.Security.Cryptography.
Ce namespace, comme son nom le laisse deviner, contient de nombreuses classes fort utiles en cryptographie. Et qui dit cryptographie dit nombres (pseudo) aléatoires. Mais comme il s’agit ici de sécurité les exigences mathématiques placent la barre un peu plus haut. Même si la qualité ne peut rivaliser avec du hardware spécialisé, elle dépasse de loin celle de Random.
Loin de moi l’idée d’aborder le contenu de ce namespace en quelques lignes. Je veux juste attirer votre attention sur son existence et qu’on y trouve un générateur qui remplace Random de façon plus efficace en évitant le risque de répétition des valeurs si plusieurs instances doivent être créées de façon proche dans le temps. Entre autres choses.
Il suffit d’utiliser RNGCryptoServiceProvider du namespace indiqué.
Cette classe permet de créer des instances de RandomNumberGenerator offrant un comportement plus fiable que Random. Il faut utiliser une instance par thread comme Random.
Quelle complexité aléatoire attendre ? Si on utilise la méthode de la compression, Random et RNG ont une complexité assez proche. Faites tourner le petit programme ci-dessous pour vous en convaincre (mode Programme C# dans LinqPad ou faites le tourner dans VS en mode console).
En revanche on obtient des séries ayant une meilleure distribution des valeurs produites et une prédictibilité bien moins grande qu’avec Random.
void Main()
{
var r = new Random();
var t = new double[10000];
for (var i = 0; i < 10000; i++) t[i] = r.NextDouble();
//for (var i = 0; i < 10000; i++) t[i] = NextRandomDouble();
//for (var i = 0; i < 10000; i++) t[i] = 1;
Console.WriteLine($"Taille tableau: {sizeof(double) * 1000}");
var tc = SerializeAndCompress(t);
Console.WriteLine($"Taille tableau compressé: {sizeof(Byte) * tc.Length}");
var tdc = DecompressAndDeserialize<double[]>(tc);
Console.WriteLine($"Taille tableau décompressé: {sizeof(double) * tdc.Length}");
}
// Define other methods and classes here
public static byte[] SerializeAndCompress(object obj)
{
using (MemoryStream ms = new MemoryStream())
{
using (GZipStream zs = new GZipStream(ms, CompressionMode.Compress))
{
BinaryFormatter bf = new BinaryFormatter();
bf.Serialize(zs, obj);
}
return ms.ToArray();
}
}
public static T DecompressAndDeserialize<T>(byte[] data)
{
using (MemoryStream ms = new MemoryStream(data))
{
using (GZipStream zs = new GZipStream(ms, CompressionMode.Decompress, true))
{
BinaryFormatter bf = new BinaryFormatter();
return (T)bf.Deserialize(zs);
}
}
}
public static double NextRandomDouble()
{
var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
var bytes = new byte[8];
rng.GetBytes(bytes);
var ul = BitConverter.ToUInt64(bytes, 0) / (1 << 11);
return ul / (Double)(1UL << 53);
}On trouvera dans ce code quelques idées annexes qui pourront vous intéresser comme la sérialisation + compression (et son inverse) en mémoire des données utilisant GZip (du framework .NET).
Quand utiliser RandomNumberGenerator plutôt que Random ?
Les réponses seront assez simples :
L’intention
Si votre code n’a rien à voir avec la sécurité et que la qualité des nombres aléatoires n’a pas grande influence utilisez Random, sinon utilisez RandomNumberGenerator on comprendra alors que vous tenez à utiliser un générateur plus pointu.
La rapidité
Si les tirages au sort sont nombreux et peuvent gêner l’exécution de votre programme préférez Random car il est beaucoup plus rapide que RandomNumberGenerator, sauf bien sûr si la sécurité est un point important.
La distribution des nombres
La classe Random ne produit pas un spectre très homogène. Si vous désirez des nombres aléatoires mieux répartis utilisez RandomNumberGenerator.
La répétabilité
C’est un comble ! Mais oui la répétabilité peut être une bonne raison (mais une bien mauvaise publicité !) de préférer Random… Pour produire des tests identiques il peut s’avérer très intéressant d’utiliser les défauts de Random en prenant soin d’utiliser toujours la même graine lors de la création de l’instance. Ainsi new Random(5); produira à coup sûr la même séquence à chaque exécution. Elle sera différente de celle produite en utilisant une autre graine et la série aura toujours l’apparence de l’aléatoire. Mais cette répétition des mêmes séquences pour les mêmes graines peut s’avérer très utile !
Conclusion
Il y aurait bien d’autres choses à dire sur les nombres aléatoires, pseudo ou non. C’est un sujet passionnant. Mais le but était principalement d’attirer votre attention sur les bonnes et les mauvaises utilisations de Random et vous signaler l’existence dans le Framework d’autres classes plus “pointues” pour produire des séries pseudo aléatoires. La mauvaise maîtrise des outils du framework n’est pas un tort en soi, on a tous quelque chose à apprendre, tous les jours. Mais quand je vois les mêmes erreurs se reproduire années après années je me dis que l’information a du mal à passer et que c’est dommage.
Stay Tuned !