RastellToull-C132-Les GenerateursPseudoAleatoires

Rastell Toull

Site web consacrée à la Bretagne,
à l'Afrique du nord
à la chanson française,
à la recherche scientifique,
et à bien d'autres sujets ...

Les générateurs pseudo-aléatoires

par Jacques-Deric Rouault

Article original

Page publique
Page en construction

Version 4.1 du
4 Mai 2012

Table générale
Administrateur du site

Comment citer ce document ?
Jacques-Deric Rouault, 2012. Les générateurs pseudo-aléatoires. Rastell Toull page C132.

Présentation

Dans toute opération de simulation sur ordinateur d'un processus matériel faisant intervenir le hasard, comme le tirage d'une boule dans une urne, on fait appel à un générateur pseudo-aléatoire.

Un générateur pseudo-aléatoire est une suite mathématique qui donne des valeurs réelles dans l'intervalle [0, 1] à distribution uniforme (ou rectangulaire). En particulier la connaissance d'une valeur de la suite ne doit pas pas permettre de deviner la valeur suivante. Il s'agit d'un processus à la fois déterministe et imprévisible qui, d'un point de vue épistémologiste, se rapproche de la théorie du chaos.

Propriétés

    De nombreux générateurs pseudo-aléatoires sont basés sur une fonction périodique, caractérisée par une période. Plus grande est la période, meilleur est le générateur.

     Suivant le loi des grands nombres, la distribution des valeurs dans l'intervalle dans [0, 1] doit tendre vers l'uniformité. Pour tester cela, on peut divisiser le segment unité en 1000 classes et calculer les effectifs pour chaque classe. Quand le nombre de valeurs augmente, le coefficient de variation (rapport de l'écart-type à la moyenne) doit tendre vers 0. En pratique, on atteint un plateau non nul, quand la période du générateur est atteinte.

    Un certain nombre de biais sont connus. Par exemple, une corrélation entre les valeurs de rang pair.

Les programmes d'évaluation

Présent que nous disposons d'une première série de nombres au hasard qui va nous servir de référence, nous allons définir différents programmes d'évaluation de la qualité du hasard ainsi généré.

Un million de chiffres au hasard

    En 1946-47, la Rand Corporation a fabriqué une machine électromécanique capable de générer au hasard des nombres de 5 chiffres. De ce que j'ai compris, il y a d'une part un générateur haute fréquence calibré sur 100 000Hz, d'autre part un générateur de bruit basé sur un tube 6D4 placé dans un champ magnétique. Un compteur de 5 chiffres binaires est entrainé par ces deux générateurs et sa valeur est relevée toutes les secondes. Le nombre binaire est converti en décimal et on ne retient que le chiffre des unités du nombre à 2 chiffres. Les tests effectués ont montré que les chiffres ainsi produits possédaient de bonnes propriétés de hasard.

    Ce tableau d'un million de chiffres est aujourd'hui directement accessible en ligne. On télécharge un gros fichier compacté de 663 943 octets qui s'appelle digits.txt.zip et qui contient lui-même un gros fichier texte de 1 440 000 octets qui s'appelle digits.txt.

    L'informatique que vous utilisons travaille avec des flottants simple précision construits à partir de 4 mots de 8 bits, soit 32 octets, ce qui correspond à environ 7 chiffres décimaux significatifs ou des flottants double précision construits à partir de 8 mots de 8 bits, soit 64 octets, ce qui correspond à environ 16 chiffres décimaux significatifs. Avec ce million de chiffres, nous allons construire autant de nombres flottants au hasard. Pour cela nous procédons de la façon suivante : nous prenons le tableau de chiffres, et nous les regroupons par paquets de 10, soit 100 000 paquets. Chaque paquet va coder un nombre entre 0 et 1, chacun des 10 chiffres du paquet codant autan de chiffres décimaux. Nous recommençons en introduisant un décalage en écartant le premier chiffre de la suite, puis les 2 premiers ... etc. Pour éviter des effets de bord indésirables, le début du fichier de chiffres sera recopié à la fin.

    Il est possible d'obtenir d'autres séries d'un million de nombre au hazard en considérant les chiffres par paquets de 7, 8, 9, 11, ... Il faut cependant faire attention à la taille des paquets par rapport au nombre de chiffres significatifs des flottants utilisés : ainsi, les paquets de 7 et de 14 chiffres auront en commun la moitié des valeurs ... La séquence pseudo-aléatoire s'en trouve biaisée.

    Le programme Ada RT_C132A2A1.adb lit le fichier texte digits.txt et en fait un gros fichier data de 1 000 050 octets de caractères RT_C132A2A3.dat. Les deux premières lignes du fichier originel sont répétées à l'envers pour chaque paquet de 5 à la fin du fichier pour compléter le fichier originel (car manque la dernière ligne) et éviter des effets de bord. En effet, si ces chiffres sont considérés comme étant au hasard dans l'ordre direct, il le seront également dans l'ordre inverse ...

        Le programme Ada RT_C132A2A4.adb lit le fichier data de un million de caractères RT_C132A2A3.dat créé à l'étape précedente. En groupant ces caractères par paquets de 10, et en introduisant un décalage de 0 à 9 positions dans la lecture du fichier de caractères, ce programme génère un million de nombres flottants à 10 chiffres significatifs dans le gros fichier data RT_C132A2A5.dat. Ce fichier est un fichier autolisible, avec trois flottants de plus, en début de fichier, qui décrivent la structure et la taille du fichier.

        Le programme Ada RT_C132A2A6.adb lit et affiche les 20 premières valeurs du gros fichier data autolisible RT_C132A2A5.dat.

Les décimales de Pi

    Pi est un nombre transcendant, ce qui se traduit par l'absence de régularité (périodicité) dans ses décimales. Comme on en connait aujourd'hui un grand nombre (5 000 milliards en 2010), il parait particulièrement judicieux de construire un générateur aléatoire à partir de cette suite de chiffres. Le premier problème est qu'il faut stocker toutes ces valeurs dans un fichier, et que cela se chiffre en tera-octets. C'est encore un peu juste pour les disques durs actuels.

    J'ai trouvé un fichier avec 100 millions de décimales de Pi (fichier Zip de 60 Mo) Le fichier lui-même, pi_100_millions.txt représente 136 178 581 octets.

    Le programme Ada RT_C132A3A1.adb lit le fichier texte pi_100_millions.txt et en fait un gros fichier data de 100 000 050 octets de caractères RT_C132A2A2.dat . La première ligne de décimales du fichier originel est répétée à l'envers pour chacun des 5 paquets de 10 chiffres à la fin du fichier pour éviter des effets de bord. En effet, si ces chiffres sont considérés comme étant au hasard dans l'ordre direct, il le seront également dans l'ordre inverse ...

        Le programme Ada RT_C132A3A3.adb lit le fichier data de 100 millions de caractères RT_C132A2A2.dat créé à l'étape précedente. En groupant ces caractères par paquets de 10, et en introduisant un décalage de 0 à 9 positions dans la lecture du fichier de caractères, ce programme génère 100 millions de nombres flottants à 10 chiffres significatifs dans le fichier data RT_C132A3A4.dat . Ce fichier est un fichier autolisible, avec trois flottants de plus, en début de fichier, qui décrivent la structure et la taille du fichier.

        Le programme Ada RT_C132A3A5.adb lit et affiche les 20 premières valeurs du gros fichier data autolisible RT_C132A3A4.dat.

Dans le même ordre d'idées, on peut également penser à d'autres nombres transcendants comme e (100 milliards de décimales connues en 2007) et C.

Les générateurs congruentiels linéaires

Les générateurs congruentiels linéaires sont définis par la suite mathématique d'entiers x(n+1) = (a*x(n)+b) mod c. Ces générateurs ont été définis en 1948 par Lehmer et se caractérisent par les trois constantes a, b et c et la graine x(0). Les valeurs de x sont comprises entre 0 et c-1.

Le choix des valeurs des 3 parametres sont essentielles, et ce type de générateurs produit de nombreux biais.

a	b	c	nom	source/auteur
65539	0	2^31	Randu	IBM 370
31415821	1	10^8		Robert Sedgewick
129	907633385	2^32		Turbo Pascal
1103515245	12345	2^31		Unix
16807	0	2^31-1	Standard minimal	Park & Muller
1664525	1013904223	2^32		Knuth & Lewis
69069	0	2^32		Marsaglia
31167285	1	2^48		Lavaux & Jenssens
6 364 136 223 846 793 005	1	2^64		Haynes

Il existe également d'autres familles de générateurs, comme les générateurs additifs, que nous ne détaillerons pas ici.

Le générateur de Wichmann et Hill

Le générateur de Wichmann & Hill publié en 1982 combine 3 générateurs conguentiels linéaires basés sur les nombres premiers 30269, 30307 et 30323.

Le programme RT_C132A4A1.adb implémente le générateur de Wichmann et Hill et affiche les 20 premières valeurs.

L'exécution du programme rt_c132a4a1.exe donne l'affichage suivant :

Le générateur de Wichmann & Hill a un cycle de 6.9536 10^12.

Le générateur Mersenne-Twister

Le générateur pseudo-aléatoire de Mersenne-Twister a été décrit par Matsumoto et Nishimura en 1998. Il utilise le 24e nombre de Mersenne 19 937. La mise en oeuvre de cet algorithme est assez complexe. Pour l'implémentation figurant ci-dessous, nous sommes partis du paquetage ADA Adammt19937 écrit par Adrian Hoe en 2002, plus précisément de la procédure random_3, et nous l'avons simplifié au maximum, de façon à l'intégrer comme une procédure dans le programme.

Le programme RT_C132A5A1.adb implémente le générateur Mersenne-Twister et affiche les 20 premières valeurs.

A faire à la maison sur grand ecran ...

Dans cette implémentation, au début de la fonction Marsenne-Twister, il y a un test de la valeur de la variable state.condition. Si celle-ci prend la valeur invalid, il est normalement prévu un traitement spécifique. Nous avons choisi de ne pas implémenter ce traitement et de lever une exception si cela se produisait. Un test d'exécution du programme sur plusieurs heures n'a pas permis de lever cette exception,ce qui indique que ce traitement n'est pas utile pour les applications courantes.

L'exécution du programme rt_c132a5a1.exe donne l'affichage suivant :

Le générateur Mersenne-Twister a une période de 2^19937-1, soit environ 10^5982

Casualisation des générateurs

Tels que ces générateurs sont conçus, il vont produire à chaque exécution la même suite de nombres. Il est des contextes où on souhaite répéter un grand nombre de fois la même simulation avec des suites différentes de nombres au hasard.

L'idée consiste à démarrer la suite de nombres produits non pas à partir du début, mais à partir d'un endroit quelconque de la liste, suivant un processus de casualisation. Pour déterminer le point de départ dans la liste, on utilise en général un processus externe sur lequel l'utilisateur n'a aucun controle. Cela peut être l'instant précis (en centièmes de secondes) où le programme est lancé, ou le délai mis par l'utilisateur pour frapper une touche.

Les générateurs physiques

    Aujourd'hui, il existe des dispositifs qui se connectent directement à un ordinateur et qui produisent des nombres aléatoires.

    Un ensemble de 6 lampes à lave sont numérisées par une caméra, et l'image est traitée par une fonction de hachage cryptographique, ce qui produit la graine du générateur pseudo-aléatoire Blum Blum Shub.

    Il existe également des cartes électroniques pour ordinateur qui générent des nombres aléatoires sur la base de mécanismes physiques : bruit d'une jonction électronique, désintégrations atomiques, bruit thermique, ... le bruit est échantillonné et convertiti sous une forme numérique. Il existe même une clé USB qui génère du hasard.

Sources

Liens internes

Autolien

Numéro	Article	Auteur	Rubrique	Sous-rubrique	Nature
C132	Les générateurs pseudo-aleatoires	Jacques-Deric Rouault	B41 Mathématiques B42 Informatique	Analyse numérique	Article original

Cette page utilise les articles

Numéro	Article	Auteur	Rubrique	Sous-rubrique	Nature
A3	Les gros fichiers
C137	Les fichiers autolisibles	Jacques-Deric Rouault	B42 Informatique		Article original

Articles utilisant cette page
Propriétés des GPA

Articles connexes

Page d'accueil
Table thématique
Table chronologique
Administrateur du site / Contact