Générateur congruentiel linéaire

Générateur congruentiel linéaire

Un générateur congruentiel linéaire est un générateur de nombres pseudo-aléatoires dont l'algorithme, introduit en 1948 par D.H Lehmer, sous une forme réduite, pour produire des nombres aléatoires, est basé sur des congruences et une fonction linéaire.

Sommaire

Définition

Les nombres pseudo aléatoires forment une suite dont chaque terme dépend du précédent, selon la formule suivante :

X_{n+1} = ( a \cdot X_n + c ) \mod m

Où a est le multiplicateur, c l’incrément, m le module.

Le terme initial, X_0~ est appelé la graine (seed en anglais). C'est elle qui va permettre de générer une suite apparemment aléatoire. Pour chaque graine, on aura une nouvelle suite. Cependant, il est possible que certaines graines permettent d'obtenir une suite plus aléatoire que d'autres.

Du fait de l'opération mod (reste dans la division euclidienne de a*Xn+c par m), les termes de cette suite sont compris entre 0 et m - 1. De plus, comme chaque terme dépend entièrement du précédent, si un nombre apparaît une deuxième fois, toute la suite se reproduit à partir de ce nombre. Or le nombre de valeurs que le nombre peut prendre étant fini (égal à m), la suite est amenée à se répéter au bout d'un certain temps. On dit qu'elle est ultimement périodique.

Du bon choix des paramètres a, c et m

Dans ce type d'algorithme, la qualité du générateur va entièrement dépendre du choix de a, c et m car on ne peut pas se satisfaire d'un générateur qui produit des suites plus ou moins aléatoires, sans aucune raison apparente, selon le choix de X0.

Un mauvais exemple

Choisir a, c et m « au hasard » n'est pas une bonne idée, prenons un exemple :
Soit le générateur congruentiel linéaire (a=25, c=16, m=256), nous obtenons

  • avec X0 = 10, la suite : 10, 10, 10, 10, 10, ...
  • avec X0 = 11, la suite : 11, 35, 123, 19, 235, 3, 91, 243, 203, 227, 59, 211, 171, 195, 27, 179, 139, 163, 251, 147, 107, 131, ...
  • avec X0 = 12, la suite : 12, 60, 236, 28, 204, 252, 172, 220, 140, 188, 108, 156, 76, 124, 44, 92, 12, 60, 236, 28, 204, 252, 172, ...

Il est clair que ces suites ne peuvent être considérées comme aléatoires.
On voit donc bien que l'on doit choisir avec précaution les paramètres du générateur si l'on espère obtenir des nombres qui s'approchent de l'aléa parfait.

Il faut alors se demander comment choisir a, c et m convenablement.

Choix du module

Les générateurs congruentiels font intervenir un calcul modulo m, et donc a priori une division euclidienne, ce qui peut avoir un coût de calcul important dans le cadre d'une utilisation fréquente du générateur. La solution la plus simple est d'utiliser un module de type m = 2e. En effet, les ordinateurs calculant naturellement en base binaire, un tel choix est tout à fait transparent pour eux, ce qui rend inutile une division euclidienne.

Cependant, un tel choix présente une limite importante: les bits dits de poids faible (les bits les plus à droite) sont beaucoup moins aléatoires que ceux de la partie de poids fort (les bits les plus à gauche). En effet, si d est un diviseur de m, alors la suite Yn, telle que :

Y_n = X_n \mod d

satisfait à la suite congruentielle linéaire :

Y_{n+1} = (a \cdot Yn + c) \mod d

en particulier, avec d = 2k, pour k fixé, compris entre 1 et e, on voit que les k chiffres de poids faible, ont une période maximale de 2k, évidemment inférieure à m.
Pour remédier à ce problème, on peut ne garder que les bits de poids fort, c'est-à-dire garder les bits les plus à gauche du nombre obtenu. Si l'on tronque les k derniers bits, on aura alors un générateur pseudo aléatoire de nombres compris entre 0 et 2e − k − 1.

Une autre solution consiste à prendre un module du type m = 2^e \pm 1, ce qui permet encore d'éviter une division euclidienne par une astuce (cf. The Art Of Computer Programming de D. E. Knuth).

Choix du multiplicateur et de l'incrément

Afin de pouvoir choisir une graine X0 sans contraintes entre 0 et m-1, il faut chercher à maximiser la période du générateur. Or il se trouve que les valeurs de a et c sont connues, ce qui permet d'obtenir une période maximale (égale à m).

Si c \not= 0 la période d’un générateur congruentiel linéaire est maximale si et seulement si :

  1. c est premier avec m. Pgcd(c,m) = 1.
  2. Pour chaque nombre premier p divisant m, (a-1) est un multiple de p.
  3. (a-1) est un multiple de 4 si m en est un.

On remarquera que l'on possède un théorème d'équivalence (si et seulement si) : la période est maximale pour toutes les valeurs qui possèdent les propriétés du théorème et seulement pour celles-là.

On possède, de plus, de conditions suffisantes dans le cas particulier où c est nul. Ainsi, pour c nul la période d'un générateur congruentiel linéaire est maximale si :

  1. m est premier.
  2. am − 1 − 1 est un multiple de m.
  3. aj − 1 n'est pas divisible par m, pour j = 1,...,m − 2

Attention: ce n'est pas une équivalence!

Le potentiel

Le potentiel est une notion qui permet d'écarter certains générateurs insuffisamment aléatoires. Il est toujours défini que pour une suite possédant une période maximale (et ce, d'après la deuxième propriété énoncée plus haut). On ne peut pas toujours le définir sur les autres générateurs, et il existe de bons générateurs sur lesquels le potentiel n'est pas défini.

Le potentiel s d’une suite possédant une période maximale est défini comme le plus petit entier tel que :

(a-1)^s \equiv 0 \mod m

Pour une suite de période maximale, on peut prendre X0 = 0, et donc :

X_n = \frac {a^n - 1} {a - 1} \cdot c \mod m

ainsi, avec an = ( (a-1) + 1 )n :

X_n = c \cdot \left ( n + {n \choose 2} \cdot (a-1) + \ldots + {n \choose s} \cdot (a-1)^{s-1} \right ) \mod m

et un potentiel inférieur ou égal à trois, apparaît immédiatement comme trop faible car la suite n’est pas suffisamment aléatoire. En fait un potentiel de 5 ou plus est conseillé.

Rappelons cependant que la notion de potentiel est uniquement là pour écarter quelques mauvais générateurs. Un générateur possédant un potentiel supérieur à 5 ne peut en aucun cas être d’emblée considéré comme bon, il doit d’abord subir quelques tests.

Tests statistiques

Comme tous les générateurs de nombres pseudo-aléatoires, le générateur congruentiel linéaire doit être soumis à une série de tests avant d’être homologué.

Le plus connu d’entre eux, le test de fréquence n'est généralement pas un problème pour un générateur congruentiel linéaire de période maximale, mais il existe bien d'autres tests. Test des séries, Gap test, Run test, ...
L'un des plus discriminant, car aucun générateur congruentiel linéaire démontré mauvais ne l’a réussi, étant le test spectral.

Exemples

Algorithme a c m Remarques
RANDU 65539 0 231 Biaisé et fortement déconseillé
générateur de Robert Sedgewick 31415821 1 108 Intéressant mais déconseillé (essayer avec X_0 = 0~)
Standard minimal 16807 0 231-1
  • RANDU défini par X_{n+1} = 65539 X_n \mod 2^{31}. Implanté sur les IBM System/370 et réputé mauvais par tous ceux qui ont à l'utiliser sérieusement
  • Le générateur de Turbo Pascal défini par X_{n+1} =(129 X_n + 907633385) \mod 2^{32}. On sait dans 1 cas sur 129 que Xn + 1 > Xn, ce qui est un biais énorme pour une application scientifique. En plus comme 129 est de la forme 2^n + 1, les nombres produits ne sont pas si « aléatoires que ça » [cf. Knuth p.23].
  • Le générateur d'UNIX (dont le comité ANSI C a heureusement recommandé de ne conserver que les 16 bits de poids fort) :

X_{n+1} = (1103515245 X_n + 12345) \mod 2^{31}. Même la documentation du Berkeley 4.2 admet que les bits de poids faible des nombres produits ne sont pas vraiment aléatoires.

autres exemples

D. Knuth recense dans « Seminumerical Algorithms » un certain nombre de générateurs congruentiels linéaires de qualité. S'il n'est pas possible d'utiliser le Standard Minimal, on pourra essayer par exemple :

  • X_{n+1} = ( 137 X_n + 187 ) \mod 2^8 (une suite cyclique de 256 nombres, est-ce encore du hasard ?)
  • X_{n+1} = ( 1664525 X_n + 1013904223 ) \mod 2^{32} : générateur de Knuth & Lewis
  • X_{n+1} = 69069 X_n \mod 2^{32} : générateur de Marsaglia au multiplicande remarquable, utilisé sur le VAX
  • X_{n+1} = 31167285 X_n \mod 2^{48} : générateur de Lavaux & Jenssens
  • X_{n+1} = 6 364 136 223 846 793 005 X_n \mod 2^{64} : générateur de Haynes

Dans tous ces cas, comme le modulant est une puissance de 2, les bits de poids faible des nombres produits ne sont pas eux très « aléatoires ». Il est par conséquent préférable de ne conserver que les poids forts (16 bits par exemple), comme le fait le générateur de Borland C++ par exemple :

  • X_{n+1} = (22 695 477 X_n+1 ) \mod 2^{32} et on sort Xn + 1 > > 16

Ce faisant, la période du générateur reste la même mais on ne va produire que des nombres compris entre 0 et 65535, chacun se retrouvant 65536 fois dans la suite.

Voir aussi

Références

v · Générateurs de nombres pseudo-aléatoires
Rapide Générateur congruentiel linéaire • Mersenne Twister • RANDU
Cryptographiques Blum Blum Shub • Fortuna • ISAAC • Yarrow
Briques Congruence sur les entiers • Fonction de hachage • LFSR

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Générateur congruentiel linéaire de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Generateur congruentiel lineaire — Générateur congruentiel linéaire Un générateur congruentiel linéaire est un générateur de nombres pseudo aléatoires dont l algorithme, introduit en 1948 par D.H Lehmer, sous une forme réduite, pour produire des nombres aléatoires, est basé sur… …   Wikipédia en Français

  • Générateur Congruentiel Linéaire — Un générateur congruentiel linéaire est un générateur de nombres pseudo aléatoires dont l algorithme, introduit en 1948 par D.H Lehmer, sous une forme réduite, pour produire des nombres aléatoires, est basé sur des congruences et une fonction… …   Wikipédia en Français

  • Generateur de nombres pseudo-aleatoires — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

  • Générateur De Nombres Pseudo-Aléatoires — Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être… …   Wikipédia en Français

  • Générateur de nombre pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

  • Générateur de nombres pseudo-aléatoires — Pour les articles homonymes, voir Générateur. Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple …   Wikipédia en Français

  • Registre à décalage à rétroaction linéaire — Un registre à décalage à rétroaction linéaire, ou LFSR (acronyme de l anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite récurrente linéaire, initialement sur le corps fini à 2 élements (0 et …   Wikipédia en Français

  • Code pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

  • Fonction pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

  • PRNG — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”