Invers kongruent metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. april 2020; checks kræver 3 redigeringer .

Den inverse kongruentielle metode (eller Eichenauer-Lehn-generator , også muligvis Eichenauer-Lehn ) er en pseudo-tilfældig talgenereringsmetode baseret på at bruge det inverse modulo-tal til at generere det næste medlem af sekvensen.

Beskrivelse

Den omvendte kongruentielle metode blev foreslået af Eichenauer og Lehn i 1986 [1] som en erstatning for den ikke-gitter lineære kongruentielle metode [2] .

Denne metode består i at beregne en sekvens af tilfældige tal i ringen af rester modulo et naturligt tal . $X_{{n}}$ $n$

Den væsentligste forskel fra den lineære metode er, at når du genererer en sekvens, bruges tallet invers til det forrige element i stedet for selve det forrige element.

Generatorparametrene er [3] :

$frø$ - salt
$-en$ - multiplikator $(0\leqslant a<n)$
$b$ - stigning $(0\leqslant b<n)$

I tilfælde af et simpelt n

Værdien af sekvensmedlemmerne er givet som:

$x_{0}=frø$
$x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n$	hvis $x_{i}\neq 0$
$x_{i+1}=b$	hvis $x_{i}=0$

I tilfælde af sammensat n

Hvis tallet er sammensat, beregnes elementerne i sekvensen som følger: $X_{{n}}$

$x_{0}=frø$
$x_{i+1}\equiv (ax_{i}^{-1}+b)\mod n$

Parametrene er valgt på en sådan måde, at . $(frø,n)=1;(a,n)=1$

Periode

Sekvensen er periodisk, og perioden overstiger ikke ringens dimension . Den maksimale periode nås, hvis polynomiet er primitivt . En tilstrækkelig betingelse for sekvensens maksimale periode er et sådant valg af konstanter , og at polynomiet er irreducerbart [4] . $x_{i+1}$ $n$ $n$ $f(x)=x^{2}-bx-a\in \mathbb {F} _{n}[x]$ $-en$ $b$ $f(x)$

I tilfælde af en komposit er den maksimalt mulige periode ( Euler funktion ) [5] . $n$ $\varphi (n)$

Eksempel

Den inverse kongruentiale generator med parametre genererer en sekvens i ringen , hvor tallene og , samt og er omvendt til hinanden. I dette eksempel er polynomiet irreducerbart i, og tallene er ikke dets rødder, på grund af hvilket perioden er maksimal og lig med . $n=5,a=2,b=3,frø=1$ $\{1,0,3,2,4,1,...\}$ $\mathbb {F} _{5}$ $en$ $fire$ $2$ $3$ $f(x)=x^{2}-3x-2$ $\mathbb {F} _{5}[x]$ $0.1.2.3.4$ $n=5$

Implementeringseksempler

Python

Koden def egcd ( a , b ): hvis a == 0 : return ( b , 0 , 1 ) ellers : g , y , x = egcd ( b % a , a ) return ( g , x - ( b // a ) * å , å ) def modinv ( a , m ): gcd , x , y = egcd ( a , m ) hvis gcd != 1 : return Ingen # modulær invers eksisterer ikke andet : return x % m def ICG ( n , a , c , frø ): hvis ( frø == 0 ): returner c return ( a * modinv ( frø , n ) + c ) % n frø = 1 n = 5 a = 2 c = 3 antal = 10 for i i området ( antal ): udskriv ( frø ) frø = ICG ( n , a , c , frø )

C++

Koden #include <iostream> bruger navneområde std ; int mod_inv ( int a , int n ) { int b0 = n , t , q ; int x0 = 0 , x1 = 1 ; hvis ( n == 1 ) returner 1 ; mens ( a > 1 ) { q = a / n ; t = n , n = a % n , a = t ; t = x0 , x0 = xl - q * x0 , xl = t ; } if ( x1 < 0 ) x1 += b0 ; returnere x1 ; } int ICG ( int n , int a , int c , int frø ) { hvis ( frø == 0 ) returnere c ; return ( a * mod_inv ( frø , n ) + c ) % n ; } int main ( void ) { int frø = 1 ; int n = 5 ; int a = 2 ; int c = 3 ; int count = 10 ; for ( int i = 0 ; i < tælle ; i ++ ) { cout << frø << endl ; frø = ICG ( n , a , c , frø ); } returnere 0 ; }

Sammensatte inverse generatorer

Den største ulempe ved inverse kongruentielle generatorer er stigningen i beregningskompleksitet med stigende periode. Denne mangel korrigeres i sammensatte inverse kongruentiale generatorer.

Konstruktionen af sammensatte inverse generatorer er en kombination af to eller flere invers kongruente generatorer.

Lade være forskellige primtal, hver . For hvert indeks indenfor , lad være en sekvens af elementer med periode . Med andre ord . $p_{1},\dots ,p_{r}$ $p_{j}\geq 5$ $j$ $1\leq j\ \leq r$ $\{y_{n}^{(j)}\}_{n\geq 0}$ $\i \mathbb {F} _{p_{j}}$ $p_{j}$ $\{y_{n}^{(j)}|0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}$

Lade være en sekvens af tilfældige tal inden for , hvor . $\{x_{n}^{(j)}\}_{n\geq 0}$ $x_{n}^{(j)}\in [0;1]$ $x_{n}^{(j)}={\frac {y_{n}^{(j)}}{p_{j}}};{n\geq 0};1\leq j\ \leq r$

Den resulterende sekvens er defineret som summen af: . $(x_{n})_{n\geq 0}$ $x_{n}:=x_{n}^{(1)}+x_{n}^{(2)}+\dots +x_{n}^{(r)}\mod 1$

Perioden for den resulterende sekvens [6] . $T=p_{1}p_{2}\dots p_{r}$

En af fordelene ved denne tilgang er evnen til at bruge inverse kongruentiale generatorer, der kører parallelt.

Et eksempel på en sammensat invers generator

Lad og . For nemheds skyld, lad os sætte og . For hver vi beregner . $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}}$

Så . Det vil sige, at vi fik en sekvens med et punktum . $(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$

For at slippe af med brøktal kan vi gange hvert element i den resulterende sekvens med og få en sekvens af heltal: $35$ $(x_{n}^{(int)})_{n\geq 0}=\{0,$ $12,$ $24,$ $en,$ $13,$ $25,$ $2,$ $fjorten,$ $26,$ $3,$ $femten,$ $26,$ $fire,$ $16,$ $28,$ $5,$ $17,$ $28,$ $6,$ $atten,$ $tredive,$ $7,$ $19,$ $31,$ $otte,$ $tyve,$ $32,$ $9,$ $21,$ $33,$ $ti,$ $22,$ $34,$ $elleve,$ $22,$ $0\}$

Fordele ved inverse kongruentiale generatorer

Inverse kongruentiale generatorer bruges til praktiske formål af en række årsager.

For det første har inverse kongruente generatorer ret god ensartethed [7] , derudover er de resulterende sekvenser fuldstændig blottet for den gitterstruktur, der er karakteristisk for lineære kongruente generatorer [1] [8] [9] .

For det andet har de binære sekvenser opnået ved hjælp af ICG ikke uønskede statistiske afvigelser. Sekvenserne opnået ved denne metode er blevet verificeret ved en række statistiske test og forbliver stabile med skiftende parametre [7] [8] [10] [11] .

For det tredje har sammensatte oscillatorer de samme egenskaber som enkelte lineære inverse oscillatorer [12] , men samtidig har de en periode, der væsentligt overstiger perioden for enkeltoscillatorer [13] . Derudover giver enheden af sammensatte generatorer mulighed for at opnå en høj ydeevneforøgelse, når den bruges på multiprocessorsystemer [14] .

Der er en algoritme, der tillader udvikling af sammensatte generatorer med forudsigelig periodelængde og kompleksitet, samt gode statistiske egenskaber for outputsekvenserne [15] .

Ulemper ved inverse kongruentiale generatorer

Den største ulempe ved inverse kongruentiale generatorer er den langsomme hastighed for at generere elementer i sekvensen: beregningen af et element i sekvensen kræver multiplikationsoperationer [16] $O(\log n)$ .

Noter

↑ 1 2 Knut, 2013 , s. 45.
↑ Eichenauer, Lehn, 1986 .
↑ Hellekalek, 1995 , s. 255: "Vi skal vælge modulet p, en multiplikator a, en additiv led b."
↑ Amy Glen: On the Period Length of Pseudorandom Number Sequences, 2002 , 5.3, s. 67: "Hvis x2-bx-a er et primitivt polynomium over Fp, så har Xi fuld periodelængde p".
↑ Amy Glen: On the Period Length of Pseudorandom Number Sequences, 2002 , 5.4, s. 69: "Sekvensen Xi er rent periodisk med periodelængde d ≤ φ(m)".
↑ Hellekalek, 1995 , s. 256: "Det er elementært at se, at perioden for sekvensen (Xn)n er lig med M := p1*p2*...* pr".
↑ 1 2 Eichenauer-Herrmann, Niederreiter, 1992 .
↑ 1 2 Eichenauer-Herrmann, 1991 .
↑ Eichenauer-Herrmann, Grothe, Niederreiter et al., 1990 , s. 81: "Disse generatorer viser ikke den simple gitterstruktur af de meget anvendte lineære kongruentiale generatorer."
↑ Eichenauer-Herrmann, 1993 .
↑ Hellekalek, 1995 , s. 261: "De fremragende teoretiske og empiriske egenskaber ved inversive metoder forbliver stabile under variationen af parametre, forudsat at vi har maksimal periodelængde".
↑ Bubicz, Stoklosa, 2006 , s. 2: "Sammensat tilgang giver de samme fremragende egenskaber ved producerede sekvenser som enkelte inversive generatorer".
↑ Bubicz, Stoklosa, 2006 , s. 2: "Sammensatte inversive generatorer gør det muligt at opnå periodelængde betydeligt større end opnået med en enkelt ICG".
↑ Bubicz, Stoklosa, 2006 , s. 2: "De ser ud til at være designet til anvendelse med multiprocessor parallelle hardwareplatforme."
↑ Bubicz, Stoklosa, 2006 , s. 2: "Der findes en stabil og enkel måde at vælge parameter på, baseret på Chou-algoritmen. Det garanterer maksimal længde".
↑ Anne Gille-Genest: Pseudo-Random Numbers Generators, 2012 , s. 12: "Den største ulempe ved de begge inverse generatorer er, at en beregning af et tilfældigt tal tager O(log m ) multiplikation i F m , så algoritmen er ikke hurtig."

Litteratur

Bøger

Knut D. E. The Art of Programming : Bind 2. Opnåede algoritmer - 3 - M . : Williams , 2013. - 828 s. — ISBN 978-5-8459-0081-4

Artikler

Eichenauer J. , Lehn J. En ikke-lineær kongruentiel pseudo-tilfældig talgenerator (engelsk) // Statistische Hefte - Springer Berlin Heidelberg , Springer Science + Business Media , 1986. - Vol. 27, Iss. 1. - S. 315-326. — ISSN 0932-5026 ; 1613-9798 - doi:10.1007/BF02932576
Eichenauer-Herrmann J. , Grothe H. , Niederreiter H. , Topuzoǧlu A. På gitterstrukturen af en ikke-lineær generator med modul 2ᵅ (engelsk) // J. Comput. Appl. Matematik. - Elsevier BV , 1990. - Vol. 31, Iss. 1. - S. 81-85. — ISSN 0377-0427 ; 1879-1778 - doi:10.1016/0377-0427(90)90338-Z
Eichenauer-Herrmann J. Inversive kongruentielle pseudorandom-tal undgår flyene // Math . Comp. - AMS , 1991. - Vol. 56, Iss. 193. - S. 297-301. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2008543
Eichenauer-Herrmann J. , Niederreiter H. Nedre grænser for uoverensstemmelsen mellem inversive kongruentielle pseudotilfældige tal med en magt af to modul // Math . Comp. - AMS , 1992. - Vol. 58, Iss. 198. - S. 775-779. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2153216
Eichenauer-Herrmann J. Statistisk uafhængighed af en ny klasse af inversive kongruentielle pseudorandom-tal // Math . Comp. - AMS , 1993. - Vol. 60. - S. 375-384. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1993-1159168-9
Chou W. S. På inversive maksimalperiodepolynomier over endelige felter (engelsk) // Appl. Algebr. Eng. Comm. - Springer Science + Business Media , 1995. - Vol. 6, Iss. 4. - S. 245-250. — ISSN 0938-1279 ; 1432-0622 - doi:10.1007/BF01235718
Hellekalek P. Inversive pseudorandom-talgeneratorer: koncepter, resultater og links (engelsk) // WSC'95 : Proceedings, 1995 Winter Simulation Conference / D. Goldsman , C. Alexopoulos - Washington : IEEE Computer Society , 1995. - S. 255 - 262. — 1463 s. - ISBN 978-0-7803-3018-4 - doi:10.1145/224401.224612
Bubicz J. , Stoklosa J. Compound Inversive Congruential Generator Design Algorithm (engelsk) // IMCSIT 2006 : Proceedings of the 4th International Multiconference on Computer Science and Information Technology - Amman : ASPU , 2006. - Vol. 1. - S. 1-6.
Gille Genest Anne. Pseudo-tilfældige talgeneratorer . — 2012. (utilgængeligt link)
Glen Amy. Om periodelængden af pseudorandom-talsekvenser // University of Adelaide: Honours in Pure Mathematics. - 2002.