Metoda congruentă inversă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 aprilie 2020; verificările necesită 3 modificări .

Metoda congruențială inversă (sau generatorul Eichenauer-Lehn , eventual și Eichenauer-Lehn ) este o metodă de generare a numerelor pseudoaleatoare bazată pe utilizarea numărului modulo invers pentru a genera următorul membru al secvenței.

Descriere

Metoda congruențială inversă a fost propusă de Eichenauer și Lehn în 1986 [1] ca înlocuitor pentru metoda congruențială liniară non-latice [2] .

Această metodă constă în calcularea unei succesiuni de numere aleatorii din inelul de reziduuri modulo un număr natural . $X_{{n}}$ $n$

Principala diferență față de metoda liniară este că atunci când se generează o secvență, se folosește numărul invers față de elementul anterior în locul elementului anterior în sine.

Parametrii generatorului sunt [3] :

$sămânță$ - sare
$A$ - multiplicator $(0\leqslant a<n)$
$b$ - increment $(0\leqslant b<n)$

În cazul unui n simplu

Valoarea membrilor secvenței este dată astfel:

$x_{0}=sămânță$
$x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n$	dacă $x_{i}\neq 0$
$x_{i+1}=b$	dacă $x_{i}=0$

În cazul compozitului n

Dacă numărul este compus, elementele șirului se calculează după cum urmează: $X_{{n}}$

$x_{0}=sămânță$
$x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n$

Parametrii sunt aleși în așa fel încât . $(sămânță,n)=1;(a,n)=1$

Perioada

Secvența este periodică, iar perioada nu depășește dimensiunea inelului . Perioada maximă este atinsă dacă polinomul este primitiv . O condiție suficientă pentru perioada maximă a secvenței este o astfel de alegere a constantelor și ca polinomul să fie ireductibil [4] . $x_{i+1}$ $n$ $n$ $f(x)=x^{2}-bx-a\in \mathbb {F} _{n}[x]$ $A$ $b$ $f(x)$

În cazul unui compus, perioada maximă posibilă este ( funcția Euler ) [5] . $n$ $\varphi (n)$

Exemplu

Generatorul congruențial invers cu parametri generează o secvență în inel , unde numerele și , precum și și sunt inverse unul față de celălalt. În acest exemplu, polinomul este ireductibil în și numerele nu sunt rădăcinile sale, datorită cărora perioada este maximă și egală cu . $n=5,a=2,b=3,sămânță=1$ $\{1,0,3,2,4,1,...\}$ $\mathbb {F} _{5}$ $unu$ $patru$ $2$ $3$ $f(x)=x^{2}-3x-2$ $\mathbb {F} _{5}[x]$ $0.1.2.3.4$ $n=5$

Exemple de implementare

Python

Codul def egcd ( a , b ): if a == 0 : return ( b , 0 , 1 ) else : g , y , x = egcd ( b % a , a ) return ( g , x - ( b // a ) * y , y ) def modinv ( a , m ): gcd , x , y = egcd ( a , m ) if gcd != 1 : return None # inversul modular nu există altfel : returnează x % m def ICG ( n , a , c , seed ): if ( seed == 0 ): return c return ( a * modinv ( seed , n ) + c ) % n sămânță = 1 n = 5 a = 2 c = 3 număr = 10 pentru i în interval ( număr ): imprimare ( seed ) seed = ICG ( n , a , c , seed )

C++

Codul #include <iostream> folosind namespace std ; int mod_inv ( int a , int n ) { int b0 = n , t , q ; int x0 = 0 , x1 = 1 ; dacă ( n == 1 ) returnează 1 ; în timp ce ( a > 1 ) { q = a / n ; t = n , n = a % n , a = t ; t = x0 , x0 = x1 - q * x0 , x1 = t ; } dacă ( x1 < 0 ) x1 += b0 ; întoarcere x1 ; } int ICG ( int n , int a , int c , int seed ) { dacă ( sămânță == 0 ) returnează c ; return ( a * mod_inv ( seed , n ) + c ) % n ; } int main ( void ) { int samanta = 1 ; int n = 5 ; int a = 2 ; int c = 3 ; număr int = 10 ; pentru ( int i = 0 ; i < număr ; i ++ ) { cout << sămânță << endl ; sămânță = ICG ( n , a , c , sămânță ); } returnează 0 ; }

Generatoare inverse compozite

Principalul dezavantaj al generatoarelor congruențiale inverse este creșterea complexității de calcul cu creșterea perioadei. Acest neajuns este corectat în generatoarele compuși congruențiale inverse.

Construcția generatoarelor inverse compozite este o combinație de două sau mai multe generatoare inverse congruente.

Fie numere prime distincte, fiecare . Pentru fiecare index din , fie o succesiune de elemente cu punct . Cu alte cuvinte, . $p_{1},\dots ,p_{r}$ $p_{j}\geq 5$ $j$ $1\leq j\ \leq r$ $\{y_{n}^{(j)}\}_{n\geq 0}$ $\in \mathbb {F} _{p_{j}}$ $pijamale}$ $\{y_{n}^{(j)}|0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}$

Fie o succesiune de numere aleatoare în , unde . $\{x_{n}^{(j)}\}_{n\geq 0}$ $x_{n}^{(j)}\în [0;1]$ $x_{n}^{(j)}={\frac {y_{n}^{(j)}}{p_{j}}};{n\geq 0};1\leq j\ \leq r$

Secvența rezultată este definită ca suma: . $(x_{n})_{n\geq 0}$ $x_{n}:=x_{n}^{(1)}+x_{n}^{(2)}+\dots +x_{n}^{(r)}\mod 1$

Perioada secvenței rezultate [6] . $T=p_{1}p_{2}\dots p_{r}$

Unul dintre avantajele acestei abordări este capacitatea de a utiliza generatoare congruențiale inverse care rulează în paralel.

Un exemplu de generator invers compus

Lasă și . Pentru simplitate, să punem și . Pentru fiecare calculăm . $r=2,p_{1}=5$ $p_{2}=7$ $(y_{k}^{(1)})_{k\geq 0}=(0,1,2,3,4,\dots)$ $(y_{k}^{(2)})_{k\geq 0}=(0,1,2,3,4,5,6,\dots)$ $1\leq n\leq 35$ $x_{n}={\frac {y_{n}^{(1)}}{5}}+{\frac {y_{n}^{(2))){7}}$

Apoi . Adică avem o secvență cu punct . $(x_{n})_{n\geq 0}=\{0.0,$ ${\displaystyle}$ $0,34$ ${\displaystyle}$ $0,69$ ${\displaystyle}$ $0,03,$ ${\displaystyle}$ $0,37$ ${\displaystyle}$ $0,71$ ${\displaystyle}$ $0,06,$ ${\displaystyle}$ $0,4$ ${\displaystyle}$ $0,74$ ${\displaystyle}$ $0,09,$ ${\displaystyle}$ $0,43$ ${\displaystyle}$ $0,77$ ${\displaystyle}$ $0,11$ ${\displaystyle}$ $0,46$ ${\displaystyle}$ $0,8$ ${\displaystyle}$ $0,14$ ${\displaystyle}$ $0,49$ ${\displaystyle}$ $0,83$ ${\displaystyle}$ $0,17$ ${\displaystyle}$ $0,51$ ${\displaystyle}$ $0,86$ ${\displaystyle}$ $0,2$ ${\displaystyle}$ $0,54$ ${\displaystyle}$ $0,89$ ${\displaystyle}$ $0,23$ ${\displaystyle}$ $0,57$ ${\displaystyle}$ $0,91$ ${\displaystyle}$ $0,26$ ${\displaystyle}$ $0,6$ ${\displaystyle}$ $0,94$ ${\displaystyle}$ $0,29$ ${\displaystyle}$ $0,63$ ${\displaystyle}$ $0,97$ ${\displaystyle}$ $0,31$ ${\displaystyle}$ $0,66$ ${\displaystyle}$ $0,0\}$ $5\times 7=35$

Pentru a scăpa de numerele fracționale, putem înmulți fiecare element al șirului rezultat și obținem o secvență de numere întregi: $35$ $(x_{n}^{(int)})_{n\geq 0}=\{0,$ $12,$ $24,$ $unu,$ $13,$ $25,$ $2,$ $paisprezece,$ $26,$ $3,$ $cincisprezece,$ $26,$ $patru,$ $16,$ $28,$ $5,$ $17,$ $28,$ $6,$ $optsprezece,$ $treizeci,$ $7,$ $19,$ $31,$ $opt,$ $douăzeci,$ $32,$ $9,$ $21,$ $33,$ $zece,$ $22,$ $34,$ $unsprezece,$ $22,$ $0\}$

Beneficiile generatoarelor congruențiale inverse

Generatoarele congruențiale inverse sunt utilizate în scopuri practice din mai multe motive.

În primul rând, generatoarele congruente inverse au o uniformitate destul de bună [7] , în plus, secvențele rezultate sunt complet lipsite de structura rețelei caracteristică generatoarelor congruente liniare [1] [8] [9] .

În al doilea rând, secvențele binare obținute folosind ICG nu au abateri statistice nedorite. Secvențele obținute prin această metodă au fost verificate printr-un număr de teste statistice și rămân stabile cu modificarea parametrilor [7] [8] [10] [11] .

În al treilea rând, oscilatorii compuși au aceleași proprietăți ca și oscilatorii liniari unici invers [12] , dar în același timp au o perioadă care depășește semnificativ perioada oscilatoarelor unice [13] . În plus, dispozitivul generatoarelor compozite permite obținerea unei creșteri de performanță ridicate atunci când este utilizat pe sisteme multiprocesor [14] .

Există un algoritm care permite dezvoltarea unor generatoare compozite cu lungimea perioadei și complexitatea previzibile, precum și proprietăți statistice bune ale secvențelor de ieșire [15] .

Dezavantajele generatoarelor congruențiale inverse

Principalul dezavantaj al generatoarelor congruențiale inverse este viteza lentă de generare a elementelor secvenței: calculul unui element al secvenței necesită operații de înmulțire [16] $O(\log n)$ .

Note

↑ 1 2 Knut, 2013 , p. 45.
↑ Eichenauer, Lehn, 1986 .
↑ Hellekalek, 1995 , p. 255: „Trebuie să alegem modulul p, un multiplicator a, un termen aditiv b”.
↑ Amy Glen: On the Period Length of Pseudorandom Number Sequences, 2002 , 5.3, p. 67: „Dacă x2-bx-a este un polinom primitiv peste Fp, atunci Xi are perioada completă p”.
↑ Amy Glen: On the Period Length of Pseudorandom Number Sequences, 2002 , 5.4, p. 69: „Secvența Xi este pur periodică cu lungimea perioadei d ≤ φ(m)”.
↑ Hellekalek, 1995 , p. 256: „Este elementar să vedem că perioada șirului (Xn)n este egală cu M := p1*p2*...* pr”.
↑ 1 2 Eichenauer-Herrmann, Niederreiter, 1992 .
↑ 1 2 Eichenauer-Herrmann, 1991 .
↑ Eichenauer-Herrmann, Grothe, Niederreiter et al, 1990 , p. 81: „Acești generatori nu arată structura simplă de rețea a generatoarelor congruențiale liniare utilizate pe scară largă”.
↑ Eichenauer-Herrmann, 1993 .
↑ Hellekalek, 1995 , p. 261: „Excelentele proprietăți teoretice și empirice ale metodelor inversive rămân stabile sub variația parametrilor, cu condiția să avem lungimea maximă a perioadei”.
↑ Bubicz, Stoklosa, 2006 , p. 2: „Abordarea compusă oferă aceleași proprietăți remarcabile ale secvențelor produse ca și generatoarele inversive unice”.
↑ Bubicz, Stoklosa, 2006 , p. 2: „Generatoarele inversive compuși permit obținerea unei perioade semnificativ mai mari decât cea obținută de un singur ICG”.
↑ Bubicz, Stoklosa, 2006 , p. 2: „Par a fi proiectate pentru aplicații cu platforme hardware paralele cu multiprocesor.”
↑ Bubicz, Stoklosa, 2006 , p. 2: „Există o modalitate constantă și simplă de alegere a parametrilor, bazată pe algoritmul Chou. Acesta garantează lungimea maximă”.
↑ Anne Gille-Genest: Pseudo-Random Numbers Generators, 2012 , p. 12: „Principalul dezavantaj al acelor ambele generatoare inverse este că un calcul al unui număr aleatoriu necesită înmulțirea O(log m ) în Fm , astfel încât algoritmul nu este rapid.”

Literatură

Cărți

Knut D. E. The Art of Programming : Volumul 2. Obtained Algorithms - 3 - M . : Williams , 2013. - 828 p. — ISBN 978-5-8459-0081-4

Articole

Eichenauer J. , Lehn J. Un generator de numere pseudoaleatoare congruențiale neliniare (engleză) // Statistische Hefte - Springer Berlin Heidelberg , Springer Science + Business Media , 1986. - Vol. 27, Iss. 1. - P. 315-326. — ISSN 0932-5026 ; 1613-9798 - doi:10.1007/BF02932576
Eichenauer-Herrmann J. , Grothe H. , Niederreiter H. , Topuzoǧlu A. Despre structura rețelei a unui generator neliniar cu modul 2ᵅ (engleză) // J. Comput. Aplic. Matematică. - Elsevier BV , 1990. - Vol. 31, Iss. 1. - P. 81-85. — ISSN 0377-0427 ; 1879-1778 - doi:10.1016/0377-0427(90)90338-Z
Eichenauer-Herrmann J. Numerele pseudoaleatoare congruențiale inversive evită planurile // Math . Comp. - AMS , 1991. - Vol. 56, Iss. 193. - P. 297-301. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2008543
Eichenauer-Herrmann J. , Niederreiter H. Limite inferioare pentru discrepanța numerelor pseudoaleatoare congruențiale inversive cu putere de doi module // Math . Comp. - AMS , 1992. - Vol. 58, Iss. 198. - P. 775-779. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2153216
Eichenauer-Herrmann J. Independenta statistica a unei noi clase de numere pseudoaleatoare congruentiale inversive // Math . Comp. - AMS , 1993. - Vol. 60. - P. 375-384. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1993-1159168-9
Chou W. S. Despre polinoame cu perioade maxime inversive peste câmpuri finite (engleză) // Appl. Algebr. ing. Comm. - Springer Science + Business Media , 1995. - Vol. 6, Iss. 4. - P. 245-250. — ISSN 0938-1279 ; 1432-0622 - doi:10.1007/BF01235718
Hellekalek P. Generatori de numere pseudoaleatoare inversive: concepte, rezultate și legături (engleză) // WSC'95 : Proceedings, 1995 Winter Simulation Conference / D. Goldsman , C. Alexopoulos - Washington : IEEE Computer Society , 1995. - P. 255 - 262. — 1463 p. - ISBN 978-0-7803-3018-4 - doi:10.1145/224401.224612
Bubicz J. , Stoklosa J. Compound Inversive Congruential Generator Design Algorithm (engleză) // IMCSIT 2006 : Proceedings of the 4th International Multiconference on Computer Science and Information Technology - Amman : ASPU , 2006. - Vol. 1. - P. 1-6.
Gille Genest Anne. Generatoare de numere pseudo-aleatoare . — 2012. (link inaccesibil)
Glen Amy. Despre durata perioadei de secvențe de numere pseudorandom // Universitatea din Adelaide: Honors in Pure Mathematics. — 2002.