Générateur aléatoire

[GBo]

Une telle PN en entrée d'un modulateur mary-PSK ou QAM (pour faire un test de BER en présence de bruit blanc gaussien par exemple, un classique), tu vas voir majoritairement le même trajet parcouru sur le plan complexe I&Q (celui décrivant la suite de symboles correspondant au codage binaire de 012345789) sauf au passage du digit de la décimale de Pi (tous les 11 digits donc).
-> ça me fait sourciller, on perd du temps pour atteindre la diversité des chemins souhaitable, il y a donc forcément meilleure PN pour une durée de test donnée (raisonnement intuitif, mais je pense qu'on se comprend).
-----

[Deedee81]

Salut,

Il y a un commentaire intéressant ici sur sa réapparition dans le cadre du cryptage quantique. Et qui met en avant des inconvénients en usage normal que j'avais oubliés : pas de garantie d'intégrité ni d'authentification.

Ah oui, je ne pensais pas au cryptage quantique. Merci,

Par contre si je crée mon propre générateur en introduisant 0123456789 entre chaque décimale de Pi, je reste "normal" au niveau expérimental mais il y a des répétitions du même motif, sans être périodique au sens défini au dessus !
-> Pas très bon pour un PN, donc les critères ci-dessus ne suffisent peut-être pas à faire un bon PN ?

Ton exemple me rappelle le nombre de Champernowne qui est normal en base 10. Or il ne serait clairement pas une bonne source pour un générateur aléatoire. Donc "être normal" est loin d'être suffisant. Dommage (car des nombres "vraiment" aléatoire comme ceux dont on aurait besoin, comme dans le cas de l'équation Diophantienne de Chaitin, sont difficile voire impossible à calculer à nombre arbitraire de chiffres, ce qui est ma foi normal sinon on pourrait écrire un programme totalement déterministe qui serait un parfait générateur aléatoire, ce qui est impossible).

[invite452d5a24]

Bonjour,

Juste une petite remarque en passant les nombres rationnels, ne sont pas périodique dans leurs développement en base 10, mais pseudo-périodique, c'est à dire que le développement décimal n'est périodique qu'à partir d'un certain rang, comme par exemple :
4/3=1.33333... il n'est période qu à partir de 1/10 avec des 3 qui se repètent.

Bonne journée.

[GBo]

Oui c'est bien ce qui est indiqué en bleu dans le messsage #23 ("for every n > N, d(n+k) = d(n)").

[Médiat]

@Dattier
Pour une fois que ce que vous écrivez n'est pas une énorme ânerie, vous ne faites que répéter le message #23 publié 6 heure avant le votre ....

[fred3000gt]

De ce qui précède, j'ai l'impression que la proposition:

"Tout générateur pseudo-aléatoire infini est périodique"

est donc fausse.

[GBo]

Oui Pi est justement un bon candidat de générateur pseudo aléatoire infini non périodique (hormis la difficulté de calcul déjà relevée) car :
- il ne peut pas présenter de périodicité au sens de la définition du message #23, puisque Pi est irrationnel (désolé d'avoir semé le doute ce matin)
- la suite de décimales générées a la propriété de l'aléatoire de par la "normalité" de Pi (non prouvée mais constatée jusqu'ici)

(rappel "normalité": il y a autant de 0 que de 1 que de 2 que de ... 9 qui sortent, on peut donc simuler une pièce non pipée avec pile pour une décimale paire et face pour une décimale impaire, par exemple)

cdlt,
GBo

[Deedee81]

Salut,

De ce qui précède, j'ai l'impression que la proposition:
"Tout générateur pseudo-aléatoire infini est périodique"
est donc fausse.

En fait, si elle est vraie. Même un générateur qui utiliserait le nombre pi ou autre astuce du genre (que le générateur soit médiocre ou pas est une autre question ). En effet, calculer autant de décimales qu'on veut de pi est forcément limité car plus on calcule loin et plus il faut de mémoire. Même un simple compteur prend de plus en plus de places. Et en pratique la mémoire est toujours limitée. Or un système informatique de taille limitée ne peut prendre qu'un nombre fini d'états et si la machine est déterministe alors le résultat ne peut être que périodique.

Evidemment on peut toujours imaginer une mémoire illimitée. Dans les travaux théoriques avec Turing and cie on ne se gène pas

[GBo]

Pourquoi de plus en plus de mémoire ? je ne comprends pas Deedee, ne peut-on pas générer une nouvelle décimale de Pi par calcul sans avoir à mémoriser toutes les précédentes ?

[fred3000gt]

Le sujet ne porte pas sur la calculabilité.

[GBo]

D'accord, mais le message #38 est fâcheux s'il s'avérait vrai, il y aussi des ingénieurs que ta question, décidément très bonne, intéresse

[Deedee81]

Pourquoi de plus en plus de mémoire ? je ne comprends pas Deedee, ne peut-on pas générer une nouvelle décimale de Pi par calcul sans avoir à mémoriser toutes les précédentes ?

Ah je ne parlais pas de stocker tous les résultats précédents mais il faut forcément plus de mémoire pour calculer la milliardième décimale que la première (même avec la méthode, en binaire, permettant de calculer une décimale sans les précédente). Net fut-ce théoriquement à cause du nombre limité d'états d'un programme (mémoire inclue) de taille fixée.

[GBo]

Ah je ne parlais pas de stocker tous les résultats précédents mais il faut forcément plus de mémoire pour calculer la milliardième décimale que la première (même avec la méthode, en binaire, permettant de calculer une décimale sans les précédente). Net fut-ce théoriquement à cause du nombre limité d'états d'un programme (mémoire inclue) de taille fixée.

Tu as raison. Le meilleur algo que je viens de trouver date de 2003, si j'ai bien compris il troque de la complexité contre de la faible croissante de l'utilisation mémoire (mais elle croit inévitablement avec le rang de la décimale calculée, même si beaucoup plus lentement que des méthodes précédentes) :
Computation of the n-th decimal digit of π with low memory Xavier Gourdon
http://numbers.computation.free.fr/C...cimaldigit.pdf

Ca c'est pour Pi, OK.
Mais est-ce qu'il est prouvé que c'est un problème général, comme tu le laisses entendre dans le message #34 ?

[Deedee81]

Mais est-ce qu'il est prouvé que c'est un problème général, comme tu le laisses entendre dans le message #34 ?

Mais oui et c'est même évident. Prend un programme et sa mémoire dont le tout ferait N bits au maximum. Le nombre d'états que peu prendre le tout est de 2^N au maximum. Et donc le programme ne saurait pas sortir plus de 2^N décimales (sauf si c'est constant ou périodique bien sûr ).

[GBo]

J'ai fait 2 puissance 16 Go (en bits) sur Matlab, il me répond Inf

[Deedee81]

J'ai fait 2 puissance 16 Go (en bits) sur Matlab, il me répond Inf

C'est un limite théorique, bien sûr. Les générateurs on en pratique des registres en mémoire de quelques centaines de bits.

[polo974]

J'ai fait 2 puissance 16 Go (en bits) sur Matlab, il me répond Inf

Heureusement pour toi, parce que s'il t'avait sorti un nombre avec en gros 40 milliards de digits, tu aurais eu un peu de mal pour les lire tous...

[GBo]

J'ai de quoi faire mes tests de BERT à séquence non périodique jusqu'à la retraite et au-delà dans l'au-delà !