IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

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


Sujet :

Mathématiques

  1. #1
    Rédacteur

    Avatar de ram-0000
    Homme Profil pro
    Consultant en sécurité
    Inscrit en
    mai 2007
    Messages
    11 519
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 59
    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 519
    Points : 50 361
    Points
    50 361
    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
    Développeur
    Inscrit en
    juillet 2013
    Messages
    1 350
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 350
    Points : 8 518
    Points
    8 518
    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 extrêmement actif
    Homme Profil pro
    Consultant Ingenierie mécanique
    Inscrit en
    mars 2006
    Messages
    1 336
    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 : 1 336
    Points : 3 221
    Points
    3 221
    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
    Développeur
    Inscrit en
    juillet 2013
    Messages
    1 350
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 350
    Points : 8 518
    Points
    8 518
    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
    188
    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 : 188
    Points : 79
    Points
    79
    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
    Développeur
    Inscrit en
    juillet 2013
    Messages
    1 350
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 350
    Points : 8 518
    Points
    8 518
    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
    188
    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 : 188
    Points : 79
    Points
    79
    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.

  8. #8
    Membre averti

    Homme Profil pro
    Développeur Web
    Inscrit en
    octobre 2013
    Messages
    168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Pérou

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : octobre 2013
    Messages : 168
    Points : 334
    Points
    334
    Par défaut Quoi, je suis parano...
    Bonjour,

    Voici les questions que je me pose, relatives aux générateurs de nombres aléatoires (RNG), et pour lesquelles je n'attends pas de réponse**.
    - Il y a quelques années, j'ai posé une question sur le site DVP relative au "mot de passe" des liaisons WIFI et leur "longueur", étant bêtement convaincu que si 63 caractères étaient utilisables, le meilleur "mot de passe" en serait un de 63 caractères de long. Il m'a été répondu que ce "mot" n'était là que comme graine d'un générateur qui lui donnait "autre chose" utilisée comme "mot de passe" (ou équivalent). RàS, mais j'ai surtout noté que le thread avait disparu dans les jours qui suivirent !
    - Il me semble avoir compris qu'en France, la politique interdit de crypter les communications, et que tout ce qui concerne l'exécutif (la police au sens large, dont DST et descendants) s'intéresse de très près aux hébergeurs et fournisseurs d'accès internet, où ils imposent des règles comme, par exemple, celle de ne pas avoir à chercher les mots de passe des visiteurs des sites hébergés.
    - J'ai également noté qu'un des premiers travaux demandé aux hypers ordinateurs (quantiques) a été de casser des codes d'encryptage.
    - Je ne vois plus, comme par le passé, l'interdiction d'exporter les logiciels de cryptage, comme on pouvait le lire il y a (trop) longtemps dans les manuels des produits d'origine des USAs. En fait ma mémoire est confuse, mais je me souviens avoir lu ça dans des documents de produits d'origine des USAs (Digital Equipment Corporation ?). Je me dis que les ressources pour casser les codes sont suffisamment puissantes aujourd'hui pour ne plus imposer ces remarques.
    - On ne manque jamais sur DVP en particulier, de parler de la NSA, des failles de sécurité, des portes dérobées et autre "grâcieusetés". L'objectif est clairement d’espionner, et comme le générateur de nombres pseudo-aléatoires est au centre du système de cryptage, je me dis qu'il parait judicieux de "contrôler" (au sens anglais) tout ce qui se publie dans ce domaine.
    - En 2006, j'ai commencé à utiliser un jeu de belote qui a été développé sous WindOverDose mais qui, par chance, tournait convenablement sous Wine. J'ai souvent vécu la frustration parce que j'avais l'impression de rejouer les mêmes donnes. Je suis entré en contact avec le développeur qui a fini par se fâcher et cessé de me répondre. J'ai fini par penser que l'auteur n'était pas en cause, mais que le générateur de nombres pseudo-aléatoires, si. Il faut que le générateur de Microsoft à l’export soit faible, pour faciliter l'espionnage, mais sa faiblesse peut finir par se voir.

    En 2014, j'ai commencé construire un jeu de belote fonctionnant dans un fureteur. J'ai D’abord utilisé l’objet Math, puis ai décidé d'utiliser un générateur propre à l'application. Ce premier fut une implémentation de "Richard Brent's Xorgens: xor4096 algorithm"(code ici). Mais je n'en étais pas satisfait, même si c'est un excellent générateur. Je me suis ensuite tourné vers celui-ci www.imagine-programming.com où j'ai trouvé de quoi moudre.

    Pour faire un générateur aux résultats humainement très imprévisibles, j'utiliserais un compteur électronique 16 bits en boucle capable de passer très rapidement par ses 65536 états (par exemple, mais au moins !)_: il ne resterait pas plus de 1 nanoseconde sur un état (horloge à 1GHz). Considérant que deux gestes identiques répétés rapidement par un humain ne sont pas facilement espacés de moins de 100mS, ce compteur aurait eu le temps de passer ~1500 fois par tous ses états. Si on échantillonne ce compteur une fois par action, la valeur de l'échantillon peut être considérée comme aléatoire. C'est moins facile pour le suivi d'une souris : le système questionne-t-il régulièrement la souris pour en connaître la position ou la souris n'informe-t-elle le système que quand il y a un changement de position sur l’un des deux axes ? Quel espace de temps entre deux de ces événements curseur vu du système, de X ou de JavaScript ? Avec ce compteur exemple, on doit s'attendre à devoir augmenter la fréquence d'horloge pour générer de l'entropie à partir des déplacements du curseur.

    Finalement je souhaite créer une graine digne de ce nom et voudrais utiliser (en JavaScript dans un fureteur, donc) souris et touches afin de créer de l'entropie, quitte à créer un court "jeu" à l'ouverture de la page. Mais les choses ne sont pas si simples qu'il semble. D'abord, j'aimerais que la répartition des bits sur une certaine quantité d'échantillons (mais combien ?) soient 50% de 1 (-: et autant de 0).
    - 1er cas_: Je garde les X bits à droite du bit levé le plus significatif : par exemple 0001_0011_0110_0111 -> 12 bits 0011_0110_0111 que je "sérialise de sorte à composer un mot de N bits (32 bits à priori).
    - 2nd cas_: j'échantillonne le e.timeStamp et retourne ou inverse les huit bits de poids faibles, le bit 0 étant le plus "instable", de sorte que le bit 0 devienne le bit 7, le 1 en 6, etc. Je totalise les bits de tous les échantillons et au-delà de 100 (?) d'entre eux, je favorise les 1 ou les 0 (comment ?) pour arriver à une parité de 50,00% au bout de 128 échantillons.

    Il y a un problème majeur à utiliser e.timeStamp_: il me semble avoir lu dans quelque documentation (FF probablement) que ses valeurs sont modulos 5mS ou quelque chose comme ça. Mais si les 5ms ne sont pas cadensé par un échantillonnage genre "setInterval()", je crois qu'il est possible de faire bien sans e.timeStamp.

    **Les réponses à cette question m'intéressent : quelqu'un aurait un exemple de source (ouverte de préférence), ou une bonne méthode pour parvenir à un résultat correct de graine, voire de générateur ?

    Je vous remercie pour l’attention que vous aurez portée à ce post.

  9. #9
    Membre averti

    Homme Profil pro
    Développeur Web
    Inscrit en
    octobre 2013
    Messages
    168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Pérou

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : octobre 2013
    Messages : 168
    Points : 334
    Points
    334
    Par défaut
    Bonjour,

    J'ai eu le temps d'essayer un petit pneu, et ça ne m'a pas gonflé !

    Je me suis trompé : autant que je puisse juger des résultats, l'utilisation de e.timeStamp fonctionne bien mieux (et est probablement moins "lourd") que new Date().getTime(). Ces histoires de 5mS doivent concerner la précision, "seulement". J'ai du confondre, et ai la flemme de chercher…

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
     
    …
      var rTi=-1
      ,lCnt=0
      ,Str=""
      ,Tp1=0
      ;
      function newEntro (e) {
      var ets=e.timeStamp
      ,dt=ets-rTi // C'était (ets-rTi)&0xFFFF
      ,p1
      ,b
      ,s
      ,l
      ;
        if (rTi<0)
         rTi=ets;
        else if (dt>1){                     // ex: 1100_1011_1100_0110 0xCBC6
         s=dt.toString(2);                  // s <- "1100101111000110"
         s=s.substring(s.indexOf("1")+1);   // s <-  "100101111000110"
         Str+=s;                            // Ajout à la chaîne existante
         for (b=p1=0, l=s.length; b<l; b++) // Comptage des bits à 1
          p1+=parseInt(s[b]); // |          // "merger"
         Tp1+=p1;             // |          // "merger"
         if (Tp1>=5000) {                   // N bits à 1 ?
          Tty.App11dev(Str+" (len: "+Str.length+"), bit à 1: "+Tp1);
          Str="";
          Tp1=lCnt=0;
         }
        }
       }
    …
     $($d$).ready( function () {
    …
       document.body.addEventListener(kEL[20], newEntro); // 20:"keydown"
       document.body.addEventListener(kEL[21], newEntro); // 20:"keypress"
       document.body.addEventListener(kEL[22], newEntro); // 22:"keyup"
       document.body.addEventListener(kEL [8], newEntro); //  8:"click"
       document.body.addEventListener(kEL[10], newEntro); // 10:"mousedown"
       document.body.addEventListener(kEL[11], newEntro); // 11:"mouseup"
       document.body.addEventListener(kEL[12], newEntro); // 12:"mousemove"}
    /*
    FireFox Developer Edition 98.0b7 (64bits):
    Mouse (only)
    10111101001111101111010111111011111000111110111110011111101111101111101011111110111011000000000111110000000111111100000011011111000000111110110000010101101100000110111011000001110111110000100011111100001001111111000100000110110001011101101100010111111111000111101110110001111111111100100000111111001000011110110010001011101100100011111111001001001111110010010111101100100110111011001001111111110010100011111100101001111011001010101110110010110001101100101101011011001011100111110010111101101100110000011111001100010111110011001001101100110011011011001100111110110011010101111100110110011011001101110110110011100011101100111001111111001111011110110100010001101101000100011011011101011111110111100001101101111001111111011110110110110111110001111101111100111111011111100111110111111101111110000000011111100000010110111000000111101110000011011111100001001111111000010111101110000111111111100010001111111000100111101110001010111011100010111111111000110011111110001101111011100011110111111001000001101110010001011111100100011111111001001100001110011100111111100111101110111001111111101110100000111111101000011110111010001101101110100100111011101001100110111010011101101110110011011011101101000110111011010011101110111001111011101110101111111011101111111110111101111111101111111110111100000100001111000010011111110000110110111100010001101111000101011111110001101110111100100001101111001001011111110010101110111100110001101111001101011111110011101110111100111111111111010001011011110100100111111101001101111111010100111111110101100111111101100111101111011100111111110111100000111101111101111111011111111111111000010110111110001011111111100011111011111100110111111111010001111111110101011111111101100111111111011111111111111001011111111110100111111111101101111111111100111011111111100111111111111101100000000000011100000000000111100000000001111100000000010101100000000011011100000000011111100000000100011110000001100001110000001100111110000001101011110000001101111100000001110011100000001110111110000001111111100000010000111110000010001011110000010001111100000010010011100000010011001110000010011101100000011001011110000011110001100000011110011110000011110111110000011111111110000100000001100000100000111110000100010011110000100011001100000100011101100000100100001110000100100101110000100101011100000100101111100000100110011110000100110101110000101010011110000101110111100000101110111100000110001101100000110101101100000110101101100000111001101100001001001111100001001101111110001001101111110001110101111110001110110101100001110111001110001110111101110001111000001100001111000101100001111001001110001111001101110001111010001100001111010101100001111011001110001111011101110001111100001100001111100101100001111101011100001111101111100001111110011110001111110111110001111111011100001111111111100010000000011110010000000111110010000001011100010000010011110010000010101100010000011011100010000100001110010000100101100010000101001100010000101101110010000110011110010000110111110010000111011100010010001111110010010010011110010010101101110010011001011100010011001111110010011010011110010011010111100010011011011100010011011111110010011100101100010011100111100010011101101100010011110001110010011110101110010011111001100010100100111100010100101011110010100101111110010100110011100010100110111100010100111011110010100111111110010101000101110010101001001110010101001101100010101010001100010101010101110010101011001110010101011101100010101100001100010101100101110010101101001110010101101101100010101110001110010101110101100010101111011100010101111111100010110000011110010110000111110010110001011100010110001111100010110010011110010110010111110010110011011100010110011111110010110100011110010110100111100010110111101110010111011011110010111100111110010111110001110010111110011110010111111011110010111111111110011000000011110011000000111110011000001101110011000010001110011000010101110011000010111110011000101001110011001001011100011001001011100011010111001110011011100001100011011100001100011101011011100011101101001110011101110111100011101111011100011110000011110011110000111100011110001111110011110010111100011110011101110011110100101100011110101001110011110110001100011110110101100011110111001110011110111011100011111000001110011111000101110011111001011110011111001101100011111010011110011111010101110011111011011110011111011111110011111100011110011111100111110011111101011110011111101111110011111110011110011111111011110100000000001100100000000101110100000001001110100000001011110100000010001100100000010101110100000011001110100000011101100100000100001100100000100111100100000101101100100000110001100100000110111100100000111011110100000111111100100001000101100100001010101100101100101101110101101001011100101101101001100101101101011100101101101111100101101110101110101101111011110101101111111100101110000001110101110100011100101111000101100101111000101100110000101101100110001010001110110001010001110110110110011110110110110111010110110111011100110110111111110110111000011100110111001011010110111001111110110111010011110110111010111100110111011011100110111100001100110111100101100110111101001110110111101101010110111110001100110111110101110110111111001010110111111101010111000000001100111000010111100111010110101010111010111001010111010111111010111011000101010111011001001010111011001101110111011010001100111011010101010111011011001010111011100011110111011101111110111011110101100111100010001010111100011111010111100101111010111100110101110111100111011100111100111101010111101000011010111101000111100111101001011100111101001111010111101010011010111101010111100111101011001100111101011111010111101101111110111101110011100111110001111100111110001111100111111000001010111111100001010111111100001011000011001111011000011010011011000011010111101000011011011101000011011111101000011100011011000011100111101000011101011111000011101111011000011110011101000011110101101000100001001101000100100001101000100100001101000110100011101000110100111101000110101101101000110101111101000110110011101000110110111101000110111011101000110111111101000111000001011000111000111101000111001111101000111100001011001000000101011001000000101011010000110001011010000110101101010000111001101010000111101011010001000001011010001000101101010001001001011010001001101101010001010011101010001010101011010001011111101010001100011101010011001111011010011010011011010011010111101010011011001011010011100101101101101001001101101101001101101101101010001011101101010111011101101011011011101110110001011101110110111101101110111011011101110111111011101111000011101101111000111101101111001011011101111001111011101111010011101101111010111101101111011011011110000001011101110000110001011110001111111101110010000011101110010000101101110010001011011110010001110001110011001001011110011001101011110011010001101110101011011101110101011111101110101100011101110101100111101110101101011101110101101111101110101110011101110101111001101110101111101101110110000001011110110000101101110110001001101110110111111011110111000011101110111000111011110111001011011110111001111101110111010011101110111010111011110111011101011110111100001011110111100101011110111101001111110111101101101110111110001011110111110101011110111111001101110111111101101111000000001011111000000101011111000001001101111000001101101111000010101011111000010111011111000011011011111000011111101111000100011101111000100111011111000101011011111000101111101111000110011101111000110111011111000111011011111001000001011111001000101101111001110111101111010000011101111010000111011111010010001011111010100001011111100000011101111100000111011111101100011011111101100111101111101101011111111101110001101111101110101101111101111001011111101111101011111110000001101111110000101101111110110111011111110111011101111110111101011111111000001101111111010101011101101111110110000000010100000101010000100110000011011000010001010001010110000110010100011101010010000110001001011000101011010010111101001100111000110111100011101101001111110101000011100100011110010010110101001111010101001110010101110101011011100110000101011001011001101001100110110101011100010101110101101000000101100001011010001001101000110101100100010111111011100010101011010101000011010110111101011001000011101001001001101001001111011001010011101001010111101001011011011001011111011001100011101001100111101001101011011001110001011001110101101001110111101001111101011010000001101010100011101010100111101010101011011010110011101010110111011010111011101010111111101011000011011011001001101011001011101011010011011110000011011111011011101111011111101111100001100000001001101000000110011000000011101010000010000101000001000110100000101101010000011001101000001101110100000111001100000011111110000010000111000001000101100000100101101000010101010100001010111010000101101101000010111111000001100011100000110100101000011011011000001110001100000111010101000011110010100001111101100001000000110000100001010100010001001010001000110110
     (len: 8858), bit à 1: 5003
     
    001…100 (len: 10222), bit à 1: 5000
     
    101…011 (len: 9575), bit à 1: 5005
     
    110…011 (len: 10159), bit à 1: 5003
     
    111…010 (len: 9927), bit à 1: 5001
     
    111…001 (len: 11390), bit à 1: 5006
     
    010…110 (len: 9559), bit à 1: 5000
     
    Keyboard (only)
    010111010111000110111100110001111010010111011101110111011110100111111111011111100000000111110101101111111010111101111001100010011110110010100110011010001111001101011111101101011010110110110101011001101010110110011011010001100111010101111001110110110110011110001011100111100111111001111011110110011111011001101001010101111010010111000011100110010101101001101101111010100010100110101001000101101010011000111010100111011110101010001111101010101001011010101100000110101011101001101011001100111010110100111110101101111001101011100010111010111010100110101110111111011100010100011011000110111110110011001001101100111011111011010110110110110110000011101101101000011011011011001110110111001111101101111000111011100001101111111000101111101110010011111011100110001101111100110011101111010011111000000101011011000000110010111000001000100011000001001001111100001010010011000001010110110100001011101011000001100100010100010100101110100010101110011000100010000110100100010111011000100011110111000100100011111000100101011011000100110010111000110001101011000110010100010100110011011011100110100000111001000010010011001000011100110101010010011110101010011010011001010100101011001010101101010101100010001100001100011001011010100100111010110100101101010110100110011110110100111001111010101010100010110101011011110110111110010010110111111001010110111111110110111000000100110111000101100010111000110010010111001011110011011001100100010111001101011110111001110000110111001111000011011001111111110111010111011010111011000001010111011010100010111011011100110011100011011110111100011111110111101010111010111101011110110111101100101010111101101011110111101110010110111101111010110111110010000110111110011010010011111110011110111111111000010000001011010001111101011011010110000011011001111101101101110111010101011111010101000111011010010111010111101110101000000011110011110110101100000001101110111110100111001101101111100010101111101110101111111011100000000011110000000100111010000100001101000100010010100010101111011100010100100110001111110001000101001100010001101101000101100101010101011011000101010111011011000101111100110010010011110100100101001011001001011010010110011000001011110000111101001100010101110000000110010010000000110111010000000111110110000001000110110000100101100101100100110011110000100111010110000101000011110001000000110010001000001100001101000011000010001000100001001101101011000110001101100000110001111111001001101111111111010010000001010001110000001111110010101000011101110101001011110010101011000001110101100001010010110110100001110110111100010010111010101110010111011011001110111100011001110111101000001110111101111101110111110011001110111111010110010111111110101111000000111010011000001001010011000101010001111000110000101111000111000010011000111101001111001101011101111001110101101111010100100101111010101001001111010110001101111010110110101111100000011001111100001000010011100010001010011100011000010011100101001110011100110000101111100110111101111100111101101111101101110010011101110111101111110010100001111110011000001111110100010001111110101010001111110110000001111110110101101111111000000001111111000101101111111010010101111111011001101111111100001001111111100111110011111011001101011111110001100001000011001010000110011011110001001001011010101000110110011001101110111011111000110111111001101000001010101100010100001100100100001100101100001100110111101100111110001101000111001101001110101111110110001100001110001000001011110011000110110101101000111010110100101011101010100111101101010111110101010000101011001001011100011001011100001010001100111001011001101000010010001101001110010001101011110010010101111010010010110001001010010111101000010010111110101010011000000101010011000001111010011011110110010011100000100010011111001010010011111010110010100001000011010100001001110100100001011101011100001101001010100010100001010100010110011010100101001111010100101100001001100110111110010100111001011010100111011011010100111101000010101001110100001101010000100010101010111010010101011001000010101011110111010101100000001010101100010000010101100011010001101100101001010101100110110001101110010101010101110100100001110000101111001110000111010001110001001001001110001010110001110010000011001110010001110001110010011110001110010101010001110010111010010110011001000001110100111001010110101000101010110101010101010110101100001001110101110001010110110000011010111010111011001111011001110001111100111011100111101001001001100101010010100111011001101011011001101101001001101111001001110000111010110011100011110110000001111101111001000000001000100101010000010010110011011001100000101000110011100010100001010001010001101101101110100100010111100000001000001001010010000011000100100001000001001000010010110010000101110000100001101010000000100100000010001010000100000100110010001001001111110010010110010001000101110001001001011111100010011000100000100110010110001001100111101110011011101100100111001100001010000000010010100001000100101010101111001010101110100010101100110000101011010110001010111010100010101111101000101100110010001011010000110011001110111100010011110110000101001000110101010011000100110100111110001101010010010011010101011000110101100100010101101101010011011100011100111001111111001110100100000011101010000100111010101111000111000011110101110001111100111100101110000111001110110001110100101000111101011000001111111000000001111111000000100101001011100100101010010100000101011011000000101100011000000111011011000100111101010100001001001011100101001010100000001100101011000001100110001100001100110111000001100111100000001101001011100001101010010000010000100010000010000101001000010111101100000010111110000111110111111000100010111111111011111001000101100011001001011011111001010111100011001100000100011010110111111111010111101111111011000100111111011001100011111011110000000001110100011011011111010010001111011000100110111111010110000100010000011100011000100101101000111100000101001110000111110111001011111100000110010011110011011001000001110010011100011011000111000111001001110001111001000000011111101111001000010110000010001011111100100111100111001010100100000011101001011100111100101111010101101010000101100000111101011001101111010110111000000101111101111101100010000111011101001011110111010101011101110111000111011110000110000111101000011101111010110111011111001101110111110100011001111110101111011111111001111000010101111110000110110111100010000111111000100111111010001011101000100011010001111000111010111110010000101001100101011101111001100000111110100101011111101001110011111010100100011110101010100111101011000110101010110111011110110010111111101101001001111011011000100010110111100111101110001101111011101001011110111011110111101111011111111100010111011111001000011111110101011001101101011110011111011010111111110111000101101101111000111111011111000111111000001111101110001001111111100100010111111001011111101110011110111111101001111111111101111111111111100111111111111101100111111111101111100000000001001100000000011101110000000111001110000001001011110000001101001110000001111101110000010011011100000010111001100000110101011110000111001111110001000000111110001000011101110001000111001110001001001101110001001101001100001010000001100001010100001110001011000101100001110011011110001110110101110001111010100000001111101101100010000001101100010000110001110010100100011110010101000011110101110110111110101111011001100110000100111100110001000111100110100110011100110101001011100111011011001100111011111111110111100110011100111101001101110111101101101100111110000101100111110100011110111111001101101000001101001101000010001011101000110100101111000111001011101001010011001101001010101011111001011001011101001011010101101001011101101101001100001000001001101000101101001101100001101001101111101101001110011001101001110111001101001111100011101010001101101111010010011001101010111001111111010111101111101011001000101101011001100001101011001111101101011010010011111011010110011111011011001011101011100010011101011100111011101100001110001101100010000101101100010100011101100010110111101100011010111111100011110011101100101000011101100101100101101101001010101101101001111001101101011001111101101011100111101101100000111101101100100011011101100110111111101101010111101101110000011011101110101001101110000011111101110000111111101110100111111101110101011001101110111000111011110111100101101111000010001101111000101011101111001000101101111001100001101111001111001101111010010001101111010110001101111011010001101111100110001101111101011011011111111000111101111111101001101011111101101110011001011011111011111111100001110011000101110110110001101110110011010101110101010101110111000101011111011010110000000111101011101111110101111111110111000011101011100100000110110101010110111011001011011111001111110111101111011000000011010110000001010001010010010101010100100110101101001010001001010010100111010100101011011110001011010101010011001110111000110110000110001111110101100100000110011001011011000101010111010011010110000101110101100010101101011001000111010110010111010101100111110101011010100011011000001001010110000011111101100001011111011000100000111010010000100110100100100111011001010100110110010110100101100110000001011001100110010110011011001101100111001011011001111001110110100000110101101010001111101010101101011011000000011110110000100111011100011011110111001000011101110010100001101100101101110111001101010101110011101101111110000111011111100011101100111100100111011111001111010111110101101101
     (len: 9384), bit à 1: 5007
    */
    Le jeu utilisé permet de jouer au clavier comme à la souris. J'ai donc pu sortir les ~70 kbits rapidement en jouant avec la souris, mais ce fut bien plus long pour les ~10 Kbits en jouant au clavier !

    J'ai commencé à coder avec des opérateurs "bitwise". Je ne sais pas si on y gagne en temps d’exécution, mais le fait de pouvoir utiliser une chaîne de caractères comme un tableau, ça va bien plus vite à écrire et même tester…

    Ça semble correct ! Mais ce n'est que l'appréciation d'un incompétent ! Qu'en, pensez-vous ? Je n'ai pas encore eu le temps de tester le "second cas du post précédent. Mais je me demande si ça vaut la peine.

    Dans l'espoir de vous lire bientôt…

  10. #10
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 235
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 235
    Points : 2 392
    Points
    2 392
    Billets dans le blog
    9
    Par défaut Les générateurs de nombres aléatoires
    Bonjour,

    J'avais lu (et relu) d'une manière approfondie l'article auquel se réfère cette discussion, et qui constituait une excellente initiation sur le sujet.

    Ton intervention cite des références intéressantes, mais que je n'ai pas eu le temps d'examiner dans le détail.
    Je ne suis pas spécialiste en ce domaine, mais deux remarques concernant la description de ton projet me viennent à l'esprit.

    Citation Envoyé par Paul_Le_Heros Voir le message
    ... Finalement je souhaite créer une graine digne de ce nom et voudrais utiliser (en JavaScript dans un fureteur, donc) souris et touches afin de créer de l'entropie ... / ... D'abord, j'aimerais que la répartition des bits sur une certaine quantité d'échantillons (mais combien ?) soient 50% de 1 (-: et autant de 0)
    ... / ... Je totalise les bits de tous les échantillons et au-delà de 100 (?) d'entre eux, je favorise les 1 ou les 0 (comment ?) pour arriver à une parité de 50,00% au bout de 128 échantillons.

    Il y a un problème majeur à utiliser e.timeStamp_: il me semble avoir lu dans quelque documentation (FF probablement) que ses valeurs sont modulos 5mS ou quelque chose comme ça. Mais si les 5ms ne sont pas cadensé par un échantillonnage genre "setInterval()", je crois qu'il est possible de faire bien sans e.timeStamp.

    **Les réponses à cette question m'intéressent : quelqu'un aurait un exemple de source (ouverte de préférence), ou une bonne méthode pour parvenir à un résultat correct de graine, voire de générateur ? ...
    1°) Qu'entends-tu par un graine correcte, digne de ce nom ? Une séquence de caractères totalement imprévisible, dont chaque terme ne pourrait être déduit de ses prédécesseurs - à l'exact opposé de ce qu'emploierait un internaute peu imaginatif, comme par exemple:
    <Timeismoney> ou <Unagneausedésaltéraitdanslecourantd'uneondepure> ?
    Il te faudra renoncer à tout langage humain, car je crois bien les logiciels casseurs de code capables d'identifier les mots de toute langue connue, pour peu qu'elle s'écrive (ou soit translittérable) en caractères latins ou cyrilliques.
    La seule solution: un séquence pseudo-aléatoire de (n) termes, qu'il s'agisse des chiffres décimaux - ou éventuellement des caractères imprimables du code standard. Le calcul apparaît ici comme une étape obligatoire, le cerveau humain étant incapable d'assumer cette tâche; une calculatrice scientifique dont la précision est assurée sur 14 chiffres, mais dépourvue d'accès à Internet donc inaccessible à l'espionnage, fera fort bien l'affaire: il suffira pour cela de faire intervenir une fonction à valeurs irrationnelles, s'étalant sur un domaine d'étendue raisonnable, qui à tout argument banal (par exemple la date et l'heure du premier mail, ou de la création d'un fichier) pourra faire correspondre une séquence de 6 à 12 chiffres.
    L'entier (x) représentant par exemple la date au format <jjmmaa>, la fonction F(x) = (x*10-4)2/3
    varie de 1.008 116 884 594 0 (au 01/01/2022) à 9.894 188 790 472 5 (au 31/12/2022)
    et peut conduire à des séquences de 12 chiffres décimaux. Les variantes envisageables sont innombrables, dès lors qu'on en a saisi le principe.
    Un logiciel de calcul présente des possibilités beaucoup plus vastes, mais son installation sur la machine rend son utilisation visible à un intrus: il faut prendre des dispositions cohérentes.

    2°) La parité des chiffres binaires (0 et 1) doit-elle être exactement respectée ? Un séquence apparaît-elle moins "aléatoire" dès lors qu'elle ne comporte que 45% de (1) ? La probabilité de sortie de tels nombres est certes inférieure à celle du cas précédent, mais nullement négligeable.
    Ainsi dans une séquence de 128 bits, la probabilité de présence de 64 chiffres (1) est (de tête, à vérifier):
    Cnp/2n = C12864/2128 = 7.039 % (1)
    donc très minoritaire (moins d'une séquence sur 14).
    La restriction des séquences à la condition évoquée est artificielle et excessive; en restreignant drastiquement le nombre de combinaisons, elle facilite au contraire la tâche des pirates.
    De plus elle ne tient pas compte de la succession des chiffres, dont la régularité éventuelle serait rapidement détectée; prendrais-tu pour graine un nombre tel que
    <1111 1111 1111 1111 0000 0000 0000 0000> ?
    Il paraît préférable de renoncer à toute restriction de ce genre.

    D'autres manipulations, que tu as évoquées, sont sûrement plus efficaces: inversion de la séquence, mélange par énumération alternée, recours à l'opérateur Xor.

    (1) https://www.wolframalpha.com/input?i...4%29%2F2%5E128


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Membre averti

    Homme Profil pro
    Développeur Web
    Inscrit en
    octobre 2013
    Messages
    168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Pérou

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : octobre 2013
    Messages : 168
    Points : 334
    Points
    334
    Par défaut
    Bonjour wiwaxia et merci pour votre post.
    Cette histoire de parité m'a turlupiné à cause du bout de code utilisé pour mélanger un tableau :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
       ,ArrShuff: function (a) { /// ***************************************************************
        // Mélange les éléments d'un tableau (Bat un paquet de cartes)
         a.sort(function() {
          return O.MmmPf() ? 1 : -1;  // OK
          });
        }
    Je me suis demandé quel bit utiliser, parmi les 32 retournés par le générateur. Au début, j'ai écrit :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
       ,MmmPf:function () { /// ********************************************************************
        // "Pile ou face"
        return 0+!(O.pop()&0x40000000);
        }
    Mais il m'est rapidement apparu que pour battre sérieusement un jeu de 32 cartes avec cette méthode, il faut décemment appeler au moins 10 fois consécutivement ArrShuff(). L'entropie peut se révéler précieuse, alors, pour écrire "vert" (-: , j'ai modifié le code de ArrShuff() pour qu'elle retourne un résultat en lien avec un seul des 32 bits d'un mot en buffer (le code est sans intérêt). Dans le premier cas j'utilisais 320x32 bits et comme j'ai poussé le battage des cartes jusqu'à 32 appels dans le second cas, je n'utilise plus que 32x32 bits. Mais avec cette modification, la parité, la "disposition" ou "répartition" des bits dans le mot ont beaucoup d'effet, surtout si on ne répète pas suffisamment l'appel à ArrShuff(). D'où cette question : quid de la parité des résultats ? Mon raisonnement est simple : ces générateurs XOR cycles plus ou moins rapidement (le moins rapidement -> le meilleur), on peut supposer que même si un nombre X se trouve N fois dans un cycle complet, tous les autres nombres devraient idéalement se retrouver également N fois dans ce cycle. Dans mon exemple de compteur 16 bits à 1GHz, ce serait évidemment vrai puisque la parité des 1 et des 0 est garantie en comptant de 0 à 65535. Si le PRNG utilisé boucle sur un nombre astronomique, il est clairement difficile d'apprécier la parité des 1 et des 0 sur un échantillon astronomiquement microscopique de 256 valeurs de 32 bits…

    C'est vrai qu'il y a de nombreuse façons d'ensemencer un PRNG. Isaac propose rien, un nombre ou un tableau de 256 mots de 32 bits, du genre de celui dans lequel il donne ses résultats.
    - Rien signifie partir du nombre 0 en quelque sorte. Cela peut être bien pendant le développement pour retrouver toujours les mêmes situations, mais surtout pas en cas d'une vraie utilisation.
    - Un nombre entier de 32 ou 64 bits, c'est tout de même pas mal, mais comme le hasard ne se trouve guère que dans le temps écoulé depuis Epoch, exprimé en milliseconde, au lancement du logiciel (JavaScript dans un fureteur), je me dis qu'un malin pourrait bien y penser_! je sais bien qu'il ne s'agit que d'un tout petit jeu de belote, mais je suis parano, comme chacun aura pu le lire dans mon premier post dans ce thread_! L'utilisation simple de l'objet Math est à proscrire aussi, bien sûr.
    - Au démarrage et pour ensemencer le PRNG, la meilleure solution m'a donc semblé être de récupérer le dernier tableau de 256 mots de 32 bits générés antérieurement et préalablement stocké localement ou, si ce tableau n'existe pas, de proposer un petit jeu se jouant à la souris qui nous offre un assez "pur" hasard.

    En définitive, je proposerai un choix triple_: graine mémorisée | petit jeu | "automatique", parce qu'en cas d'arrêt brutal du fureteur, le joueur peut se retrouver à jouer à partir d'une graine qui a déjà été utilisée. Automatique sera la date "retournée" (-> inversion "bout pour bout" des 64 Bits les moins significatifs de la date en mS, ou quelque chose de ce genre).

    Cordialement.

  12. #12
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 235
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 235
    Points : 2 392
    Points
    2 392
    Billets dans le blog
    9
    Par défaut Les générateurs de nombres aléatoires
    Citation Envoyé par Paul_Le_Heros Voir le message
    ... Dans le premier cas j'utilisais 320x32 bits et comme j'ai poussé le battage des cartes jusqu'à 32 appels dans le second cas, je n'utilise plus que 32x32 bits. Mais avec cette modification, la parité, la "disposition" ou "répartition" des bits dans le mot ont beaucoup d'effet, surtout si on ne répète pas suffisamment l'appel à ArrShuff(). D'où cette question : quid de la parité des résultats ? Mon raisonnement est simple : ces générateurs XOR cycles plus ou moins rapidement (le moins rapidement -> le meilleur), on peut supposer que même si un nombre X se trouve N fois dans un cycle complet, tous les autres nombres devraient idéalement se retrouver également N fois dans ce cycle. Dans mon exemple de compteur 16 bits à 1GHz, ce serait évidemment vrai puisque la parité des 1 et des 0 est garantie en comptant de 0 à 65535. Si le PRNG utilisé boucle sur un nombre astronomique, il est clairement difficile d'apprécier la parité des 1 et des 0 sur un échantillon astronomiquement microscopique de 256 valeurs de 32 bits …
    Encore une fois, la recherche de la conformité d'un résultat particulier aux moyennes statistiques est une impasse, car elle découle d'un travers incoercible de l'esprit humain, qui espère d'instinct que tout excès ou défaut local (dans l'espace ou dans le temps) soit immédiatement compensé par une anomalie en sens contraire. Cela n'a rien d'un reproche personnel: le cerveau est spontanément mal disposé à concevoir des évènements aléatoires.
    Bien que ce soit contre-intuitif, le hasard, ce n'est pas l'uniformité.

    Nom : F mortes_525x348.png
Affichages : 109
Taille : 372,8 Ko

    Citation Envoyé par Paul_Le_Heros Voir le message
    ... C'est vrai qu'il y a de nombreuse façons d'ensemencer un PRNG. Isaac propose rien, un nombre ou un tableau de 256 mots de 32 bits, du genre de celui dans lequel il donne ses résultats.
    - Rien signifie partir du nombre 0 en quelque sorte. Cela peut être bien pendant le développement pour retrouver toujours les mêmes situations, mais surtout pas en cas d'une vraie utilisation.
    - Un nombre entier de 32 ou 64 bits, c'est tout de même pas mal, mais comme le hasard ne se trouve guère que dans le temps écoulé depuis Epoch, exprimé en milliseconde, au lancement du logiciel (JavaScript dans un fureteur), je me dis qu'un malin pourrait bien y penser_! je sais bien qu'il ne s'agit que d'un tout petit jeu de belote, mais je suis parano, comme chacun aura pu le lire dans mon premier post dans ce thread_! L'utilisation simple de l'objet Math est à proscrire aussi, bien sûr ...
    En effet, la mesure exprimée en millisecondes du temps écoulé depuis une date convenue (01/01/1970 ?) est aléatoire au niveau de ces 3 derniers chiffres décimaux, ce qui laisse une petite marge.

    Voici une autre option, histoire de passer à un autre algorithme, le recours aux suites décalées de Fibonacci définies par la relation de récurrence:
    Fn = Fn-j#Fn-k
    et dans lesquelles l'opérateur binaire (#) correspond soit à l'addition ou la multiplication modulo (m), soit à l'opérateur XOR; dans ce dernier cas le majorant strict (m) des entiers naturels envisagés correspond à une puissance remarquable de 2:
    m = 28 (Byte), 216 (Word), 232 (DWord), 264 (QWord) .
    La période effective de telles suites prend des valeurs théoriques énormes pour quelques paires privilégiées:
    (j , k) = (7 , 10) , (5 , 17) , (24 , 55) , (65 , 71) ...
    celles en fait pour lesquelles le polynôme Pj,k(x) = xk + xj + 1 est premier sur {-1 , 0 , 1} (1).
    Tu peux par exemple envisager une suite d'entiers au format Word, dont les (k) premiers termes seront initialisés à l'aide du générateur de ton choix; les termes suivants te donneront directement les positions des deux cartes à échanger, par les relation:
    xn = Fn MOD 32 ; yn = (Fn DIV 2048) MOD 32 .
    Le battage du jeu comportera un nombre arbitrairement choisi de transpositions.

    https://en.wikipedia.org/wiki/Lagged...acci_generator

    (1) Pour celles et ceux d'entre vous à qui cela ne paraîtrait pas très clair voir par exemple
    https://www.wolframalpha.com/input?i...4%2Bx%5E71%2B1
    https://www.wolframalpha.com/input?i...5%2Bx%5E71%2B1
    https://www.wolframalpha.com/input?i...6%2Bx%5E71%2B1


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    juillet 2013
    Messages
    1 350
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 350
    Points : 8 518
    Points
    8 518
    Billets dans le blog
    43
    Par défaut
    Tout à fait. L'aléatoire, c'est surtout l'absence de patterns.
    Tutoriels et FAQ TypeScript

  14. #14
    Membre averti

    Homme Profil pro
    Développeur Web
    Inscrit en
    octobre 2013
    Messages
    168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Pérou

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : octobre 2013
    Messages : 168
    Points : 334
    Points
    334
    Par défaut
    En fait ceci est une correction du code proposé post #9, les résultats affichés en fin de CODE ne correspondent plus à la correction ci-dessous et ne sont donc pas valides. En fait, si vous regardez bien le code initial, les bits créés sont plus liés à e.timeStamp qu'à un "delta e.timeStamp" entre deux événement, ce qui faisait qu'à la souris, ça allait beaucoup vite qu'au clavier…
    Voici une correction qui devrait vous permettre de tester :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    …
      var rTi=-1
      ,lCnt=0
      ,Str=""
      ,Tp1=0
      ;
      function newEntro (e) {
      var ets=e.timeStamp
      ,dt=ets-rTi // C'était (ets-rTi)&0xFFFF
      ,b
      ,s
      ,l
      ;
        if (rTi>=0 && dt>1) {               // ex: 1100_1011_1100_0110 0xCBC6
         s=dt.toString(2);                  // s <- "1100101111000110"
         s=s.substring(s.indexOf("1")+1);   // s <-  "100101111000110"
         Str+=s;                            // Ajout à la chaîne existante
         for (b=0, l=s.length; b<l; b++) // Comptage des bits à 1
          Tp1+=parseInt(s[b]);
         if (Tp1>=5000) {                   // N bits à 1 ?
          Tty.App11dev(Str+" (len: "+Str.length+"), bit à 1: "+Tp1);
          Str="";
          Tp1=lCnt=0;
         }
        }
        rTi=ets;
       }
    …
     $($d$).ready( function () {
    …
       document.body.addEventListener("keydown", newEntro);
       document.body.addEventListener("keypress", newEntro);
       document.body.addEventListener("keyup", newEntro);
       document.body.addEventListener("click", newEntro);
       document.body.addEventListener("mousedown", newEntro);
       document.body.addEventListener("mouseup", newEntro);
       document.body.addEventListener("mousemove", newEntro);
    …
    }
    Dans la version actuelle, je concatène également les bits Math.abs(e.movementX)+Math.abs(e.movementY) dans le cas où l'événement est du type "mousemove".

    Cordialement

  15. #15
    Membre averti

    Homme Profil pro
    Développeur Web
    Inscrit en
    octobre 2013
    Messages
    168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Pérou

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : octobre 2013
    Messages : 168
    Points : 334
    Points
    334
    Par défaut
    Chapeau bas...
    Citation Envoyé par wiwaxia Voir le message
    ...Pour celles et ceux d'entre vous à qui cela ne paraîtrait pas très clair voir par exemple…
    C'était bien, mais pas aidant dans mon cas !
    La dernière fois qu'on m'a parlé ainsi, ça date de près de 50 ans, et j'avais déjà du mal à suivre. J'ai pas eu souvent besoin d'une grande maitrise de l'outil mathématique dans ma vie : peut-être 3 fois (surtout en lien avec la géométrie), mais j'ai alors bien regretté de ne pas avoir accroché à l'époque. Trop tard !

    Merci à vous.

  16. #16
    Membre averti

    Homme Profil pro
    Développeur Web
    Inscrit en
    octobre 2013
    Messages
    168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Pérou

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : octobre 2013
    Messages : 168
    Points : 334
    Points
    334
    Par défaut Pas bon...
    Un petit post pour vous faire part de ma conviction que la méthode que j'ai utilisée pour traiter les événements n'est pas la bonne : j'ai encore plus souvent qu'avant (le changement du PRNG) l'impression de vivre des donnes que j'ai déjà vécues. Ça me gosse(qc) balaise(fr) !

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