+ Répondre à la discussion Actualité déjà publiée
  1. #1
    Rédacteur

    Avatar de ram-0000
    Homme Profil pro
    Consultant en sécurité
    Inscrit en
    mai 2007
    Messages
    11 517
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Consultant en sécurité
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : mai 2007
    Messages : 11 517
    Points : 50 397
    Points
    50 397

    Par défaut Les générateurs de nombres aléatoires

    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

    Raymond
    Vous souhaitez participer à la rubrique Réseaux ? Contactez-moi

    Cafuro Cafuro est un outil SNMP dont le but est d'aider les administrateurs système et réseau à configurer leurs équipements SNMP réseau.
    e-verbe Un logiciel de conjugaison des verbes de la langue française.

    Ma page personnelle sur DVP
    .

  2. #2
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 134
    Points : 6 448
    Points
    6 448
    Billets dans le blog
    43

    Par défaut

    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
    Tutoriels et FAQ TypeScript

  3. #3
    Membre expérimenté
    Homme Profil pro
    Consultant Ingenierie mécanique
    Inscrit en
    mars 2006
    Messages
    734
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Consultant Ingenierie mécanique
    Secteur : Transports

    Informations forums :
    Inscription : mars 2006
    Messages : 734
    Points : 1 612
    Points
    1 612

    Par défaut

    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 ?

  4. #4
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 134
    Points : 6 448
    Points
    6 448
    Billets dans le blog
    43

    Par défaut

    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.
    Tutoriels et FAQ TypeScript

  5. #5
    Membre régulier Avatar de Othana
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mars 2007
    Messages
    185
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2007
    Messages : 185
    Points : 78
    Points
    78

    Par défaut

    Citation Envoyé par yahiko Voir le message
    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 !

  6. #6
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 134
    Points : 6 448
    Points
    6 448
    Billets dans le blog
    43

    Par défaut

    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.
    Tutoriels et FAQ TypeScript

  7. #7
    Membre régulier Avatar de Othana
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mars 2007
    Messages
    185
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2007
    Messages : 185
    Points : 78
    Points
    78

    Par défaut

    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.

Discussions similaires

  1. Les Générateurs de Nombres Aléatoires
    Par yahiko dans le forum Développement 2D, 3D et Jeux
    Réponses: 1
    Dernier message: 26/09/2014, 18h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo