Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 25-03-2013 14:25:15

Wons
Invité

PRNG "trop performant" = perte d'aléatoire ?

Bonjour à tous,

Une petite question qui me chiffonne, et que j'ai un peu de mal à résoudre, étant donné ce qu'elle implique.

J'ai travaillé récemment sur un PRNG maison, et générant 10 Mo de données à la volée (soit 1024 * 1024 * 10 = 10 485 760 éléments).

Après avoir calculé Monte-Carlo / Pi, effectué les tests d'occurrences, et le coef' de série (histoire de vérifier si les données ne se suivaient pas), j'obtiens un résultat assez étrange : tout est presque parfaitement aléatoire. Presque trop. Le calcul est réalisé par byte, soit un intervalle [0,255].

J'entends par là que pour chaque série de 10 millions générée, la moyenne arithmétique de toutes les occurrences est aux alentours de 127.5001, Monte-Carlo / Pi est de 3.14159XXXX, avec une entropie à 7.9999XX bits par octet...

D'où une question perturbante : un PRNG sortant en permanence des résultats extrêmement proches de l'aléatoire complet est-il toujours un PRNG ?

J'entends par là que si chaque byte est représenté autant de fois que ses pairs, peut-on considérer avoir toujours de l'aléatoire ?

L'aléatoire devrait plutôt sortir des valeurs non concordantes, avec des "pics" sur certains ? Auquel cas ce ne serait plus vraiment un générateur de nombres aléatoires ...

Obtenir ne serait-ce qu'une moyenne arithmétique presque parfaite sur 10 millions de résultats en sortie de PRNG, je trouve que c'est assez perturbant pour se poser la question de l'intégrité de l'aléatoire...

Qu'en pensez-vous ? Des avis ? Des questions ?

Pour info, le résultat d'un dernier test réalisé à l'instant :

Entropy = 7.999982 bits per byte.
Chi square distribution for 10485760 samples is 262.64, and randomly
would exceed this value 35.77 percent of the times.

Arithmetic mean value of data bytes is 127.5062 (127.5 = random).
Monte Carlo value for Pi is 3.141509682 (error 0.00 percent).
Serial correlation coefficient is -0.000065 (totally uncorrelated = 0.0).

Vos avis ? :)

#2 25-03-2013 14:37:49

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Salut,

quel est ton pgm qu'on regarde ?

Sinon, il existe des mètres linéaires de littérature sur les tests de générateurs de nombre aléatoire et certains départements de recherche, comme celui de Jussieu, sont assez à la pointe de la recherche sur ces questions. As tu songé à consulter certaines de leur publication sur ce sujet  ?


Memento Mori ! ...

Hors ligne

#3 25-03-2013 15:03:53

Wons
Invité

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,

Concernant le programme, c'est un outil maison codé avec mes p'tites mimines, mais je peux sans aucun souci (et avec plaisir) vous fournir un fichier de sortie contenant les données testées. Voir ici : http://dl.free.fr/n6N8Ke9zG

Pour le programme utilisé pour tester Monte-Carlo et consorts, c'est par ici : http://www.fourmilab.ch/random/

Le fichier donné suite aux tests donne ceci :

Entropy = 7.999981 bits per byte.

Chi square distribution for 10485760 samples is 280.67, and randomly
would exceed this value 12.92 percent of the times.

Arithmetic mean value of data bytes is 127.5129 (127.5 = random).
Monte Carlo value for Pi is 3.141832406 (error 0.01 percent).
Serial correlation coefficient is 0.000216 (totally uncorrelated = 0.0).

Si l'on s'en tient aux bits (0/1), j'obtiens ceci :

Entropy = 1.000000 bits per bit.

Chi square distribution for 83886080 samples is 4.79, and randomly
would exceed this value 2.86 percent of the times.

Arithmetic mean value of data bits is 0.5001 (0.5 = random).
Monte Carlo value for Pi is 3.141832406 (error 0.01 percent).
Serial correlation coefficient is -0.000221 (totally uncorrelated = 0.0).

Par contre, je n'ai effectivement pas (pour le moment) lu la littérature associée aux tests sur les PRNG ... une voie à me conseiller quant à certaines de leurs publications ?

Merci quoiqu'il en soit pour votre réponse !

#4 25-03-2013 20:50:30

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Salut,

c'est mieux le pgm que tu as écrit, si tu veux ... Je ne peux pas charger le résultat et ça ne m’intéresse pas, et les tests sont standards, il y en a plein d'autres que tu peux toi même imaginer ...

Si tu as trouvé un générateur génial, je te garantie la prospérité, car en modélisation stochastique pour la finance et l'assurance par exemple, il y a de réels besoins.


Memento Mori ! ...

Hors ligne

#5 26-03-2013 15:35:08

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Re,

tiens, cadeau : Hasard et informatique


Memento Mori ! ...

Hors ligne

#6 27-03-2013 09:38:16

Wons
Membre
Inscription : 25-03-2013
Messages : 6

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,

Je ne vous ai pas oublié, et je ne suis pas parti en fouine, je suis juste en train d'améliorer le code et de le commenter, histoire que vous puissiez vous y retrouver :)

Le code utilisé provient à l'origine d'un logiciel de chiffrement maison, et j'ai développé une partie PRNG par dessus, ce qui explique ce soit un peu ... chaotique.

Donc je remets le tout en ordre, et vous envoi le tout par message privé dès que possible.

Merci encore pour votre temps !

Edit : Et je viens de voir le lien, merci encore !

Dernière modification par Wons (27-03-2013 09:38:42)

Hors ligne

#7 27-03-2013 14:34:59

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Re,

OK , j'attends l'arme au pied - et au passage, merci à yoshi de ses discrètes corrections ortho-typographiques ;-)))


Memento Mori ! ...

Hors ligne

#8 11-04-2013 13:27:13

Wons
Membre
Inscription : 25-03-2013
Messages : 6

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,

Je vous ait envoyé le message via la messagerie du forum il y a une semaine et quelques jours, auriez-vous eu le temps, à tout hasard, de jeter un oeil au fonctionnement ?

Merci d'avance !

Hors ligne

#9 11-04-2013 15:02:38

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Salut,

envoyé à qui ? Perso, je n'ai rien reçu.

Dernière modification par freddy (11-04-2013 15:02:48)


Memento Mori ! ...

Hors ligne

#10 12-04-2013 06:45:38

Wons
Membre
Inscription : 25-03-2013
Messages : 6

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,

Envoyé à vous, justement :)

Je suppose que je suis bon pour un nouvel envoi ? Rien dans la boite de spams ? :/

Hors ligne

#11 12-04-2013 07:05:44

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,


Si je suppose bien, tu as cru envoyer quelque chose à freddy : tu dis que tu as pris l'adresse sur le forum...
Aurais-tu utilisé cette adresse :
mathweb2002  -at-   yahoo.fr  ?
Si oui, cette adresse n'est pas celle de freddy, mais l'adresse générique du site BibMath et les messages aboutissent dans la BAL de Fred, qui n'est pas freddy, mais l'Administrateur/Créateur du site...

Avant tout nouvel envoi éclaircissons ce point !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#12 12-04-2013 07:16:47

Wons
Membre
Inscription : 25-03-2013
Messages : 6

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,

Heu .. non, j'ai fait un peu plus simple que ça, j'ai simplement cliqué sur "E-mail" sous le profil de Freddy dans ses messages postés ci-dessus...

J'avais par contre mis un lien vers un fichier dans le message, ce qui a peut-être conduit au filtrage du message ?

Hors ligne

#13 12-04-2013 08:56:29

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

Re : PRNG "trop performant" = perte d'aléatoire ?

Ave,

D'ac. Pas d'erreur de ce côté...
Donc l'adresse utilisée pointait sur hotmail...
Hmmmm... Il me semble me souvenir qu'il y ait eu des pb avec les PJ dans hotmail, mais là, tu as simplement mis un lien...
Donc, non, aucune raison qu'hotmail ait rejeté ton message...

Fais donc la même chose pour moi, pour voir...
Si ça passe, je fais suivre et on verra !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#14 12-04-2013 09:47:28

Wons
Membre
Inscription : 25-03-2013
Messages : 6

Re : PRNG "trop performant" = perte d'aléatoire ?

Bien le bonjour,

Eeeerf, je veux bien envoyer un mail, maiiiis ... à quelle adresse ? :)

Je n'ai pas le bouton "E-mail" sous votre profil ? :)

Hors ligne

#15 12-04-2013 10:50:03

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

Re : PRNG "trop performant" = perte d'aléatoire ?

Ah....

Là : yoshik_at_no-log.org. Remplacer _at_ par @

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#16 12-04-2013 15:12:01

Wons
Membre
Inscription : 25-03-2013
Messages : 6

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,

Le message est parti ! :)

Hors ligne

#17 12-04-2013 16:27:21

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Re,

person, je n'ai toujours rien reçu ..;


Memento Mori ! ...

Hors ligne

#18 12-04-2013 17:20:17

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

Re : PRNG "trop performant" = perte d'aléatoire ?

Salut,

Je viens de te le relayer...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#19 13-04-2013 15:40:08

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Salut yoshi,

rien reçu ...


Memento Mori ! ...

Hors ligne

#20 13-04-2013 18:05:05

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

Re : PRNG "trop performant" = perte d'aléatoire ?

Bon,

Vérifies si ton logiciel courrier ne rejetterait pas l'extension .7z...

Je renvoie à ton adresse perso, on va être fixé.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#21 13-04-2013 18:53:16

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : PRNG "trop performant" = perte d'aléatoire ?

Salut,

OK reçu ! Merci je regarde ...


Memento Mori ! ...

Hors ligne

#22 14-05-2017 17:12:23

Pyrr
Invité

Re : PRNG "trop performant" = perte d'aléatoire ?

Bonjour,

Excusez moi de faire remonter le post, mais je suis entrain d'étudier les séries de tests du programme ENT.
Le fait est que je n'arrive pas à comprendre comment il fait ses calculs :
Votre échantillon de 10 Mo est utilisé en tant que séquences de nombres ou autre chose pour réaliser les calculs d'entropie, du khi carré, de la moyenne arithmétique et la simulation de Monte Carlo.
Merci d'avance.

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le troisième mot de cette phrase?

Pied de page des forums