RANDU

RANDU est le nom d'un générateur congruentiel linéaire introduit dans les années 1960, sur des machines IBM System/370 ou d’autres machines 32 bits. Il est très impopulaire car il possède de nombreux biais auxquels ont dû faire face les personnes qui l'ont utilisé.

Tracé tridimensionnel de 100 000 valeurs générées avec RANDU. Chaque point représente 3 valeurs pseudo-aléatoires consécutives. On voit clairement que les points se situent dans 15 plans bidimensionnels.

Définition

Il est défini par la relation de récurrence :

${\displaystyle X_{n+1}\equiv (65539\times X_{n})\mod 2^{31}}$

avec X₀ impair. On engendre des nombres réels pseudo-aléatoires entre 0 et 1 par

${\displaystyle r_{n}\equiv X_{n}/2^{31}.}$

Critiques

C'est l'exemple parfait du fait que le potentiel d'un générateur ne saurait en aucun cas garantir sa qualité. En effet, bien que son potentiel soit de 31 (le minimum requis pour un bon générateur est de 5), il donne des résultats plus que décevants au test spectral pour des dimensions supérieures à 2 et n’aurait donc jamais dû être utilisé. De plus l'absence d'incrément fait que sa période est faible (moins de 2³⁰).

Les défauts de ce générateur s'expliquent en remarquant que ${\displaystyle 65539=2^{16}+3.}$ C'est pour cela que ce générateur avait été introduit. En effet, la multiplication par 65539, opération lente sur les machines de l'époque, était remplacée par un algorithme plus rapide utilisant des additions et des décalages de bits (shift), puisque ${\displaystyle 65539\times x=x\ll 16+x\ll 1+x}$.

Malheureusement, un tel choix de multiplicateur, ${\displaystyle m=2^{16}+3}$, est un désastre pour les propriétés statistiques. En effet,

${\displaystyle m^{2}=6m-9\mod 2^{31}.}$

On en déduit que trois nombres successifs X_n, X_n+1 et X_n+2 vérifient toujours la relation

${\displaystyle X_{n+2}=6X_{n+1}-9X_{n}\mod 2^{31}.}$

Il en est de même pour les réels r_n qui vérifient

${\displaystyle r_{n+2}=6r_{n+1}-9r_{n}\mod 1.}$

Cette relation donne des corrélations macroscopiques : par exemple, une modification des valeurs de r_n et r_n+1 de l'ordre de 0,01, change la valeur de r_n+2 d'au plus 0,15. Pour avoir un « bon » générateur, on souhaite une relation avec des coefficients beaucoup plus grands que 6 et 9, de telle manière qu'une petite modification de r_n ou r_n+1 change complètement la valeur de r_n+2, pour donner l'illusion d'un tirage vraiment aléatoire.

Ce générateur est parfois étudié dans les cours, pour ses vertus pédagogiques.

« ...its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists! » — Donald E. Knuth

Voir aussi

• Mersenne Twister - un exemple de bon générateur.
• Générateur de nombres aléatoires ou pseudo-aléatoires

Références

• Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, chapitre 3 : Random Numbers (Addison-Wesley, Boston, 1998).

• Portail de l’informatique