Generator congruențial liniar

Aranjamentul punctelor generate de generatorul liniar a funcționat0

În matematică, generatorul congruențial liniar ( LCG din engleza Linear Congruential Generator) este un algoritm vechi și bine cunoscut pentru generarea de numere pseudo-aleatorii . Teoria pe care se bazează este ușor de înțeles și implementat; are și avantajul de a fi ușor din punct de vedere computerizat.

Generatorul este definit recursiv :

X_{n+1}=\left(aX_{n}+c\right)\ {\bmod {\ }}m

{\ displaystyle X_ {n + 1} = \ left (aX_ {n} + c \ right) \ {\ bmod {\}} m}

{\ displaystyle X_ {n + 1} = \ left (aX_ {n} + c \ right) \ {\ bmod {\}} m}

unde este $X_{n}$ ${\ displaystyle X_ {n}}$ ${\ displaystyle X_ {n}}$ este o valoare a succesiunii numerelor pseudorandom și

m,\,0<m

{\ displaystyle m, \, 0 <m}

{\ displaystyle m, \, 0 <m}

- „ modulul ”

a,\,0<a<m

{\ displaystyle a, \, 0 <a <m}

{\ displaystyle a, \, 0 <a <m}

- „multiplicatorul”

c,\,0\leq c<m

{\ displaystyle c, \, 0 \ leq c <m}

{\ displaystyle c, \, 0 \ leq c <m}

- "creșterea" (în cazul special în care

c=0

{\ displaystyle c = 0}

c = 0

vorbim despre Park-Miller RNG sau generator multiplicativ)

X_{0},\,0\leq X_{0}<m

{\ displaystyle X_ {0}, \, 0 \ leq X_ {0} <m}

{\ displaystyle X_ {0}, \, 0 \ leq X_ {0} <m}

- „semința” sau „valoarea inițială”

Perioada unui LCG este de cel mult m , iar pentru unele alegeri a lui poate fi mult mai mică. LCG are un termen complet dacă și numai dacă :

$c$ ${\ displaystyle c}$ $c$ Și $m$ ${\ displaystyle m}$ $m$ sunt coprimă
$a-1$ ${\ displaystyle a-1}$ ${\ displaystyle a-1}$ este divizibil cu toți factorii primi ai $m$ ${\ displaystyle m}$ $m$ ,
$a-1$ ${\ displaystyle a-1}$ ${\ displaystyle a-1}$ este multiplu de 4 se $m$ ${\ displaystyle m}$ $m$ este multiplu de 4. ^[1]

Deși LCG-urile sunt în general capabile să producă numere pseudorandom decente, calitatea lor este foarte sensibilă la alegerea coeficienților c , m și a .

Din punct de vedere istoric, alegerile slabe au dus la implementări ineficiente ale LCG. Un exemplu semnificativ este RANDU, care a fost utilizat pe scară largă la începutul anilor 1970 și a condus la rezultate care sunt în prezent puse la îndoială din cauza utilizării unui LCG de calitate slabă ^[2] .

Dacă un generator congruențial liniar este inițializat cu un caracter și iterat, rezultatul este un cifru clasic simplu numit cifru afin ; acest cifru este ușor forțat cu o analiză frecventistă standard.

Exemple

Generatoare de bază

Graficul Generatorului Liniar definit pe lateral. Rețineți cum funcția este periodică a perioadei 4

Un exemplu de generator de bază poate fi dat de

a=3

{\ displaystyle a = 3}

{\ displaystyle a = 3}

c=1

{\ displaystyle c = 1}

{\ displaystyle c = 1}

m=5

{\ displaystyle m = 5}

{\ displaystyle m = 5}

X_{0}=1

{\ displaystyle X_ {0} = 1}

{\ displaystyle X_ {0} = 1}

Sau:

X_{i+1}=3\cdot X_{i}+1{\pmod {5}}

{\ displaystyle X_ {i + 1} = 3 \ cdot X_ {i} +1 {\ pmod {5}}}

{\ displaystyle X_ {i + 1} = 3 \ cdot X_ {i} +1 {\ pmod {5}}}

Secvența generată este:

X_{1}=3\cdot X_{0}+1{\pmod {5}}=4

{\ displaystyle X_ {1} = 3 \ cdot X_ {0} +1 {\ pmod {5}} = 4}

{\ displaystyle X_ {1} = 3 \ cdot X_ {0} +1 {\ pmod {5}} = 4}

X_{2}=3\cdot X_{1}+1{\pmod {5}}=3

{\ displaystyle X_ {2} = 3 \ cdot X_ {1} +1 {\ pmod {5}} = 3}

{\ displaystyle X_ {2} = 3 \ cdot X_ {1} +1 {\ pmod {5}} = 3}

X_{3}=3\cdot X_{2}+1{\pmod {5}}=0

{\ displaystyle X_ {3} = 3 \ cdot X_ {2} +1 {\ pmod {5}} = 0}

{\ displaystyle X_ {3} = 3 \ cdot X_ {2} +1 {\ pmod {5}} = 0}

X_{4}=3\cdot X_{3}+1{\pmod {5}}=1

{\ displaystyle X_ {4} = 3 \ cdot X_ {3} +1 {\ pmod {5}} = 1}

{\ displaystyle X_ {4} = 3 \ cdot X_ {3} +1 {\ pmod {5}} = 1}

X_{5}=3\cdot X_{4}+1{\pmod {5}}=4

{\ displaystyle X_ {5} = 3 \ cdot X_ {4} +1 {\ pmod {5}} = 4}

{\ displaystyle X_ {5} = 3 \ cdot X_ {4} +1 {\ pmod {5}} = 4}

X_{6}=3\cdot X_{5}+1{\pmod {5}}=3

{\ displaystyle X_ {6} = 3 \ cdot X_ {5} +1 {\ pmod {5}} = 3}

{\ displaystyle X_ {6} = 3 \ cdot X_ {5} +1 {\ pmod {5}} = 3}

Perioada este egală cu patru.

Exemple de utilizare

Cel mai eficient generator congruențial liniar are m egală cu o putere de 2, adesea m = 2 ³² sau m = 2 ^64, deoarece acest lucru vă permite să calculați operația modulo pur și simplu prin trunchierea celor mai puțin semnificativi 32 sau 64 de biți. Următorul tabel listează parametrii LCG utilizați în mod obișnuit, inclusiv funcțiile rand () ale unor compilatoare .

Sursă	m	la	c	biți de ieșire de semințe în rand () / aleator (L)
Rețete numerice	2 ³²	1664525	1013904223
Borland C / C ++	2 ³²	22695477	1	biți 30..16 în rand () , 30..0 în lrand ()
glibc (folosit de GCC ) ^[3]	2 ³²	1103515245	1 2 3 4 5	biți 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C / C ++	2 ³²	1103515245	1 2 3 4 5	biți 30..16
Borland Delphi , Virtual Pascal	2 ³²	134775813	1	biți 63..32 din (semințe L)*
Microsoft Visual / Quick C / C ++	2 ³²	214013	2531011	biți 30..16
Apple CarbonLib	2 ³¹ - 1	16807	0	vezi Park - Miller RNG
Donald Knuth lui cat merita de fapt	2 ⁶⁴	6364136223846793005	1442695040888963407
VAX 's MTH $ RANDOM , ^[4] versiuni vechi ale glibc	2 ³²	69069	1
Clasă aleatorie în API-ul Java	2 ⁴⁸	25214903917	11	biți 48 ... 17

^{[ fără sursă ]}

După cum se arată mai sus, LCG nu folosește întotdeauna toți biții pe care îi produce. Implementarea Java produce 48 de biți la fiecare iterație, dar doar cei mai semnificativi 32 de biți sunt returnați ca rezultat. Acest lucru se datorează faptului că cei mai semnificativi biți au o perioadă mai lungă. Algoritmii care utilizează această soluție sunt mai buni.

Avantaje și dezavantaje

Generatoarele liniare congruente necesită memorie minimă (de obicei 32 sau 64 biți) pentru a stoca starea.

Hiperplane ale unui generator congruențial liniar în trei dimensiuni

LCG-urile nu ar trebui utilizate în aplicații în care utilizarea aleatoriei ridicate este critică.

De exemplu, acestea nu sunt potrivite pentru simulările Monte Carlo, deoarece au o corelație între ele. Acestea nu trebuie utilizate în criptografie.

Mai mult, acești algoritmi tind să aibă unele defecte. De exemplu, dacă se folosește un LCG pentru a alege puncte într-un spațiu n-dimensional, punctele se află pe hipere cu cel mult m ^{1 / n-} dimensional ( teorema lui Marsaglia ). Acest lucru se datorează unei corelații între valorile succesive ale secvenței.

O altă problemă este că în LCG-urile biții cel mai puțin semnificativi ai secvenței generate au o perioadă mai scurtă decât cea a secvenței dacă m este setat să fie o putere de 2. În general, a n-a cea mai mică cifră din baza b a secvența produsă, unde este $b^{k}=m$ ${\ displaystyle b ^ {k} = m}$ ${\ displaystyle b ^ {k} = m}$ pentru un număr întreg k , se repetă cu cel mult un punct $b^{n}$ ${\ displaystyle b ^ {n}}$ ${\ displaystyle b ^ {n}}$ .

În ciuda acestui fapt, LGC-urile pot fi o alegere bună în anumite contexte, cum ar fi sistemele încorporate, unde memoria disponibilă este adesea foarte limitată; chiar și în cazul unui joc video, luarea unui număr mic dintre cei mai semnificativi biți poate fi suficientă. Niciodată nu trebuie folosiți cei mai puțin semnificativi biți ai unui LCG în care m este o putere de 2.

Comparație cu alte metode

Dacă trebuie să aveți numere pseudorandom de calitate și o anumită memorie este disponibilă (~ 2 kiloocteți ), atunci algoritmul Mersenne Twister oferă o perioadă mult mai lungă (2 ^ 19937-1)

Notă

^ Knuth 1997, pp. 17-19
^ Press, William H., și colab., Numerical Recipes in Fortran 77: The Art of Scientific Computing , 2nd, 1992, ISBN 0-521-43064-X .
^ Funcția rand () din stdlib.h în biblioteca GNU C folosește un generator liniar congruent simplu (cu o singură stare) numai în cazul în care starea este declarată ca 8 octeți. Dacă starea este mai mare (o matrice), generatorul devine un generator de feedback aditiv și perioada crește. Vedeți codul simplificat care redă secvența aleatorie a bibliotecii.
^ Biblioteca științifică GNU: Alte generatoare de numere aleatorii

Elemente conexe

linkuri externe

Generare de numere aleatorii ( PDF ) ^{[ link rupt ]} , pe www-tlc.deis.unibo.it .
Generator de numere aleatorii (Regiunea Emilia-Romagna) , pe Regione.emilia-romagna.it .

Portal de criptografie

Portalul de matematică

[Knuth-1997-1] Knuth 1997, pp. 17-19

[2] Press, William H., și colab., Numerical Recipes in Fortran 77: The Art of Scientific Computing , 2nd, 1992, ISBN 0-521-43064-X .

[3] Funcția rand () din stdlib.h în biblioteca GNU C folosește un generator liniar congruent simplu (cu o singură stare) numai în cazul în care starea este declarată ca 8 octeți. Dacă starea este mai mare (o matrice), generatorul devine un generator de feedback aditiv și perioada crește. Vedeți codul simplificat care redă secvența aleatorie a bibliotecii.

[4] Biblioteca științifică GNU: Alte generatoare de numere aleatorii

[1]

[2]

[3]

[4]