Introduction
Développé par Makoto Matsumoto et Takuji Nishimura en 1997, le Mersenne Twister est un générateur de nombres pseudo-aléatoires particulièrement réputé pour sa qualité.
L’algorithme est basé sur un TGSFR (twisted generalised shift feedback register, un type particulier de registre à décalage à rétroaction) et tient son nom d’un nombre premier de Mersenne. Il existe au moins deux variantes majeures, la plus répandue étant MT 19937, utilisant le nombre premier de Mersenne 2 − 1 et présente les propriétés suivantes :
- sa période est de 2 − 1 ;
- il est uniformément distribué sur un grand nombre de dimensions (623 pour les nombres de 32 bits) ;
- il est plus rapide que la plupart des autres générateurs (sauf les plus médiocres statistiquement) ;
- il est aléatoire quel que soit le poids du bit considéré, et passe les tests Diehard.
Une révision de l'algorithme a été faite afin de combler quelques lacunes, notamment l'initialisation correcte, afin d'assurer la maximisation de la période.