Générateurs à congruence linéaire (séquence aleatoire)

[invite90ee81d4]

Il s'agit de l'algorithme le plus utilisé pour produire des nombres aléatoires depuis qu'il a été inventé en 1948 par D. H. Lehmer. C'est la suite :


xn+1 = (a·xn + c) mod m

avec a (multiplicateur), c (incrément), x0 (germe), et m qui sont quatre nombres entiers non-négatifs.


Si on désire produire toujours la même séquence (ce qui est pratique à des fins de tests), on rentre toujours la même valeur de x0.
Si on préfère que la séquence soit toujours différente, on initialise x0 avec une grandeur toujours différente, l'heure système par exemple.
Dans tous les cas, les nombres de la suite sont compris entre 0 et m-1.
ma question est la suivante:je voudrai générer une sequence aleatoire de 256 valeurs,comment je dois choisir a,c,x0 et m?? merci d'avance
-----

[martini_bird]

Salut,

j'ai trouvé ceci.

Un extrait:

D. Knuth fait la démonstration des critères que doivent remplir a, c et m pour cela :

• 1. c et m doivent être premiers entre eux
• 2. a-1 doit être un multiple de p, pour tout p nombre premier diviseur de m
• 3. a-1 doit être un multiple de 4 si m est un multiple de 4.
• 4. si m est une puissance de 2, le bit de poids faible des nombres produits vaut alternativement 0 et 1 (ce n'est d'ailleurs pas le seul cas où cela se produit).

Tu as déjà la valeur de m=2⁸. Pour le reste, bonne lecture!

Cordialement.

[invite90ee81d4]

moi aussi j'ai trouvé ce lien mais j'ai pas bien compris comment trouver le reste

[martini_bird]

Sur le site, ils proposent cette suite, qu'ils qualifient de qualité:

x_n+1 = (137 x_n + 187) mod 256

D'autre part, même si les critères de Knuth sont appliqués, ils précisent qu'il faut faire des tests statistiques pour juger de la qualité du générateur.

Si c'est pour une application pratique, la suite ci-dessus devrait te convenir a priori.
Si c'est pour une étude théorique des générateurs, il va falloir s'armer de patience pour faire les tests (il y pas mal de combinaisons possibles).

Cordialement.

[A voir en vidéo sur Futura]

[invite90ee81d4]

en fait je voudrais générer un signal aleatoire a partir d'un DSP

[martini_bird]

Du point de vue technique, je ne pourrai pas te conseiller, mais tu devrais avoir des résultats sympas avec la suite ci-dessus. A mon avis, si ça ne convient pas, il vaudrait peut-être mieux le faire en 16 bits.

D'autres participants sauront aussi mieux te conseiller que moi.

A+ et bon courage.