N.B. : les dernières constantes (19,1,81,0) proviennent de "Algorithms" Robert Sedgewick Addison Wesley p.512
où Xn
est le ne terme de la suite et Xn-1 le terme précédent.
a, b, m sont des constantes,la valeur initiale X0 est le germe.
Ce générateur a une période qui n’est pas plus grande que m : la période
est maximale si a, b, m sont choisis correctement (voir paragraphe
suivant) :
| Le choix de ces valeurs
n'est pas un problème à négliger (bien que se résolvant facilement). En
effet, voici pour quelques valeurs prises au hasard, la mise en évidence des
périodes obtenues:
N.B. : les dernières constantes (19,1,81,0) proviennent de "Algorithms" Robert Sedgewick Addison Wesley p.512 |
|
| Autre exemple:
Les valeurs semblent ici correctes (il n'est bien sûr pas question de vérifier que la période est de 10 000 000), mais on observe que le dernier chiffre des valeurs générées est incrémenté à chaque nouvelle valeur d'une unité: le résultat est alors biaisé. Un contrôle d'abord visuel s'avère alors en premier lieu nécessaire, et doit être suivi de tests (détaillés page suivante).
|
|
Il est fortement recommandé lors du choix des constantes de vérifier les hypothèses d'un théorème démontré par Donald E. Knuth dans The Art of Computer Programming Vol. 2 (p.16 dans l'édition 2):
La suite définie par Xn=(a Xn-1 + b) mod m est de période maximale m si et seulement si :i) b est premier avec mii) quel que soit p premier divisant m, c=a-1 est un multiple de piii) si m est multiple de 4, alors b est multiple de 4 |
On peut notamment citer le générateur utilisant les constantes:
Il est en particulier utilisé dans le logiciel Maple.
Ce générateur ne vérifie pas les hypothèses du théorème précédent, il n'est donc pas de période maximale; néanmoins Knuth aborde le cas particulier des générateurs pour lesquels b est nul: ceci permet l'économie d'une addition, et on peut notamment faire en sorte lorsque m est premier (ce qui est ici le cas), d'atteindre un période de m-1.
Linear Feedback Shift Register (LFSR) en anglais.
On utilise un tableau à n bits dans lequel on effectue une opération, comme une addition, puis on effectue un décalage dans le tableau en ajoutant le nouvel élément.
Exemple avec 4 bits:
Ici on utilise un ou exclusif (addition sans retenue) sur les deux derniers bits.
Le registre est successivement à la valeur 0111, 0011, 0001, 1000, 0100...
Pour un LFSR à n bits, on peut faire en sorte d’obtenir une période maximale de 2n–1.
