Les générateurs de nombres aléatoires

Version imprimable

14/10/2014, 11h36
ram-0000

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.

Citation:

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 !

:fleche: Les générateurs de nombres aléatoires

:merci:

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:

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.

http://1.bp.blogspot.com/-92e22bUMww...%2Bdrawing.png

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

29/07/2016, 15h57
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 ?
30/07/2016, 00h08
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.

Citation:

Envoyé par 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.

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:

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:

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 !

23/08/2016, 12h17
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)

Citation:

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.
23/08/2016, 15h40
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.
20/02/2022, 03h17
Paul_Le_Heros

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.

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:

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
…
  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…

22/02/2022, 17h06
wiwaxia

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

... 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):

C_n^p/2ⁿ = C₁₂₈⁶⁴/2¹²⁸ = 7.039 % ⁽¹⁾
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

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:

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:

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.

23/02/2022, 10h41
wiwaxia

1 pièce(s) jointe(s)

Les générateurs de nombres aléatoires

Citation:

Envoyé par Paul_Le_Heros

... 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é.

Pièce jointe 614231

Citation:

Envoyé par Paul_Le_Heros

... 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:

F_n = F_n-j#F_n-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 = 2⁸ (Byte), 2¹⁶ (Word), 2³² (DWord), 2⁶⁴ (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 P_j,k(x) = x^k + x^j + 1 est premier sur {-1 , 0 , 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:

x_n = F_n MOD 32 ; y_n = (F_n DIV 2048) MOD 32 .
Le battage du jeu comportera un nombre arbitrairement choisi de transpositions.

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

⁽¹⁾ Pour celles et ceux d'entre vous à qui cela ne paraîtrait pas très clair :aie: 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
23/02/2022, 11h54
yahiko

Tout à fait. L'aléatoire, c'est surtout l'absence de patterns.

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:

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

25/02/2022, 09h33
Paul_Le_Heros

Chapeau bas...8O

Citation:

Envoyé par wiwaxia

...Pour celles et ceux d'entre vous à qui cela ne paraîtrait pas très clair :aie: voir par exemple…

C'était bien, mais pas aidant dans mon cas ! :calim2:
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.
01/03/2022, 00h08
Paul_Le_Heros

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) !

Solution finale (-: pour cette belote)

Bonjour à tous.
Je suppose que ça ne va pas intéresser grand monde, mais je place ici une solution que je trouve satisfaisante.
Pour le générateur de nombres pseudos aléatoires, je suis revenu à xor4096, qui, tout nu, ne m'a pas plus satisfait que ISAAC, mais pèse moins lourd. Voici un large extrait du module créé :

Code:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/* Générateur de nombre aléatoire
  A Javascript implementaion of Richard Brent's Xorgens xor4096 algorithm.
  This fast non-cryptographic random number generator is designed for
  use in Monte-Carlo algorithms. It combines a long-period xorshift
  generator with a Weyl generator, and it passes all common batteries
  of stasticial tests for randomness while consuming only a few nanoseconds
  for each prng generated. http://arxiv.org/pdf/1004.3115v1.pdf and
  https://github.com/davidbau/seedrandom/raw/released/
 
  MmmF()          : Nombre flottant de 32 bits < 1.0. Entre 0.0 et 1.0, 1.0 non compris
  MmmB()          : Nombre entre 0 et ((2^^32)-1)
  MmmPf()         : "Pile ou face"
  MmmE(r)         : Nombre entier entre 0 et une limite "r" considérée entière ("r" exclu)
  MmmDf()         : Retourne un flottant de 56 bits (? jamais utilisé)
  ArrShuff(a)     : Mélange les éléments d'un tableau "a" (Bat un paquet de ▒s)
  ArrSort(a)      : Trie dans l'ordre croissant les éléments du tableau "a"
  ArrRSort(a)     : Trie dans l'ordre décroissant les éléments du tableau "a"   */
 
  (function(wNam) { /**  ### ### ### ### ### ### ### ### ### ### ### ### ### ###    Random.js */
"use strict";
   /// * Propriétés et méthodes privées.
   const kta=[4,8,16,32,64,128,256,512,1024,2048,4096,8192,1<<14,1<<15,1<<16]
   ;
   var _bCnt=0 // Compteur des bits en stock
   ,_b32       // Source des 32 bits
   //,_ppese=Math.ceil    // le plus petit entier supérieur ou égal à x
   ,_pgeie=Math.floor     // le plus grand entier inférieur ou égal à x
   //,_epv  =Math.round   // la valeur de l'entier le plus proche de x
   ,_w=0  // Les 3 variables qui suivent sont de la soupe à Marcel !
   ,_X=0  // Marcel, y dit qu'une locale, c'est traité plus vite qu'une moins locale :-)
   ,_i=0  // Quand je serais grand, je vérifierai ça, mais je me doute que c'est vrai.
   ,_mixTime=function () {
     // Ici, Inverse les bits 31 à 0 (miroir)
    var r=(+new Date); // Équivaut a new Date().getTime()
// ...
     return r;
    }
   ,_Rnd=function () { /// ---------------------------------------------------------------------
    // Retourne un entier de 32 bits, signé
// ... résultat en r_
     z_=Events.NextXor();
     return r_^z_;
    }
   ,_Seed=function (ee) { /// ------------------------------------------------------------------
    // Initialise le générateur à partir de la graine "ee"
// ...
    }
   ,_bGet=function () { /// --------------------------------------------------------------------
   // Diviser par 32 le nbre de PRN utilisés pour "Pile ou Face" (O.MmmPf [mélange des ▒s])
    var r_;
    if (!_bCnt) {  // Source à sec ?
     _bCnt=31;    // Il reste 32 bits disponibles
     r_=(_b32=_Rnd()) & 0x80000000; // Donner le 1er résultat après avoir rechargé la source
    } else
      r_=_b32 & (1<<_bCnt--); // Servi !
    return 0+(!!r_);          // Envoyer le résultat
    }
  /// * Propriétés et méthodes publiques.
  ,O=$w$[wNam]={
// ...
   ,MmmF:function () { /// *********************************************************************
    // Nombre flottant IN[0..1[
    return Math.abs(_Rnd()%0x7FFFFFFF)/0x7FFFFFFF;
    }
   ,MmmB:function () { /// *********************************************************************
    // Nombre entier IN[0..2^^32[
    return _Rnd();
    }
   ,MmmPf:function () { /// ********************************************************************
    // "Pile ou face", Return 0 ou 1 et non false ou true
    return _bGet(); // Nouveau "bit à bit"
    }
   ,MmmE:function (x) { /// ********************************************************************
    // Nombre entier entre 0 et une limite "x" considérée entière ("x" exclu). Utilisé pour les
    // coupes du paquet (surtout). Génération d'un mot de passe de 63 caractères :
    //  for(_a="",_i=0;_i<63;_i++)
    //   _a+="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"[Rand.MmmE(62)]
    // Pour prendre tous les caractères de la chaîne "ABCD…6789" au hasard et 1 seule fois :
    //  var _a="",_r="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
    // ,_n,_x=_r.length;
    // while(_x>0){_a+=_r[_n=Rand.MmmE(_x--)];_r=_r.slice(0, _n)+_r.slice(_n+1)}
    var i_=0, j_=0, r_=0
    ;
     // if (isNaN(x)) debugger;      // x<0 && $clog("Paramètre de MmmE < 0 ! ("+x+")");
     x=_pgeie(Math.abs(x))|0;        // Sécuriser le paramètre "x"
     if (x<3)
      r_=x>1 ? _bGet() : 0;          // 0||1:->0; 2->1. Les cas simples
     else {
      for (; i_<kta.length && x>kta[i_]; // Trouver le nb de bits nécessaires
           j_=++i_);
      if (i_>=kta.length)            // Si plus de 16 bits sont necessaires
       r_=_pgeie(O.MmmF()*x);        // On utilisera les 32 bits d'un mot
      else {                         // Si non, similaire à MmmF mais avec "économie" de bits!
       for (r_=(_bGet()<<1)+_bGet(); // Composer le PRN
            i_>0;
            i_--, r_|=_bGet()<<i_+2);
       if (x!=kta[j_])               // Si non utilisable directement...
        r_=_pgeie(r_/kta[j_]*x);     // ...faire du calcul
       }
     }
     return r_;
    }
   ,MmmDf:function () { /// ********************************************************************
    // Retourne un flottant de 56 bits (utiles ?) WARNING Jamais testée
    var _t, _b, _r
    ;
     do {
       _t=_Rnd()>>>11;
       _b=O.MmmF();
       _r=(_t+_b)/0x200000; // (1<<21) plus rapide que 0x200000 ?
     } while (!_r);
     return _r;
    }
   ,ArrShuff: function (a) { /// ***************************************************************
    // Mélange les éléments d'un tableau "a" (Battait un paquet de ▒s)
    // a.sort(function() { return O.MmmPf() ? 1 : -1; }); // Trop couteux !
    // for (i_=0; i_<32; i_++) Rand.ArrShuff(_pak); est très couteux en chaos: 1024 bits ! Cette
    // nouvelle fonction pour un tableau de 32 valeurs consomme 16*5+8*4+4*3+3*2+2 bits c'est-à-
    // dire 80+32+12+6+2 bits -> 132 bits. (mais 129 mesurés !)
    var t_=a.length, k_=a.concat() // Clonage de _pak
    ;
     for(a=[]; t_; ) // réponse "à neuf",
      a.push(k_.splice(Rand.MmmE(t_--), 1)[0]); // Rand.MmmE(_t) pos. dans k_ de la valeur
     return a;
    }
   ,ArrSort: function (a) { /// ****************************************************************
    // Trie dans l'ordre croissant les éléments du tableau a
     a.sort(function (a, b) { return(a-b); }); // Done !
    }
   ,ArrRSort: function (a) { /// ***************************************************************
    // Trie dans l'ordre décroissant les éléments du tableau a
     a.sort(function (a, b) { return(b-a); }); // Done !
    }
   }; // Fin de la définition de l'objet "O"
   /// *************************************************** Initialisation de PRNG avec la graine
    _Seed(); // Initialisation du générateur String (+new Date)+"\0" -> "1651621280579\u0000")
  }("Rand"));

Il faut noter dans ce code les grosses "économies" d'entropie réalisées, en particulier dans la réécriture de ()Rand.ArrShuff, principale utilisation dans le jeu. On peut noter dans la méthode privée _Rand un appel à ()Events.NextXor. Selon moi, c'est la clé qui fait que je n'ai ensuite jamais eu l'impression de rejouer des donnes déjà vues.

Voici une extrait de du module Events :

Code:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
  (function (wNam) { /**  ### ### ### ### ### ### ### ### ### ### ### ### ### ###   Events.js */
"use strict";
  const kEntL=464 // Left positionnement de l'anti-barre-graphe du plein d'entropie
  ,kEntT=545      // Top
  ,kRndPwr=(1<<6) // Taille des tableaux générés
  var _rTi=-1
  ,_Str=""
  ,_memO=new Uint32Array(kRndPwr)
  ,_iXor=0
  ,_memC=-1      // <0 -> _memO vide
  ,_$en
  ,_morEntro=function (e) { /// ****************************************************************
   // La doc Firefox relative à window.performance me semble très médiocre (2022-05-17)
   var ets=e.timeStamp // e.timeStamp / NOTE window.performance.now() KO pour Chrome
   ,dt=ets-_rTi                // On ne limite pas
   ,dXdY=Math.abs(e.movementX) // ### Considération dX,dY
        +Math.abs(e.movementY)
   ,s1                         // ### Considération dX,dY
   ,s
   ,show=function (q) { // ---------------------------------------------------------------------
    // Barre-graphe de l'entropie: "q" complément à 128 de la quantité à afficher
     _$en && _$en.css({ left:kEntL+q+"px" ,width:128-q+"px" });
     }
   ; // --------------------------------------------------------------------------------------
    if (_rTi>0 && dt>1) {                /// Traitement pure entropie
     dt+=e.type==kEL[12] ? dXdY : 0;     // ### Considération dX,dY "mousemove"
     s=dt.toString(2);                   // s <- "1100101111000110"
     s=s.substring(s.indexOf("1")+1);    // s <-  "100101111000110"
     _Str+=s;                            // Ajout à la chaîne existante
     s1="";                              // ### Considération dX,dY
     e.type==kEL[12] && (                // ### Considération dX,dY "mousemove"
      s1=dXdY.toString(2),               // ### Considération dX,dY // s <-"1100101111000110"
      s1=s1.substring(s.indexOf("1")+1), // ### Considération dX,dY // s <- "100101111000110"
      _Str+=s1);                         // ### Considération dX,dY  // Add à la chaîne exist
     for (;_Str.length>32           // Tant qu'il y a un mot de 32 bits dispo ET...
       && _memC<kRndPwr; ) {        // ... de la place où le stocker
      s=_Str.slice(0,32);           // La chaîne des 32 bits
      _Str=_Str.substr(32);         // Réduire la source d'autant
      _memO[++_memC]=parseInt(s,2); // Placer le résultat
     }
     if (_memC<0)
      return
     show(_memC<<1);                // Actualiser le barre-graphe
     if (_memC==kRndPwr) {          // N bits à 1 ?
      show(_memC=0);                // Fin de la mise à jour de l'affichage ET RàZ
      localStorage.setItem('rand1');
      O.once=1;
     }
    } /// Fin du traitement de la pure entropie
    _rTi=ets;
// ... Suit la "distribution" des événements
   }
  ,O=$w$[wNam]={ /// ---------------------------------------------------------------------------
 //...
   ,NextXor:function () { /// ******************************************************************
     return _memC>=0              // Remplissage commencé ?
       ? _memO[_iXor<_memO.length // Toujours dans les limites
         ? _iXor++                // oui
         : _iXor=0]               // "Tourner autour"
       : 0xFFFFFFFF;              // Inversion
     }
   ,Init:function () { /// *********************************************************************
   var $EmR=_morEntro
   ;
    // Handlers nécessaire à l'utilisateur pour la génétion d'entropie. Pour le dispaching voir
    // la fonction _morEntro
     $dbaEL(kEL[20], $EmR);   // 20:"keydown"
     $dbaEL(kEL[21], $EmR);   // 21:"keypress"
     $dbaEL(kEL[22], $EmR);   // 22:"keyup"
     $dbaEL(kEL [8], $EmR);   //  8:"click"
     $dbaEL(kEL[10], $EmR);   // 10:"mousedown"
     $dbaEL(kEL[11], $EmR);   // 11:"mouseup"
     $dbaEL(kEL[12], $EmR);   // 12:"mousemove"
// ...
     $("bbody").append("<img id=entro src="+gPathImg+"entro.png style=position:absolute;"
                      +"left:"+kEntL+"px;top:"+kEntT+"px;width:132px;height:8px >");
     _$en=$("#entro");
    }
   }; // Fin de l'objet O
  }("Events")); /// ****************************************************************************

J'y ai laissé le code du suivi d'un barre-graphe auquel il ne faut pas prêter d'attention. Si l'utilisateur joue avec la sourie, la génération d'entropie est vraiment très rapide, et il en est produit plus que nécessaire : parfait pour le jeu. Pour faire court, le temps entre deux événements sert de source, auquel il est ajouté quelques bits de plus quand les événements proviennent d'un mouvement de la souris. Les seuls bits "à droite" du bit le plus significatif à 1 sont conservés, ce qui fait qu'on devrait trouver entre 0…0 à 1…1 comme résultats. On devrait ainsi se retrouver avec une probable parité globale des 1 et des 0. Un tableau de 64 valeurs et progressivement garni mais le contenu est utilisé dès que possible par ()Events.NextXor.
Je vous remercie pour l'attention que vous aurez porté à ce post, et vous invite à faire des remarques (relatives au code :weird:), tant sur la forme que sur le fond...

NB: J'espère actualiser la page où se trouve une ébauche de belote (avant la fin de l'année :oops:)

EDIT: Précision (en bleu), et simplification repéré au nettoyage des sources...