Les générateurs de nombres aléatoires [Tutoriel]

[ram-0000]

Bonjour à tous !

La rubrique Mathématiques vous propose un article sur la génération des nombres pseudo aléatoires écrit par yahiko : les générateurs de nombres aléatoires.

Cet article est une présentation de diverses méthodes pour générer des nombres pseudo-aléatoires.

N'hésitez pas à faire part de vos remarques, commentaires ou propositions d'améliorations !

Les générateurs de nombres aléatoires

[yahiko]

Cela est sans doute passé inaperçu, mais depuis la version de Chrome 49, la fonction Math.random() génère de bien meilleurs nombres pseudo-aléatoires.

L'algorithme jusqu'à cette version 49 était un LCG nommé MWC1616.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
uint32_t state0 = 1;
uint32_t state1 = 2;
uint32_t mwc1616() {
  state0 = 18030 * (state0 & 0xffff) + (state0 >> 16);
  state1 = 30903 * (state1 & 0xffff) + (state1 >> 16);
  return state0 << 16 + (state1 & 0xffff);

Mais comme tous les LCG, il souffrait intrinsèquement de certaines régularités qui devenaient visibles au bout d'un certain nombre d'itérations.

Désormais, V8 de Chrome utilise l'algorithme XorShift128+. Ce qui est amusant de noter, c'est que ce changement chez Google a poussé Mozilla et Safari a faire de même, ce qui réduit la nécessité d'utiliser un autre générateur de nombres aléatoires que celui par défaut. Et on ne s'en plaindra pas.

source : Blog officiel de V8

[Aiekick]

Bonjour,

j'avais pensé a un système pour avoir des nombre plus aléatoire que les algorithme classique, mais j'ai jamais prit le temps de le faire et vérifier mon assertion.

l'idée était d'écouter le port série du pc et de ce servir de ce bruit "pensé plus aléatoire" pour générer des nombres aléatoire ?

vous pensez que c'est viable, ou le bruit généré par le post série qui ne serait connecté a rien ne donnerai rien de bien. pareil pour le micro ?

[yahiko]

Je ne connais pas très bien le niveau d'aléatoire (entropie) du bruit d'une prise série ou celui d'un micro, mais ce genre de systèmes existent déjà pour générer des nombres aléatoires. Certains générateurs de nombres aléatoires utilisent même le "bruit" du courant électrique au niveau d'un transistor. Mais il me semble que l'aléatoire produit ainsi n'est pas vraiment parfait dans la mesure où cela reste de la physique "classique" et donc plus ou moins déterministe, on n'a simplement pas assez d'informations. L'idéal reste donc de réaliser des mesures à un niveau quantique où le hasard n'est pas une propriété émergente, mais est réellement intrinsèque aux phénomènes observés.

[Othana]

Je ne connais pas très bien le niveau d'aléatoire (entropie) du bruit d'une prise série ou celui d'un micro, mais ce genre de systèmes existent déjà pour générer des nombres aléatoires. Certains générateurs de nombres aléatoires utilisent même le "bruit" du courant électrique au niveau d'un transistor. Mais il me semble que l'aléatoire produit ainsi n'est pas vraiment parfait dans la mesure où cela reste de la physique "classique" et donc plus ou moins déterministe, on n'a simplement pas assez d'informations. L'idéal reste donc de réaliser des mesures à un niveau quantique où le hasard n'est pas une propriété émergente, mais est réellement intrinsèque aux phénomènes observés.

On pourrait utiliser, comme précisé en début d'article, les mouvements de souris, en particulier les coordonnées du pointeur au click sur le bouton OK ou à l'appuie de la touche Entrée (après avoir saisi la seed).
Donc, randomSeed + coord souris y + coord souris x (ou *, ou autre formule, pour les plus sadiques).

J'ai dévoré l'article.

Alors j'ai deux points de discussion en tête.
D'abord, au sujet des chapitres 6 et 7, où l'alogo présenté en 7 est décrit comme plus "naturel" que le 6, avec exemple d'un univers généré. Le souci, c'est que l'on sait maintenant que l'Univers connu ressemble plus à ce que donne l'algo du 6. Voir ici http://www.nationalgeographic.fr/293...s-de-lunivers/

Second point, et si, au sein de l’algorithme, on ajoutait encore une composante random ?
Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
var randomSeed = Date.now(); 
function randCLib(): number {
  randomSeed = randomSeed * 1103515245 + 12345;
  randomSeed = (Rand(randomSeed) / 65536) % 32768; 
 
  return randomSeed / 32767.0; }// randCLib

Bon, pour être précis, j'ai dans l'idée d'utiliser un nombre aléatoire Rand() pris entre 1 et randomSeed. Je ne sais pas exactement comment l'écrire, là, tout de suite (je sais surtout le faire en basic, pour créer des tirage d'entiers, afin de simuler un lancé de dé).

De toute façon, il faut bien se dire que, dans la nature ou le reste de l'univers, l'aléatoire n'existe pas. Tout est déterminé. Mais déterminé par tellement de composants visibles et invisibles qu'il est juste humainement impossible de les traiter tous, afin de déterminer le résultat final.
Et pourtant, l'état d'un événement ou la position d'une chose à l'instant T sera toujours le résultat de l'influence d'un vaste ensemble d'autres événements : vent, humidité, vibrations, température, pression, altitude, perturbations de diverses natures causées par un autre événement (passe de voiture, abeille qui se pose ou qui frôle, gaz d'échappement d'un véhicule au feu rouge, etc...), etc., etc., etc. le tout se répercutant l'un l'autre et pouvant se propager très loin et donc influencer encore un autre événement, etc, etc, etc...
Ce qu'on appelle la théorie du Chaos, le papillon qui bat des ailes à Tokyo et qui provoque un orage à New-York.
Du coup, en y réfléchissant bien n'importe quelle formule est donc plus ou moins réaliste. Sa capacité à refléter la réalité dépend juste de sa complexité.
Le mieux, serait une formule qui, au lieu de prendre des nombres définis comme ici

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
var randomSeed = Date.now(); 
// Xorshift initialization
var x = 123456789;
var y = 362436069;
var z = 521288629;
 
function randXorshift(): number {
  var t = (x ^ (x << 11)) & 0x7fffffff;
  x = y;
  y = z;
  z = randomSeed;
  randomSeed = (randomSeed ^ (randomSeed >> 19) ^ (t ^ (t >> 8))); return randomSeed /2147483648.0;

prendrait des paramètres passés par l'utilisateur (si on lui laisse la maîtrise sur les événements de son monde) ou par le monde lui-même (ou les conditions particulières à l'instant T/l’itération i).

Oh bon sang... Je viens juste d'imaginer un algo...
Vraiment bon, cet article !

[yahiko]

Cela me fait plaisir que vous ayez apprécié l'article sur les générateurs de nombres aléatoires.

Pour répondre succinctement aux questions soulevées :

1) L'exemple d'univers présenté en fin d'article n'a aucune prétention de décrire une quelconque réalité mais juste de montrer en quoi mémoriser une graine peut permettre de régénérer un même univers, sans avoir à stocker l'ensemble des coordonnées aléatoirement générées au préalable.

2) Rendre la graine aléatoire est quelque chose qui est pratiqué dans certaines situations. Tout est permis, même s'il faut bien avoir en tête que l'algorithme reste pseudo-aléatoire et que rendre la graine aléatoire n'améliorera pas la qualité statistique des nombres produits, ni réduira le risque de pouvoir prédire les nombres aléatoires générés (par des individus malveillants par exemple).

3)

De toute façon, il faut bien se dire que, dans la nature ou le reste de l'univers, l'aléatoire n'existe pas. Tout est déterminé. Mais déterminé par tellement de composants visibles et invisibles qu'il est juste humainement impossible de les traiter tous, afin de déterminer le résultat final.

Jusqu'à preuve du contraire, les lois de la physique quantique stipulent bien que certains phénomènes quantiques sont réellement aléatoires et ne dépendent pas de paramètres qui nous seraient cachés par manque d'information (cf. débat entre Bohr et Einstein). Ce n'est qu'au niveau macroscopique que l'aléatoire intrinsèque de la physique quantique disparaît pour laisser place à des moyennes qui elles deviennent parfaitement déterministes.

[Othana]

Mais là, on va sortir le cas du chat de Schrödinger. Mais j'ai jamais accepté cet exemple. Le chat n'est pas soit mort, soit vivant : Sauf avoir sauté dessus à pieds joints, le chat est toujours aussi vivant qu'à l'entrée. Schrödinger n'avait qu'à s'y mettre lui-même dans la boite, il aurait bien vu. Ce qui pourrait changer la donne, et donc donner une courbe temporelle parallèle, c'est que des événements influents différents interviennent : On décide soudainement de sauter sur le carton où est enfermé le chat. Après ça n'a peut-être rien à voir, au final.

Bref, pour en revenir au générateur, je me souviens d'anciens jeux qui permettaient au joueur de changer des paramètres, comme je le propose, mais ces changements étaient intégrés à la seed. Or moi, j'imagine plutôt faire varier la formule elle même. Si on considère que la seed est le postulat de base d'une certaine situation à un instant T et la formule représente alors tout ce qui fera varier le postulat de base pour donner la succession d’événements suivants, alors ce sont les paramètres/données de la formule qui doivent varier. Et on pourrait même pousser plus loin en imaginant que les paramètres de base, qui ne valent que pour le postulat de base, peuvent aussi varier en fonction de la nouvelle valeur, à chaque itération.

P.S. : le bruit blanc ou QRN est produit par toutes sources naturelles ou artificielles ambiantes pouvant perturber un courant électrique ou électro-magnétique. Et ça va de la lampe-torche aux tempêtes solaire. Sur une prise ou un micro c'est pareil. On reste dans le déterminisme, mais pour le coup, je pense que la mécanique quantique à plus son mot à dire, dans le cas de la prise surtout.