Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Générateur congruentiel linéaire
Résumé
Un générateur congruentiel linéaire est un générateur de nombres pseudo-aléatoires dont l'algorithme, introduit en 1948 par Derrick Lehmer, sous une forme réduite, pour produire des nombres aléatoires, est basé sur des congruences et une fonction affine.
Les nombres pseudo aléatoires forment une suite dont chaque terme dépend du précédent, selon la formule :
où a est le multiplicateur, c l'incrément et m le module.
Le terme initial 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 par m), les termes de cette suite sont compris entre 0 et . 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.
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.
Choisir les valeurs a, c et m « au hasard » n'est pas une bonne idée. Prenons un exemple, soit le générateur congruentiel linéaire employant les valeurs a = 25, c = 16, m = 256, nous obtenons :
avec X0 = 125, la suite :
avec X0 = 96, la suite :
avec X0 = 50, la suite :
avec X0 = 10, la suite :
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.