RANDU

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é.

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

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

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

r_n \equiv  X_n / 2^{31}.

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 230).

Les défauts de ce générateur s'expliquent en remarquant que 65539 = 216 + 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 65539 * x = shift(x,16) + shift(x,1) + x.

Malheureusement, un tel choix de multiplicateur, m = 216 + 3, est un désastre pour les propriétés statistiques. En effet,

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

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

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

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

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

Cette relation donne des corrélations macroscopiques: par exemple, une modification des valeurs de rn et rn + 1 de l'ordre de 0,01, change la valeur de rn + 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 rn ou rn + 1 change complètement la valeur de rn + 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

Références


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article RANDU de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • RANDU — is an infamous linear congruential pseudorandom number generator which has been used since the 1960s. It is defined by the recurrence::V {j+1} equiv (65539 V j) mod 2^{31},with V 0 odd.Pseudo random numbers are calculated as::X {j} equiv V {j} /… …   Wikipedia

  • RANDU — Распределение в трёхмерном пространстве 100 000 точек, полученных алгоритмом RANDU. Можно видеть, что точки расположены на 15 плоскостях. RANDU  печально известный линейный конгруэнтный генератор псевдослучайных чисел, в …   Википедия

  • Randu — Original name in latin Randu Name in other language Randu State code ID Continent/City Asia/Jakarta longitude 8.1197 latitude 111.7935 altitude 96 Population 0 Date 2012 06 07 …   Cities with a population over 1000 database

  • randu — raita   …   Suomen slangisanakirjaa

  • Holiday House Randu Pļavas — (Салацгрива,Латвия) Категория отеля: Адрес: Pērnavas iela 33d, Салацгрив …   Каталог отелей

  • randuiti — ×randùiti, ùja, ùjo žr. randavoti 1: Šitie gaspadoriai, katarie randùjo žemę nuo grafo, tai ėmė parabkų slūžytie Aps …   Dictionary of the Lithuanian Language

  • Spektraltest — Der Spektraltest ist eine Methode, mit der überprüft werden kann, ob gegebene Zufallszahlen tatsächlich stochastisch voneinander unabhängig sind, oder ob das Gegenteil der Fall ist, d. h. bereits „gewürfelte“ Werte die folgenden Werte… …   Deutsch Wikipedia

  • Kassandra — Este artículo o sección necesita una revisión de ortografía y gramática. Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando se haya corregido, borra este aviso por favor …   Wikipedia Español

  • rasti — 1 ràsti, rañda, rãdo tr. 1. SD172, H, R, K ieškant aptikti, užeiti ką pamestą, paslėptą, paliktą: Paveizdėk, ir rasì Grv. Dabar eisme pažiūrėt, gal da ràsme Erž. Ilgai anie ieškojo jo ir visa negalėjo ràsti Lz. Kur anlįs, ir ràst negalėsi… …   Dictionary of the Lithuanian Language

  • randas — 1 randas sm. (3) 1. SD39,365, Q455, H, R, M2354, Sut, K, M, DŽ užgijusios žaizdos žymė, retys: Ant kaktos randas nuo įspyrimo kumelio J. Randas paliko, kai išgijo, kur buvo įkirsta Kp. Jeigu ir nugydysi, bus randas Pc. Jis pargrįžta iš karo… …   Dictionary of the Lithuanian Language

Share the article and excerpts

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