Inverz kongruens módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. április 30-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Az inverz kongruenciális módszer (vagy Eichenauer-Lehn generátor , esetleg Eichenauer-Lehn is) egy pszeudo-véletlen számgeneráló módszer , amely az inverz moduloszám felhasználásán alapul a sorozat következő tagjának generálásához.

Leírás

Az inverz kongruenciális módszert Eichenauer és Lehn javasolta 1986-ban [1] a nem rácsos lineáris kongruenciális módszer [2] helyettesítésére .

Ez a módszer abból áll, hogy véletlen számok sorozatát számítják ki a maradékok gyűrűjében természetes szám modulo . $X_{{n}}$ $n$

A fő különbség a lineáris módszerhez képest az, hogy sorozat generálásakor az előző elem helyett az előző elemhez képest inverz szám kerül felhasználásra.

A generátor paraméterei a következők : [3] :

$mag$ - só
$a$ - szorzó $(0\leqslant a<n)$
$b$ - növekmény $(0\leqslant b<n)$

Egyszerű n esetén

A sorozattagok értéke a következőképpen van megadva:

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

Összetett n esetén

Ha a szám összetett, a sorozat elemeit a következőképpen számítjuk ki: $X_{{n}}$

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

A paramétereket úgy választjuk meg, hogy . $(mag,n)=1;(a,n)=1$

Időszak

A sorozat periodikus, és a periódus nem haladja meg a gyűrű méretét . A maximális periódus akkor érhető el, ha a polinom primitív . A sorozat maximális periódusának elegendő feltétele az állandók ilyen megválasztása és az, hogy a polinom irreducibilis legyen [4] . $x_{i+1}$ $n$ $n$ $f(x)=x^{2}-bx-a\in \mathbb {F} _{n}[x]$ $a$ $b$ $f(x)$

Kompozit esetén a maximális lehetséges periódus ( Euler függvény ) [5] . $n$ $\varphi (n)$

Példa

A paraméterekkel rendelkező inverz kongruenciális generátor egy sorozatot generál a gyűrűben , ahol a és a számok , valamint a és inverzek egymással. Ebben a példában a polinom irreducibilis -ben, és a számok nem a gyökei, ezért a periódus maximális és egyenlő . $n=5,a=2,b=3,mag=1$ $\{1,0,3,2,4,1,...\}$ $\mathbb {F} _{5}$ $egy$ $négy$ $2$ $3$ $f(x)=x^{2}-3x-2$ $\mathbb {F} _{5}[x]$ $0.1.2.3.4$ $n=5$

Megvalósítási példák

Python

A kód def egcd ( a , b ): ha 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 # moduláris inverz nem létezik else : return x % m def ICG ( n , a , c , seed ): if ( seed == 0 ): return c return ( a * modinv ( seed , n ) + c ) % n mag = 1 n = 5 a = 2 c = 3 szám = 10 i tartományban ( szám ) : print ( mag ) seed = ICG ( n , a , c , seed ) _

C++

A kód #include <iostream> névtér használata std ; int mod_inv ( int a , int n ) { int b0 = n , t , q ; int x0 = 0 , x1 = 1 ; if ( n == 1 ) return 1 ; míg ( a > 1 ) { q = a / n ; t = n , n = a % n , a = t ; t = x0 , x0 = x1 - q * x0 , x1 = t ; } if ( x1 < 0 ) x1 += b0 ; vissza x1 ; } int ICG ( int n , int a , int c , int seed ) { ha ( mag == 0 ) visszatér c ; return ( a * mod_inv ( seed , n ) + c ) % n ; } int main ( void ) { int mag = 1 ; int n = 5 ; int a = 2 ; int c = 3 ; int count = 10 ; for ( int i = 0 ; i < count ; i ++ ) { cout << mag << endl ; mag = ICG ( n , a , c , mag ); } return 0 ; }

Kompozit inverz generátorok

Az inverz kongruenciális generátorok fő hátránya a számítási bonyolultság növekedése a periódus növekedésével. Ezt a hiányosságot az összetett inverz kongruenciális generátorok javítják.

A kompozit inverz generátorok felépítése két vagy több inverz kongruens generátor kombinációja.

Legyenek külön prímszámok, mindegyik . Legyen minden indexen belüli elem sorozata ponttal . Más szóval, . $p_{1},\pontok,p_{r}$ $p_{j}\geq 5$ $j$ $1\leq j\ \leq r$ $\{y_{n}^{(j)}\}_{n\geq 0}$ $\in \mathbb {F} _{p_{j}}$ $p_{j}$ $\{y_{n}^{(j)}|0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}$

Legyen véletlen számok sorozata belül , ahol . $\{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$

Az eredményül kapott sorozatot a következők összegeként határozzuk meg: . $(x_{n})_{n\geq 0}$ $x_{n}:=x_{n}^{(1)}+x_{n}^{(2)}+\pontok +x_{n}^{(r)}\mod 1$

A kapott sorozat periódusa [6] . $T=p_{1}p_{2}\dots p_{r}$

Ennek a megközelítésnek az egyik előnye a párhuzamosan futó inverz kongruenciális generátorok használata.

Példa egy összetett inverz generátorra

Hagyjuk és . Az egyszerűség kedvéért tegyük fel és . Mindegyikre kiszámoljuk . $r=2,p_{1}=5$ $p_{2}=7$ $(y_{k}^{(1)})_{k\geq 0}=(0,1,2,3,4,\pontok)$ $(y_{k}^{(2)})_{k\geq 0}=(0,1,2,3,4,5,6,\pontok)$ $1\leq n\leq 35$ $x_{n}={\frac {y_{n}^{(1)}}{5}}+{\frac {y_{n}^{(2))){7}}$

Akkor . Vagyis egy ponttal rendelkező sorozatot kaptunk . $(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$

A törtszámok megszabadulása érdekében a kapott sorozat minden elemét megszorozhatjuk, és egész számsorozatot kaphatunk: $35$ $(x_{n}^{(int)})_{n\geq 0}=\{0,$ $12,$ $24,$ $egy,$ $13,$ $25,$ $2,$ $tizennégy,$ $26,$ $3,$ $tizenöt,$ $26,$ $négy,$ $16,$ $28,$ $5,$ $17,$ $28,$ $6,$ $tizennyolc,$ $harminc,$ $7,$ $19,$ $31,$ $nyolc,$ $húsz,$ $32,$ $9,$ $21,$ $33,$ $tíz,$ $22,$ $34,$ $tizenegy,$ $22,$ $0\}$

Az inverz kongruenciális generátorok előnyei

Az inverz kongruenciális generátorokat számos okból gyakorlati célokra használják.

Először is, az inverz kongruens generátorok meglehetősen jó egyenletességgel rendelkeznek [7] , ráadásul az így kapott sorozatokból teljesen hiányzik a lineáris kongruens generátorokra jellemző rácsszerkezet [1] [8] [9] .

Másodszor, az ICG-vel kapott bináris szekvenciák nem rendelkeznek nem kívánt statisztikai eltérésekkel. Az ezzel a módszerrel kapott szekvenciákat számos statisztikai teszttel igazolták, és változó paraméterekkel stabilak maradnak [7] [8] [10] [11] .

Harmadszor, az összetett oszcillátorok tulajdonságai megegyeznek az egyszeres lineáris inverz oszcillátorokéval [12] , ugyanakkor periódusuk jelentősen meghaladja az egyszeres oszcillátorok periódusát [13] . Ezenkívül a kompozit generátorok eszköze lehetővé teszi nagy teljesítménynövekedés elérését, ha többprocesszoros rendszereken használják [14] .

Létezik egy algoritmus, amely előre megjósolható periódushosszú és összetettségű kompozit generátorok fejlesztését teszi lehetővé, valamint a kimeneti sorozatok jó statisztikai tulajdonságaival [15] .

Az inverz kongruenciális generátorok hátrányai

Az inverz kongruenciális generátorok fő hátránya a sorozat elemeinek generálásának lassú sebessége: a sorozat egy elemének kiszámításához szorzási műveletek szükségesek [16] $O(\log n)$ .

Jegyzetek

↑ 1 2 Knut, 2013 , p. 45.
↑ Eichenauer, Lehn, 1986 .
↑ Hellekalek, 1995 , p. 255: "Ki kell választanunk a p modulust, egy a szorzót, egy b additív tagot."
↑ Amy Glen: On the Period Length of Pseudorandom Number Sequences, 2002 , 5.3, p. 67: "Ha x2-bx-a egy primitív polinom Fp felett, akkor Xi teljes p periódushosszú".
↑ Amy Glen: Az álvéletlen számsorozatok periódushosszáról, 2002 , 5.4, p. 69: "A Xi sorozat tisztán periodikus, periódushossza d ≤ φ(m)".
↑ Hellekalek, 1995 , p. 256: "Elemi látni, hogy az (Xn)n sorozat periódusa egyenlő M := p1*p2*...* pr".
↑ 1 2 Eichenauer-Herrmann, Niederreiter, 1992 .
↑ 1 2 Eichenauer-Herrmann, 1991 .
↑ Eichenauer-Herrmann, Grothe, Niederreiter et al, 1990 , p. 81: "Ezek a generátorok nem mutatják a széles körben használt lineáris kongruenciális generátorok egyszerű rácsszerkezetét."
↑ Eichenauer-Herrmann, 1993 .
↑ Hellekalek, 1995 , p. 261: "Az inverzív módszerek kiváló elméleti és empirikus tulajdonságai a paraméterek változása mellett stabilak maradnak, feltéve, hogy maximális periódushosszunk van."
↑ Bubicz, Stoklosa, 2006 , p. 2: "Az összetett megközelítés az előállított sorozatok ugyanazokat a kiemelkedő tulajdonságait adja, mint az egyedi inverzív generátorok".
↑ Bubicz, Stoklosa, 2006 , p. 2: "Összetett inverzív generátorok lehetővé teszik az egyetlen ICG-nél lényegesen hosszabb periódushossz elérését".
↑ Bubicz, Stoklosa, 2006 , p. 2: "Úgy tűnik, többprocesszoros párhuzamos hardverplatformokra tervezték."
↑ Bubicz, Stoklosa, 2006 , p. 2: „Létezik egy állandó és egyszerű módja a paraméterválasztásnak, amely a Chou algoritmuson alapul. Garantálja a maximális hosszúságot."
↑ Anne Gille-Genest: Pseudo-Random Numbers Generators, 2012 , p. 12: "Mindkét inverz generátor fő hátránya, hogy egy véletlen szám kiszámítása O(log m ) szorzást igényel F m -ben , így az algoritmus nem gyors."

Irodalom

Könyvek

Knut D. E. A programozás művészete : 2. kötet. Megszerzett algoritmusok - 3 - M .: Williams , 2013. - 828 p. — ISBN 978-5-8459-0081-4

Cikkek

Eichenauer J. , Lehn J. Nemlineáris kongruenciális pszeudo véletlenszám-generátor (angol) // 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. 2ᵅ modulusú nemlineáris generátor rácsszerkezetéről (angol) // J. Comput. Appl. Math. - Elsevier BV , 1990. - 1. évf. 31, Iss. 1. - P. 81-85. — ISSN 0377-0427 ; 1879-1778 - doi:10.1016/0377-0427(90)90338-Z
Eichenauer-Herrmann J. Az inverzív kongruenciális pszeudovéletlen számok elkerülik a síkokat // Math . Összeg. - AMS , 1991. - Vol. 56, Iss. 193. - P. 297-301. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2008543
Eichenauer-Herrmann J. , Niederreiter H. Alsó korlátok inverzív kongruenciális pszeudovéletlenségi számok eltérésére két modulusos hatvány esetén // Math . Összeg. - AMS , 1992. - 1. évf. 58, Iss. 198. - 775-779. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2153216
Eichenauer-Herrmann J. Az inverzív kongruenciális pszeudovéletlenszámok új osztályának statisztikai függetlensége // Math . Összeg. - AMS , 1993. - Vol. 60. - P. 375-384. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1993-1159168-9
Chou W. S. Inverzív maximális periódusú polinomokról véges mezők felett (angol) // Appl. Algebr. Eng. Comm. - Springer Science + Business Media , 1995. - Vol. 6, Iss. 4. - P. 245-250. — ISSN 0938-1279 ; 1432-0622 - doi:10.1007/BF01235718
Hellekalek P. Inverzív álvéletlenszám-generátorok: fogalmak, eredmények és linkek (angol) // 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 (angol) // 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. Álvéletlen számgenerátorok . — 2012. (elérhetetlen link)
Glen Amy. Az álvéletlenszámsorozatok periódushosszáról // The University of Adelaide: Honors in Pure Mathematics. – 2002.