Pokroky matematiky, fyziky a astronomie

Pokroky matematiky, fyziky a astronomie

Ľubomíra Balková; Jiří Hladký Generátory pseudonáhodných čísel založené na nekonečných slovech Pokroky matematiky, fyziky a astronomie, Vol. 59 (2014), No. 3, 211–222

Persistent URL: http://dml.cz/dmlcz/144026

Terms of use: © Jednota českých matematiků a fyziků, 2014 Institute of Mathematics of the Czech Academy of Sciences provides access to digitized documents strictly for personal use. Each copy of any part of this document must contain these Terms of use. This document has been digitized, optimized for electronic delivery and stamped with digital signature within the project DML-CZ: The Czech Digital Mathematics Library http://dml.cz

Generátory pseudonáhodných ˇc´ısel zaloˇzené na nekoneˇcných slovech L’ubom´ıra Balkov´ a, Jiˇr´ı Hladký, Praha

V ˇcl´ anku uk´ aˇzeme, jak lze vyuˇz´ıt nekoneˇcn´ ych aperiodick´ ych slov ke konstrukci gener´ ator˚ u n´ ahodn´ ych ˇc´ısel. Zavedeme tˇr´ıdu slov s dobˇ re rozm´ıstˇ en´ ymi v´ yskyty, pro niˇz jsme dok´ azali, ˇze pˇri kombinaci periodick´ ych generátor˚ u podle slov z této tˇr´ıdy vznikaj´ı gener´ atory aperiodické, jeˇz nav´ıc nemaj´ı mˇr´ıˇzkovou strukturu. Slova s dobˇre rozm´ıstˇen´ ymi v´ yskyty zahrnuj´ı napˇr. slova sturmovská a Arnouxova–Rauzyova slova, z nichˇz nˇekter´ a se daj´ı generovat rychl´ ym algoritmem, protoˇze jsou pevn´ ymi body morfism˚ u. Pr´ avˇe gener´ atory pseudon´ ahodn´ ych ˇc´ısel zaloˇzené na pevn´ ych bodech morfism˚ u, které maj´ı dobˇre rozm´ıstˇené v´ yskyty, jsme také otestovali bateriemi statistick´ ych test˚ u TestU01 a PractRand. Uk´ azalo se, ˇze nov´ a metoda podstatnˇe zlepˇsuje statistické vlastnosti generovan´ ych náhodn´ ych ˇc´ısel za cenu pouze zanedbatelnˇe zv´ yˇsené v´ ypoˇcetn´ı a pamˇet’ové n´ aroˇcnosti. ´ Uvod Kombinatorika na slovech je cca 100 let star´ a discipl´ına, za jej´ıhoˇz zakladatele se ˇcasto pokl´ ad´ a Axel Thue. Ten pˇri studiu jist´ ych kombinatorick´ ych vlastnost´ı nekoneˇcn´ ych slov [1] vysvˇetlil, ˇze nemˇel na mysli ˇz´ adnou konkrétn´ı aplikaci, n´ ybrˇz studoval tyto ot´ azky, protoˇze se mu zd´ aly samy o sobˇe dostateˇcnˇe zaj´ımavé. T´ımto tvrzen´ım dnes r´ adi h´ aj´ı svou pr´ aci teoretiˇct´ı kombinatorici na nekoneˇcn´ ych slovech“. V tomto ˇclánku ” ovˇsem uk´ aˇzeme, ˇze se znalosti kombinatoriky na slovech daj´ı aplikovat i v tak praktické oblasti, jakou je generov´ an´ı n´ ahodn´ ych ˇc´ısel. Gener´ atory pseudon´ ahodn´ ych ˇc´ısel se snaˇz´ı produkovat náhodná ˇc´ısla pouˇzit´ım deterministického procesu. Je jasné, ˇze takové generátory maj´ı mnoho vad na kráse. Nejˇcastˇejˇs´ı a nejlépe prostudované gener´ atory – lineárn´ı kongruenˇcn´ı generátory – jsou periodické a jejich zn´ am´ ym defektem je tzv. mˇr´ıˇzková struktura. V ˇclánku [8] je dok´ az´ ano, ˇze kdyˇz se dva line´ arn´ı kongruenˇcn´ı generátory (ale i jakékoliv jiné periodické gener´ atory) zkombinuj´ı podle nekoneˇcn´ ych slov kóduj´ıc´ıch jistou tˇr´ıdu kvazikrystal˚ u nebo ekvivalentnˇe cut-and-project mnoˇzin, v´ ysledná posloupnost je aperiodická a nem´ a mˇr´ıˇzkovou strukturu. Dalˇs´ı v´ ysledky spjaté s kvazikrystaly jsou k nalezen´ı také v ˇcl´ anc´ıch [6], [7]. Naˇs´ım pˇr´ınosem je nalezen´ı kombinatorické podm´ınky – dobˇ re rozm´ıstˇ en´ e v´ yskyty (DRV) – zaruˇcuj´ıc´ı aperiodicitu a absenci mˇr´ıˇzkové struktury [3], [2]. Ukázali jsme, ˇze vlastnost DRV splˇ nuj´ı ˇsiroké tˇr´ıdy nekoneˇcn´ ych slov: sturmovská slova, Arnouxova–Rauzyova slova a dalˇs´ı, z nichˇz mnohé um´ıme generovat rychl´ ym zp˚ usobem,

ˇ ´ , Ph.D., Katedra matematiky, FJFI CVUT Ing. L’ubom´ıra Balkova v Praze, Trojanova 13, 120 00 Praha 2, e-mail: [email protected], [email protected]

Pokroky matematiky, fyziky a astronomie, roˇcn´ık 59 (2014), ˇc. 3

211

protoˇze jsou pevn´ ymi body morfism˚ u. T´ım jsme v´ ysledky z [8] zobecnili pro ˇsirˇs´ı tˇr´ıdy bin´ arn´ıch slov, ale dokonce i pro slova nad v´ıcep´ısmennou abecedou, podle kter´ ych se kombinuje v´ıce line´ arn´ıch kongruenˇcn´ıch generátor˚ u (nebo i jin´ ych periodick´ ych gener´ ator˚ u). Poté jsme se vˇenovali testov´ an´ı kvality gener´ ator˚ u zaloˇzen´ ych na slovech z takov´ ych tˇr´ıd, konkrétnˇe na Fibonacciovˇe a Tribonacciovˇe slovˇe, pˇriˇcemˇz jsme pouˇz´ıvali bal´ıˇcky statistick´ ych test˚ u TestU01 [5] a PractRand [4]. T´ım jsme potvrdili, ˇze kdyˇz se kombinuj´ı line´ arn´ı kongruenˇcn´ı gener´ atory pomoc´ı nekoneˇcn´ ych slov s dobˇre rozm´ıstˇen´ ymi v´ yskyty, vznik´ a aperiodick´ a pseudon´ ahodn´ a posloupnost, která nejen ˇze nemá mˇr´ıˇzkovou strukturu, ale i ˇrada jej´ıch dalˇs´ıch vlastnost´ı se v´ıce podobá náhodné posloupnosti. V ˇcl´ anku nejprve uvedeme motivaci z oblasti generován´ı náhodn´ ych ˇc´ısel. Ve druhé kapitole poté pˇripomeneme pojmy z kombinatoriky na slovech, které se jiˇz v PMFA zˇca´sti objevily [1]. Ve tˇret´ı kapitole zavedeme generátory zaloˇzené na nekoneˇcn´ ych slovech. Ve ˇctvrté kapitole potom prostudujeme kombinatorickou vlastnost dobˇre rozm´ıstˇen´ ych v´ yskyt˚ u. Pát´ a kapitola shrne v´ ysledky empirického testován´ı a na závˇer zformulujeme otevˇrené problémy a smˇery dalˇs´ıho moˇzného v´ yzkumu. 1. Mˇ r´ıˇ zkov´ a struktura gener´ ator˚ u pseudon´ ahodn´ ych ˇ c´ısel Pod pojmem pseudon´ ahodn´ a posloupnost nebo generátor pseudonáhodn´ ych ˇc´ısel (PRNG – z anglického pseudorandom number generator) rozum´ıme v dalˇs´ım textu jakoukoliv posloupnost ˇc´ısel z N = {0, 1, 2, . . .}. Stále obl´ıbené generátory – lineárn´ı kongruenˇcn´ı gener´ atory – jsou z´ aˇrn´ ym pˇr´ıkladem generátor˚ u, které maj´ı slabinu zvanou mˇr´ıˇzkov´ a struktura (a to dokonce jiˇz od dimenze rovné dvˇema [10]). Necht’ Z = (Zn )n∈N ˇ ıkáme, ˇze Z má mˇr´ıˇzkovou je PRNG, jehoˇz v´ ystupem je koneˇcn´ a mnoˇzina M ⊂ N. R´ strukturu, pokud existuje kladné t ∈ N takové, ˇze mnoˇzina {(Zi , Zi+1 , . . . , Zi+t−1 ) i ∈ N} je pokryta soustavou rovnobˇeˇzn´ ych stejnˇe vzd´ alen´ ych nadrovin v eukleidovském prostoru Rt a z´ aroveˇ n tyto nadroviny nepokr´ yvaj´ı vˇsechny body mˇr´ıˇzky M t = {(A1 , A2 , . . . , At ) Ai ∈ M pro kaˇzdé i ∈ {1, . . . , t}}.

Pˇripomeˇ nme, ˇze line´ arn´ı kongruenˇcn´ı gener´ ator, zkrácenˇe LCG, (Zn )n∈N je dán parametry a, m, c ∈ N a definov´ an rekurentn´ım vztahem Zn+1 = aZn + c mod m. Pˇr´ıkladem LCG s v´ yraznou mˇr´ıˇzkovou strukturou je generátor RANDU, kter´ y se hojnˇe pouˇz´ıval v ˇsedes´ at´ ych letech 20. stolet´ ı. Pro t = 3 jsou po sobˇe jdouc´ı trojice ˇc´ısel z gener´ atoru, tj. {(Zi , Zi+1 , Zi+2 ) i ∈ N}, pokryty pouh´ ymi 15 rovnobˇeˇzn´ ymi stejnˇe vzd´ alen´ ymi rovinami, které ani zdaleka nepokr´ yvaj´ı celou mˇr´ıˇzku {1, 2, . . . , m − 1}3 , viz obr. 1. Z ˇcl´ anku [8] lze vyˇc´ıst postaˇcuj´ıc´ı podm´ınku na absenci mˇr´ıˇzkové struktury, i kdyˇz pˇr´ımo v nˇem je formulov´ ana v ménˇe obecné formˇe (Lemma 2.3). Vˇ eta 1. Necht’ Z je PRNG, jehoˇz v´ ystupem je koneˇcná mnoˇzina M ⊂ N obsahuj´ıc´ı alespoˇ n dva prvky. Pˇredpokl´ adejme, ˇze pro kaˇzdé A, B ∈ M a pro kaˇzdé ` ∈ N existuje `-tice (A1 , A2 , . . . , A` ) takov´ a, ˇze jak (A1 , A2 , . . . , A` , A), tak i (A1 , A2 , . . . , A` , B) jsou (` + 1)-tice z gener´ atoru Z. Potom Z nem´ a mˇr´ıˇzkovou strukturu. 212


Obr. 1. Trojice gener´ atoru RANDU, LCG s parametry a = (216 + 3), m = 231 , c = 0, jsou pokryty pouh´ ymi 15 rovnobˇeˇzn´ ymi stejnˇe vzd´ alen´ ymi rovinami.

Pozn´ amka 1. V ˇreˇci kombinatoriky na slovech, viz kapitola 2, lze znˇen´ı pˇredchoz´ı vˇety formulovat n´ asledovnˇe: Necht’ Z je PRNG, jehoˇz v´ ystupem je koneˇcná mnoˇzina M ⊂ N obsahuj´ıc´ı alespoˇ n dva prvky. Pokud Z obsahuje pro kaˇzdá dvˇe p´ısmena A, B ∈ M a pro kaˇzdou délku ` ∈ N prav´ y speci´ aln´ı faktor ` s prav´ ymi extenzemi A a B, potom Z nem´ a mˇr´ıˇzkovou strukturu. 2. Slovn´ık kombinatoriky na slovech Abychom mohli zformulovat kombinatorickou podm´ınku na absenci mˇr´ıˇzkové struktury a také pˇribl´ıˇzit tˇr´ıdy slov, které onu vlastnost dobˇre rozm´ıstˇen´ ych v´ yskyt˚ u maj´ı, potˇrebujeme nejprve zavést nˇekolik pojm˚ u z kombinatoriky na slovech. Abecedou A rozum´ıme koneˇcnou mnoˇzinu symbol˚ u, ˇr´ık´ ame jim p´ısmena. Slovem w naz´ yváme koneˇcnou posloupnost p´ısmen. Jeho délkou rozum´ıme poˇcet p´ısmen, která obsahuje, a znaˇc´ıme ji |w|. Symbolem A∗ znaˇc´ıme mnoˇzinu vˇsech koneˇcn´ ych slov nad abecedou A s pˇrid´ an´ım prázdného slova ε (jde o neutráln´ı prvek v˚ uˇci operaci ˇretˇezen´ı a jeho délku klademe rovnu nule). Mnoˇzina A∗ vybavená operac´ı ˇretˇezen´ı tvoˇr´ı monoid. Pod nekoneˇcným slovem u nad abecedou A pak rozum´ıme nekoneˇcnou posloupnost p´ısmen z A, v n´ıˇz se kaˇzdé p´ısmeno z A skuteˇcnˇe vyskytuje, tj. u = u0 u1 u2 . . . , kde ui ∈ A. Koneˇcné slovo w nazveme faktorem (podslovem) koneˇcného ˇci nekoneˇcného slova u, pokud existuje slovo v a slovo x (koneˇcné ˇci nekoneˇcné) tak, ˇze u = vwx. Je-li v pr´ azdné slovo, nazveme w prefixem slova u. Podobnˇe pokud je x = ε, ˇr´ıkáme, ˇze w je sufix slova u. Pro kaˇzd´ y faktor w nekoneˇcného slova u naz´ yv´ ame výskytem w v u kaˇzd´ y index i, pro kter´ y plat´ı, ˇze slovo w je prefixem nekoneˇcného slova ui ui+1 ui+2 . . . Nekoneˇcné slovo je rekurentn´ı, kdyˇz se v nˇem kaˇzd´ y jeho faktor vyskytuje nekoneˇcnˇekrát. Symbolem |w|a znaˇc´ıme poˇcet v´ yskyt˚ u p´ısmene a ve slovˇe w. Pokroky matematiky, fyziky a astronomie, roˇcn´ık 59 (2014), ˇc. 3

213

ˇ Casto pracujeme s morfismem ϕ: A∗ → A∗ , tedy zobrazen´ım, které splˇ nuje pro kaˇzd´ a dvˇe koneˇcn´ a slova v, w ∈ A∗ : ϕ(vw) = ϕ(v)ϕ(w). Morfismus je samozˇrejmˇe jednoznaˇcnˇe d´ an, pokud známe obrazy p´ısmen abecedy A. Jeho p˚ usoben´ı lze pˇrirozenou cestou rozˇs´ıˇrit i na nekoneˇcná slova: ϕ(u0 u1 u2 . . .) := ϕ(u0 )ϕ(u1 )ϕ(u2 ) . . . Pokud nekoneˇcné slovo u splˇ nuje ϕ(u) = u, nazveme je pevným bodem morfismu ϕ. Jazykem L(u) nekoneˇcného slova u naz´ yv´ ame mnoˇzinu vˇsech faktor˚ u tohoto slova. ˇ ık´ R´ ame, ˇze jazyk je uzavˇrený vzhledem k reverzi (angl. closed under reversal), kdyˇz s kaˇzd´ ym slovem obsahuje i jeho reverzi, tj. slovo vzniklé ˇcten´ım pozpátku. Necht’ n je pˇrirozené ˇc´ıslo, symbolem Ln (u) znaˇc´ıme mnoˇzinu vˇsech faktor˚ u délky n slova u. Nekoneˇcné slovo u naz´ yv´ ame posléze periodické (angl. eventually periodic), pokud je tvaru u = wv ω , kde w, v ∈ A∗ a ω znaˇc´ı nekoneˇcné opakován´ı. V opaˇcném pˇr´ıpadˇe naz´ yv´ ame slovo u aperiodické. (Faktorovou) komplexitou slova u je zobrazen´ı C : N → N definované vztahem C(n) := poˇcet r˚ uzn´ ych faktor˚ u délky n obsaˇzen´ ych ve slovˇe u. Je zn´ amo, ˇze komplexita posléze periodick´ ych slov je omezená, zat´ımco komplexita aperiodick´ ych slov splˇ nuje C(n) ≥ n + 1 pro vˇsechna n ∈ N, viz [11]. Pravou extenz´ı faktoru w slova u nazveme libovolné p´ısmeno a ∈ A takové, ˇze wa je faktor slova u. Zˇrejmˇe kaˇzd´ y faktor m´ a alespoˇ n jednu pravou extenzi. Takové faktory, které maj´ı alespoˇ n dvˇe pravé extenze, se naz´ yvaj´ı pravé speci´ aly. Podobnˇe lze definovat levou extenzi a levé speci´ aly. Pˇ r´ıklad 1. Ilustrujme uvedené pojmy na nekoneˇcném slovˇe u = (abb)ω . Abeceda je A = {a, b}. Slovo babb je faktorem délky 4 slova u. Jeho jedinou pravou extenz´ı je p´ısmeno a a jeho jedinou levou extenz´ı je p´ısmeno b. Slovo abbabba je prefixem délky 7 slova u. Snadno nahlédneme, ˇze mnoˇzina vˇsech faktor˚ u délky 5 slova u je L5 (u) = {abbab, bbabb, babba}. D´ ale si také m˚ uˇzeme rozmyslet, ˇze vˇsechna slova délky alespoˇ n dva maj´ı vˇzdy jedinou pravou (a také jedinou levou) extenzi, coˇz vlastnˇe znamen´ a, ˇze z kaˇzdého faktoru délky alespoˇ n dva se zrod´ı jedin´ y faktor délky o jednu vˇetˇs´ı. Proto komplexita bude C(n) = 3 pro kaˇzdé n ≥ 2. (To odpov´ıdá tvrzen´ı, ˇze komplexita periodick´ ych slov je omezen´ a.) Definujeme-li morfismus ϕ(a) := abb a ϕ(b) := abb, pak je zˇrejmˇe u pevn´ ym bodem ϕ. 3. Kombinov´ an´ı gener´ ator˚ u pseudon´ ahodn´ ych ˇ c´ısel Chceme-li eliminovat mˇr´ıˇzkovou strukturu, pom´ ah´ a kombinovat generátory ˇsikovn´ ym zp˚ usobem. Jednu z moˇzn´ ych metod pˇredstavili L.-S. Guimond, Jan Patera a Jiˇr´ı Patera v ˇcl´ anku [7]. Necht’ X = (Xn )n∈N a Y = (Yn )n∈N jsou dva ne nutnˇe r˚ uzné PRNG se stejn´ ym v´ ystupem M ⊂ N a stejnou periodou m ∈ N. Dále necht’ u = u0 u1 u2 . . . je nekoneˇcné bin´ arn´ı slovo nad abecedou {a, b}. Potom gener´ ator Z = (Zn )n∈N

(1)

zaloˇzený na slovˇe u z´ısk´ ame n´ asleduj´ıc´ım algoritmem: 214


ˇ krok za krokem p´ısmena u. 1. Cti ˇ s-li a po i-té, zkop´ıruj i-t´ 2. Cteˇ y symbol z X na konec konstruované posloupnosti Z. ˇ s-li b po i-té, zkop´ıruj i-t´ 3. Cteˇ y symbol z Y na konec konstruované posloupnosti Z. Snadno lze konstrukci zobecnit pro nekoneˇcn´ a slova nad v´ıcep´ısmennou abecedou a kombinovat v´ıce PRNG. Pˇ r´ıklad 2. Necht’ X = (X1 X2 X3 X4 )ω , Y = (Y1 Y2 Y3 Y4 )ω a u = (abb)ω . Potom Z = X1 Y1 Y2 X2 Y3 Y4 X3 Y1 Y2 X4 Y3 Y4 X4 Y1 Y2 . . . 4. Slova s dobˇ re rozm´ıstˇ en´ ymi v´ yskyty V ˇcl´ anku [8] je dok´ az´ ano, ˇze PRNG zaloˇzen´ y na nekoneˇcn´ ych slovech kóduj´ıc´ıch jistou tˇr´ıdu cut-and-project mnoˇzin je aperiodick´ y a nemá mˇr´ıˇzkovou strukturu. Nám se podaˇrilo v´ ysledek zobecnit a naj´ıt ˇsirˇs´ı tˇr´ıdu slov, která zaruˇcuj´ı aperiodicitu a absenci mˇr´ıˇzkové struktury pro gener´ atory zaloˇzené na takov´ ych slovech [2], [3]. ˇ ıkáme, ˇze aperiodické binárn´ı slovo u Definice 1. (Vlastnost DRV pro bin´ arn´ı slova.) R´ nad abecedou {a, b} m´ a dobˇre rozm´ıstˇené výskyty1 (nebo má vlastnost DRV), pokud u splˇ nuje pro kaˇzdé m ∈ N a pro kaˇzd´ y faktor w slova u následuj´ıc´ı podm´ınku. Oznaˇc´ıme-li i0 , i1 , i2 , . . . v´ yskyty slova w ve slovˇe u, potom |u0 u1 . . . uij −1 |a , |u0 u1 . . . uij −1 |b mod m | j ∈ N = Z2m , kde mod m je aplikováno po sloˇzk´ ach, |w|a znaˇc´ı poˇcet v´ yskyt˚ u p´ısmene a ve slovˇe w a Zm = {0, 1, . . . , m − 1}.

Vlastnost DRV definujeme pro aperiodick´ a slova, protoˇze je zˇrejmé, ˇze nikdy neplat´ı pro slova posléze periodick´ a. Pro slova s vlastnost´ı DRV jsme dokázali následuj´ıc´ı vˇetu.

Vˇ eta 2. Necht’ Z je PRNG z (1) zaloˇzen´ y na bin´ arn´ım nekoneˇcném slovˇe u s vlastnost´ı DRV. Potom je Z aperiodick´ y a nem´ a mˇr´ıˇzkovou strukturu. Pozn´ amka 2. Pokud bychom mˇeli zadané konkrétn´ı dva generátory s periodou m a pr´ avˇe pro nˇe chtˇeli garantovat absenci mˇr´ıˇzkové struktury, staˇcilo by zkontrolovat, ˇze plat´ı vlastnost DRV pouze pro modul rovn´ y m. Pˇ r´ıklad 3. Abychom vidˇeli, ˇze existuj´ı aperiodick´ a slova, která vlastnost DRV nemaj´ı, prozkoumejme Thueovo–Morseovo slovo t = abbabaabbaababbabaababbaabbabaab . . . , které je pevn´ ym bodem morfismu ϕ(a) = ab, ϕ(b) = ba. Vskutku, uvaˇzujeme-li m = 2 a w = aa, potom z tvaru morfismu plyne, ˇze se w vyskytuje pouze na lich´ ych pozic´ıch ij . Napˇr´ıklad i0 = 5, i1 = 9, i2 = 17, 1 Angl.

t0 . . . t4 = abbab, (|t0 . . . t4 |a , |t0 . . . t4 |b ) = (2, 3), t0 . . . t8 = abbabaabb, (|t0 . . . t8 |a , |t0 . . . t8 |b ) = (4, 5), t0 . . . t16 = abbabaabbaababbab, (|t0 . . . t16 |a , |t0 . . . t16 |b ) = (8, 9).

words with well-distributed occurrences


215

Proto je (|t0 t1 . . . tij −1 |a + |t0 t1 . . . tij −1 |b ) = ij liché ˇc´ıslo. Tud´ıˇz napˇr´ıklad (|t0 t1 . . . tij −1 |a , |t0 t1 . . . tij −1 |b ) mod 2 6= (0, 0). Definovali jsme kombinatorickou podm´ınku – dobˇre rozm´ıstˇené v´ yskyty – zaruˇcuj´ıc´ı absenci mˇr´ıˇzkové struktury. Nyn´ı je d˚ uleˇzité naj´ıt slova, která takovou vlastnost maj´ı. V ˇcl´ anc´ıch [2], [3] jsme dok´ azali, ˇze sturmovsk´ a slova, coˇz jsou slova s minimáln´ı komplexitou mezi slovy aperiodick´ ymi, tj. s komplexitou splˇ nuj´ıc´ı C(n) = n + 1, vlastnost DRV maj´ı. Uved’me alespoˇ n nejzn´ amˇejˇs´ıho z´ astupce této tˇr´ıdy – slavné Fibonacciovo slovo: f je pevn´ ym bodem morfismu ϕ(a) = ab, ϕ(b) = a, tj. f = abaababaabaab . . . Kromˇe zobecnˇen´ı v´ ysledku z ˇcl´ anku [8] pro slova nad binárn´ı abecedou se nám podaˇrilo také naj´ıt kombinatorickou podm´ınku pro slova nad v´ıcep´ısmennou abecedou; gener´ atory na nich zaloˇzené pak kombinuj´ı v´ıce vstupn´ıch generátor˚ u a opˇet nemaj´ı mˇr´ıˇzkovou strukturu. Uk´ azalo se, ˇze staˇc´ı nejpˇrirozenˇejˇs´ım moˇzn´ ym zp˚ usobem zobecnit definici bin´ arn´ıho slova s dobˇre rozm´ıstˇen´ ymi v´ yskyty. ˇ ıkáme, ˇze aperiodické slovo u Definice 2. (Vlastnost DRV pro v´ıcep´ısmenn´ a slova.) R´ nad abecedou {a1 , a2 , . . . , ad } m´ a dobˇre rozm´ıstˇené výskyty (nebo má vlastnost DRV), pokud u splˇ nuje pro kaˇzdé m ∈ N a pro kaˇzd´ y faktor w slova u následuj´ıc´ı podm´ınku. Oznaˇc´ıme-li i0 , i1 , i2 , . . . v´ yskyty slova w ve slovˇe u, potom |u0 u1 . . . uij −1 |a1 , |u0 u1 . . . uij −1 |a2 , . . . , |u0 u1 . . . uij −1 |ad , mod m | j ∈ N = Zdm , kde mod m je aplikováno po sloˇzk´ ach.

Pozn´ amka 3. Vlastnost DRV je postaˇcuj´ıc´ı, nikoliv nutná podm´ınka pro absenci mˇr´ıˇzkové struktury. Nen´ı tˇeˇzké uk´ azat, ˇze modifikované Fibonacciovo slovo, které vzniklo z Fibonacciova slova tak, ˇze jsme za kaˇzdé p´ısmeno napsali c, tj. u = acbcacacbcacbcac . . . , nem´ a vlastnost DRV, ale mˇr´ıˇzkovou strukturu také nemá. Jak se ale ukazuje ve statistick´ ych testech, vlastnost DRV je d˚ uleˇzit´ a nejen pro absenci mˇr´ıˇzkové struktury, ale zˇrejmˇe zaruˇcuje i dalˇs´ı dobré vlastnosti gener´ ator˚ u. Pˇ r´ıklad 4. Uved’me nejprve trivi´ aln´ı pˇr´ıklad slova s dobˇre rozm´ıstˇen´ ymi v´ yskyty. ˇ ık´ R´ ame, ˇze nekoneˇcné slovo nad abecedou A je univerz´ aln´ı, jestliˇze obsahuje vˇsechna koneˇcn´ a slova nad A jako své faktory. Univerz´ aln´ı slovo nad {0, 1, . . . , d − 1} lze z´ıskat napˇr´ıklad ˇretˇezen´ım zápis˚ u po sobˇe jdouc´ıch pˇrirozen´ ych ˇc´ısel v bázi d. Je snadné si rozmyslet, ˇze univerz´ aln´ı slova maj´ı vlastnost DRV. Stejnˇe jako nad bin´ arn´ı abecedou i nad v´ıcep´ısmennou abecedou je potˇreba ukázat, ˇze existuje ˇsirok´ a tˇr´ıda slov, kter´ a maj´ı vlastnost DRV. V hledán´ı takového pˇr´ıkladu jsme uspˇeli, protoˇze jsme zjistili, ˇze Arnouxova–Rauzyova slova vlastnost DRV maj´ı. Jde o slova, kter´ a maj´ı jazyk uzavˇren´ y vzhledem k reverzi a pro kaˇzdou délku n obsahuj´ı pr´ avˇe jeden prav´ y speci´ aln´ı faktor délky n, a tento prav´ y speciál má nav´ıc jako pravé extenze vˇsechna p´ısmena abecedy. Vˇsimnˇeme si, ˇze jde o pˇr´ımé zobecnˇen´ı sturmovsk´ ych 216


slov na v´ıcep´ısmenné abecedy, protoˇze sturmovsk´ a slova jsou pˇresnˇe takov´ ymi vlastnostmi charakterizov´ ana nad bin´ arn´ı abecedou. Asi nejznámˇejˇs´ım tˇr´ıp´ısmenn´ ym pˇr´ıkladem je Tribonacciovo slovo u, které je pevn´ ym bodem morfismu ϕ(a) = ab, ϕ(b) = ac, ϕ(c) = a, tj. u = abacabaabacab . . . Pozn´ amka 4. Existuje jednoduch´ a metoda, jak vyrábˇet ze slov s vlastnost´ı DRV opˇet slova s DRV vlastnost´ı nad abecedou s menˇs´ım poˇctem p´ısmen. Je-li abeceda rovna {a1 , a2 , . . . , ad }, kde d ≥ 3, a slovo u m´ a vlastnost DRV, potom pokud ve slovˇe u pˇrep´ıˇseme p´ısmeno ad na jiné ale pevnˇe dané p´ısmeno ai , bude m´ıt v´ ysledné slovo opˇet vlastnost DRV. Takov´ ym zp˚ usobem z´ısk´ ame slova odliˇsná od sturmovsk´ ych a Arnouxov´ ych–Rauzyov´ ych. Pozn´ amka 5. Dalˇs´ı transformac´ı slov, kter´ a zachovává vlastnost DRV a tentokrát zachov´ av´ a i abecedu, je vyuˇzit´ı morfismu, jehoˇz matice má determinant roven ±1 neboli je unimodul´ arn´ı. Matic´ı morfismu ϕ nad abecedou {a1 , a2 , . . . , ad } rozum´ıme matici Φ, jej´ıˇz ij-t´ y prvek je definov´ an jako Φij = |ϕ(ai )|aj . Pˇ r´ıklad 5. Uvaˇzujme morfismus ϕ : a → aab, b → ab. Pak jeho matice má tvar Φ = ( 21 11 ). Aplikujeme-li tento morfismus na Fibonacciovo slovo f = abaababaabaab . . ., pak dostaneme slovo ϕ(f ) = aababaabaababaababaabaababaabaabab . . ., které má také dobˇre rozm´ıstˇené v´ yskyty. 5. Statistick´ e testy gener´ ator˚ u pseudon´ ahodn´ ych ˇ c´ısel V pˇredchoz´ı ˇc´ asti jsme vysvˇetlili, ˇze PRNG zaloˇzené na slovech s DRV vlastnost´ı nemaj´ı mˇr´ıˇzkovou strukturu. V této kapitole uk´ aˇzeme, ˇze také v empirick´ ych statistick´ ych testech dopadnou velmi dobˇre, za pˇredpokladu, ˇze jsou kombinovány dostateˇcnˇe kvalitn´ı LCG. Pro testov´ an´ı jsou potˇreba dlouhé prefixy nekoneˇcn´ ych slov, podle kter´ ych kombinujeme LCG. Naˇstˇest´ı existuje cel´ a ˇrada sturmovsk´ ych a Arnouxov´ ych–Rauzyov´ ych slov, kter´ a jsou pevn´ ymi body morfism˚ u, a takové pevné body um´ıme efektivnˇe generovat [12]: prefix délky n z´ısk´ ame v ˇcase O(n) a pamˇet’ové nároky jsou O(log n). Chceme-li generov´ an´ı zrychlit, je v´ yhodnˇejˇs´ı si m´ısto obraz˚ u p´ısmen ϕ(a) pamatovat ϕk (a) pro kaˇzdé a ∈ A. Pr´ avˇe takového vylepˇsen´ı jsme vyuˇzili, ˇc´ımˇz se rychlost generov´ an´ı prefix˚ u stala vyˇsˇs´ı neˇz rychlost generován´ı v´ ystupu kombinovan´ ych LCG. Napˇr´ıklad pro z´ısk´ an´ı 1010 32bitov´ ych hodnot v´ ystupu LCG s modulem 264 jsme potˇrebovali 14.3 sekund, zat´ımco se stejn´ ym hardwarem jsme vygenerovali za p˚ ul sekundy 1010 p´ısmen pevného bodu morfismu. Seˇcteno a podtrˇzeno, pouˇzit´ı PRNG zaloˇzen´ ych na pevn´ ych bodech morfism˚ u znamená oproti pouˇzit´ı p˚ uvodn´ıch LCG pouze zanedbatelnou ˇcasovou penalizaci. D´ ale uk´ aˇzeme v´ ysledky testov´ an´ı PRNG zaloˇzen´ ych: • na Fibonacciovˇe slovˇe (jako pˇr´ıklad slova sturmovského): jde o pevn´ y bod morfismu a 7→ ab, b 7→ a, • na modifikovaném Fibonacciovˇe slovˇe – Fibonacci2 – s p´ısmenem c vloˇzen´ ym na kaˇzdou druhou pozici (viz pozn´ amka 3), • na Tribonacciovˇe slovˇe (jako ilustraci tern´ arn´ıho Arnouxova–Rauzyova slova): jde o pevn´ y bod morfismu a 7→ ab, b 7→ ac, c 7→ a. Pokroky matematiky, fyziky a astronomie, roˇcn´ık 59 (2014), ˇc. 3

217

slovo uloˇzen´ı ϕ uloˇzen´ı ϕk

Fibonacci Tribonacci 115 s 107 s 0.41 s 0.36 s

Tab. 1. Porovn´ an´ı ˇcasu v sekund´ ach pro generov´ an´ı 1010 p´ısmen Fibonacciova a Tribonacciova slova s vyuˇzit´ım p˚ uvodn´ıho algoritmu [12] a jeho vylepˇsené verze. Poˇcet iterac´ı k v pravidle ϕk je vyb´ır´ an tak, aby délka ϕk (a) nepˇrekroˇcila 4096 bajt˚ u pro ˇza ´dné p´ısmeno z abecedy. Mˇeˇren´ı bylo provedeno na Intel Core i7-3520M CPU s frekvenc´ı 2.90 GHz.

Implementovali jsme PRNG zaloˇzené na pevn´ ych bodech morfism˚ u pro v´ıce sturmovsk´ ych a tern´ arn´ıch Arnouxov´ ych–Rauzyov´ ych slov. Jelikoˇz jsou v´ ysledky podobné, pˇredstav´ıme zde pr´ avˇe jen v´ ysledky pro tˇri v´ yˇse uvedené zástupce. Náˇs program generuj´ıc´ı PRNG zaloˇzené na pevn´ ych bodech morfism˚ u je dostupn´ y online spolu s popisem [9]. Do test˚ u jsme zahrnuli modifikované Fibonacciovo slovo, které nemá vlastnost DRV, ale z´ aroveˇ n produkuje PRNG bez mˇr´ıˇzkové struktury. Ovˇsem je u nˇej vidˇet, ˇze v´ ysledky v testech jsou horˇs´ı neˇz pro Fibonacciovo slovo, a to aˇckoliv je Fibonacciovo slovo bin´ arn´ı a modifikované Fibonacciovo slovo tern´ arn´ı. Pˇri kombinov´ an´ı LCG nepouˇz´ıv´ ame vˇsechny bity v´ ystupu. Námi testované LCG maj´ı periodu m v rozsahu od 247 − 115 do 264 , ale my pouˇz´ıváme pouze 32 horn´ıch bit˚ u jako v´ ystup, protoˇze pr´ avˇe 32bitové posloupnosti jsou potˇreba jako vstup sad statistick´ ych test˚ u.2 Aplikujeme dvˇe sady test˚ u n´ ahodn´ ych ˇc´ısel – TestU01 BigCrush a PractRand. Funguj´ı rozd´ılnˇe. Prvn´ı obsahuje 160 statistick´ ych test˚ u, pˇriˇcemˇz mnoho z nich je ˇsito na m´ıru konkrétn´ım typ˚ um gener´ ator˚ u. Je to test s dobr´ ym renomé, ovˇsem jeho nev´ yhodou je, ˇze pracuje s pevn´ ym poˇctem bit˚ u a nejniˇzˇs´ı jeden aˇz dva bity vˇzdy zahazuje. Druh´ a sada se skl´ ad´ a ze tˇr´ı r˚ uzn´ ych test˚ u, pˇriˇcemˇz jeden se soustˇred’uje na korelace na bl´ızko, druh´ y na korelace na d´ alku a posledn´ı je variac´ı klasického gap testu“ (sledov´ an´ı mezer). Nav´ıc PractRand aplikuje na vstupn´ı data automa” ticky r˚ uzné filtry. Pro naˇse u ´ˇcely je zaj´ımav´ y filtr doln´ıch bit˚ u – pos´ılá na testován´ı r˚ uzn´ y, ale pˇredem dan´ y pevn´ y poˇcet bit˚ u z v´ ystupu generátoru (t´ım se dá kontrolovat, zda byla odstranˇena v´ yˇse zm´ınˇen´ a slabina, kdy doln´ı bity LCG s modulem rovn´ ym mocninˇe dvojky maj´ı menˇs´ı periodu). PractRand um´ı testovat velmi dlouhé posloupnosti, aˇz do nˇekolika exabajt˚ u. Abychom kontrolovali ˇcas, omezili jsme se na vstupu na posloupnosti délky 16 TB. Prvn´ı sloupec tabulky 2 ukazuje testované LCG. Sloupec BigCrush udává, kolik test˚ u sady TestU01 BigCrush neuspˇelo. Sloupec PractRand udává log2 délky vstupn´ıch dat v bajtech, pro kter´ a zaˇcaly b´ yt v´ ysledky PractRand velmi podezˇrelé (p-hodnota menˇs´ı neˇz 10−5 ). Jeden LCG neuk´ azal v PractRand testu ˇzádné slabiny, coˇz jsme oznaˇcili jako > 44. Posledn´ı sloupec ukazuje ˇcas v sekundách pro generován´ı prvn´ıch 1010 32bitov´ ych posloupnost´ı v´ ystupu na Intel i7-3520M CPU s frekvenc´ı 2.90 GHz. Z tabulky 2 vid´ıme, ˇze LCG s m ∈ {247 − 115, 263 − 25} dávaj´ı nejlepˇs´ı statistické v´ ysledky. Z´ aroveˇ n je ale ˇcas generov´ an´ı jejich v´ ystupu 20krát pomalejˇs´ı neˇz 2 Nepouˇ z´ıv´ ame pˇr´ımo LCG s modulem 232 , protoˇ ze u takov´ ych gener´ ator˚ u je zn´ amo, ˇ ze k-t´ y bit LCG s modulem 2` pro nˇ ejak´ e ` ∈ N m´ a periodu d´ elky pouze 2k . Nav´ıc i gener´ atory, kter´ e nemaj´ı modul ve tvaru 2` , ale maj´ı periodu bl´ızkou 232 , z˚ ust´ avaj´ı i po kombinov´ an´ı podle slov s dobˇre rozm´ıstˇ en´ ymi v´ yskyty v testech pˇr´ıliˇs slab´ e.

218


Generátor

Zkratka

LCG(247 − 115, 71971110957370, 0) L47-115 63

LCG(2

59

− 25, 2307085864, 0) 13

LCG(2 , 13 , 0) 63

19

LCG(2 , 5 , 1)

ˇ 1010 BigCrush PractRand Cas 14

40

281 s

L63-25

2

>44

277 s

L59

19

27

14.1 s

L63

19

33

14.4 s

64

L64 28

18

35

14.0 s

64

L64 32

14

34

14.1 s

64

L64 39

13

33

14.0 s

LCG(2 , 2862933555777941757, 1) LCG(2 , 3202034522624059733, 1) LCG(2 , 3935559000370003845, 1)

Tab. 2. Seznam pouˇzit´ ych LCG(m, a, c) a jejich v´ ysledky v testech BigCrush a PractRand

u ostatn´ıch pouˇzit´ ych LCG. To je d´ ano faktem, ˇze operaci modulo mus´ıme opravdu poˇc´ıtat, zat´ımco modulov´ an´ı 2` odpov´ıd´ a posouv´ an´ı binárn´ı teˇcky. V tabulk´ ach 3, 4, 5 uk´ aˇzeme v´ ysledky PRNG zaloˇzen´ ych na Fibonacciovˇe, modifikovaném Fibonacciovˇe slovˇe a Tribonacciovˇe slovˇe pˇri kombinován´ı r˚ uzn´ ych LCG z tabulky 2. (Kombinujeme tak, ˇze ˇcten´ı p´ısmene a ve slovˇe odpov´ıdá pouˇzit´ı v´ ystupu gener´ atoru ve sloupci a a analogicky pro dalˇs´ı p´ısmena b, c a sloupce b, c.) To zahrnuje také pouˇzit´ı r˚ uzn´ ych instanc´ı stejného gener´ atoru. Vˇsechny LCG maj´ı jako násadu ˇc´ıslo 1. PRNG pak byly “zahˇr´ aty” generov´ an´ım 109 hodnot, neˇz byly spuˇstˇeny statistické testy. Protoˇze frekvence p´ısmen jsou sné (napˇr. u Fibonacciova slova je √ odliˇ . pomˇer frekvence a ku b roven τ = 21 (1 + 5) = 1.618), zahˇr´ıvac´ı kolo zp˚ usob´ı, ˇze i dvˇe instance stejného gener´ atoru se budou po chv´ıli hodnˇe liˇsit. Sloupec BigCrush pouˇz´ıv´ a n´ asleduj´ıc´ı znaˇcen´ı: prvn´ı ˇc´ıslo indikuje, kolik test˚ u sady BigCrush neuspˇelo, a druhé ˇc´ıslo v z´ avorce ud´ av´ a, kolik test˚ u mˇelo podezˇrele malou p-hodnotu v rozsahu od 10−6 do 10−4 . Sloupec PractRand ukazuje log2 délky vstupn´ıch dat v bajtech, pro které zaˇcaly b´ yt v´ ysledky PractRand velmi podezˇrelé (p-hodnota menˇs´ı neˇz 10−5 ). . Maxim´ aln´ı objem vstupn´ıch dat byl 16TB = 244 B. Sloupec s ˇcasem udává dobu generov´ an´ı 1010 32bitov´ ych slov na Intel i7-3520M CPU s frekvenc´ı 2.90 GHz. Zdrojov´ y k´ od je dostupn´ y v [9]. Na z´ akladˇe v´ ysledk˚ u statistick´ ych test˚ u jsme uˇcinili následuj´ıc´ı pozorován´ı: 1. Kvalita LCG se podstatnˇe zlepˇsila, kdyˇz jsme je zkombinovali podle slov s dobˇre rozm´ıstˇen´ ymi v´ yskyty. Toto je dobˇre patrné v testu BigCrush. Zat´ımco pro p˚ uvodn´ı LCG neuspˇelo 13 aˇz 19 test˚ u (jedinou v´ yjimkou byl generátor L63-25 s dvˇema ne´ uspˇechy – viz tabulka 2), po zkombinován´ı témˇeˇr vˇsechny BigCrush testy proˇsly. Nejhorˇs´ım v´ ysledkem byl jeden ne´ uspˇeˇsn´ y test pro kombinaci podle Tribonacciova slova, resp. podle Fibonacciova slova pro LCG L47-115. Pravdˇepodobnou pˇr´ıˇcinou je ovˇsem nejkratˇs´ı perioda tohoto generátoru mezi vˇsemi uvaˇzovan´ ymi LCG. V´ ysledky sady PractRand také potvrzuj´ı zlepˇsen´ı. Napˇr´ıklad v pˇr´ıpadˇe LCG s modulem 264 zaˇcal test nach´ azet neregularity v distribuci posledn´ıho bitu ˇ aˇr necht’ tento fakt porovná s velikost´ı dat aˇz pro v´ ystup velikosti 2TB. Cten´ 8 GB aˇz 32 GB, kdy p˚ uvodn´ı LCG vykazovaly slabiny v tomto testu. Sada test˚ u PractRand aplikuje na vstupn´ı data r˚ uzné filtry a vˇsechny chyby se objevily pro filter Low1/32, kde je kontrolov´ ana distribuce pouze posledn´ıho bitu. Bylo by Pokroky matematiky, fyziky a astronomie, roˇcn´ık 59 (2014), ˇc. 3

219

Slovo Fib

Skupina A A A A A B B B C C C C C C

a L64 28 L64 32 L64 39 L64 28 L64 32 L47-115 L63-25 L59 L63-25 L59 L63-25 L64 39 L59 L64 39

ˇ 1010 b BigCrush PractRand Cas L64 28 0 41 30.2 s L64 28 0(1) 41 29.3 s L64 28 0 (2) 41 31 s L64 32 0 41 30.2 s L64 32 0 41 30.1 s L47-115 1(1) >44 302 s L63-25 0(1) >44 299 s L59 0(1) 34 28.7 s L59 0 38 198 s L63-25 0(1) 35 134 s L64 39 0 >44 199 s L63-25 0 41 135 s L64 39 0 35 30.4 s L59 0 37 31.3 s

Tab. 3. Shrnut´ı v´ ysledk˚ u statistick´ ych test˚ u pro gener´ atory zaloˇzené na Fibonacciovˇe slovˇe a r˚ uzn´ ych kombinac´ıch LCG z tabulky 2

2.

3.

4.

5. 6.

7.

220

tedy jistˇe moˇzné zlepˇsit kvalitu gener´ atoru t´ım, ˇze by se ze vstupn´ıch bit˚ u bralo pouze 16 horn´ıch bit˚ u, pˇr´ıpadnˇe kombinov´ an´ım generátor˚ u, které nemaj´ı modul tvaru 2` . Kvalita kombinovan´ ych gener´ ator˚ u silnˇe z´ avis´ı na kvalitˇe kombinovan´ ych gener´ ator˚ u, viz napˇr. nˇekteré gener´ atory skupiny B v tabulkách 3, 4, 5, které mˇely dobré v´ ysledky v testu PractRand jiˇz v p˚ uvodn´ım tvaru. Dalˇs´ım zaj´ımav´ ym pozorov´ an´ım je fakt, ˇze uˇz´ıván´ım LCG se stejn´ ymi parametry a r˚ uznou n´ asadou (inicializaˇcn´ı hodnotou) nic nepokaz´ıme. Jen je tˇreba pohl´ıdat, aby byly poˇc´ ateˇcn´ı stavy dostateˇcnˇe r˚ uzné, viz skupina A a B v tabulkách 3, 4 a 5. Kombinujeme-li LCG r˚ uzné kvality, pak LCG nejniˇzˇs´ı kvality urˇcuje kvalitu v´ ysledného gener´ atoru, viz skupina C v tabulkách 3, 4, 5. Pokud tedy kombinujeme LCG r˚ uzné kvality, je dobré pouˇz´ıt nejlepˇs´ı z nich tak, aby odpov´ıdal nejˇcastˇejˇs´ımu p´ısmenu ve slovˇe s vlastnost´ı DRV. Na druhé stranˇe, kdyˇz kombinujeme gener´ atory stejné kvality, pak na jejich poˇrad´ı nez´ aleˇz´ı, viz skupina A v tabulk´ ach 3, 4, 5. Modifikované Fibonacciovo slovo neprodukuje lepˇs´ı v´ ysledky neˇz Fibonacciovo slovo, aˇckoliv je nad vˇetˇs´ı abecedou. Je to pochopitelné, protoˇze vzniklo pravideln´ ym vkl´ ad´ an´ım nového p´ısmena za kaˇzdé p´ısmeno Fibonacciova slova. Tribonacciovo slovo ukazuje lepˇs´ı v´ ysledky neˇz Fibonacciovo slovo. Takové pozorov´ an´ı bylo platné pro kaˇzdé tern´ arn´ı Arnouxovo–Rauzyovo slovo v porovnán´ı se sturmovsk´ ymi slovy. Pokroky matematiky, fyziky a astronomie, roˇcn´ık 59 (2014), ˇc. 3

Slovo Fib2

Skupina A A A A A B B B B C C C C C C

a L64 28 L64 39 L64 39 L64 28 L64 32 L47-115 L63-25 L59 L63 L63-25 L63-25 L59 L59 L64 39 L64 39

b L64 28 L64 28 L64 32 L64 39 L64 39 L47-115 L63-25 L59 L63 L59 L64 39 L63-25 L64 39 L63-25 L59

ˇ 1010 c BigCrush PractRand Cas L64 28 0 40 28.4 s L64 28 0(2) 40 27.9 s L64 28 0 39 27.5 s L64 28 0 40 27.3 s L64 28 0 40 27.5 s L47-115 0(2) >44 297.0 s L63-25 0(2) >44 293.0 s L59 0(1) 32 27.4 s L63 0 38 27.3 s L64 39 0(1) 39 113.0 s L59 0 32 113.0 s L64 39 0 38 81.1 s L63-25 0 39 158.3 s L59 0 31 81.0 s L63-25 0 42 159.0 s

Tab. 4. Shrnut´ı v´ ysledk˚ u statistick´ ych test˚ u pro gener´ atory zaloˇzené na modifikovaném Fibonacciovˇe slovˇe a r˚ uzn´ ych kombinac´ıch LCG z tabulky 2

Slovo Trib

Skupina A A A A A B B B B C C C C C C

a L64 28 L64 39 L64 39 L64 28 L64 32 L47-115 L63-25 L59 L63 L63-25 L63-25 L59 L59 L64 39 L64 39

b L64 28 L64 28 L64 32 L64 39 L64 39 L47-115 L63-25 L59 L63 L59 L64 39 L63-25 L64 39 L63-25 L59

ˇ 1010 c BigCrush PractRand Cas L64 28 0(2) 42 27.2 L64 28 0 43 27.1 L64 28 0(1) 42 28.0 L64 28 0(1) 42 28.1 L64 28 0 42 27.1 L47-115 1 >44 299.0 L63-25 0(1) >44 298.0 L59 0 35 27.2 L63 0(1) 41 27.2 L64 39 0(1) 39 172.0 L59 0(1) 41 173.0 L64 39 0 35 106.0 L63-25 0 34 70.5 L59 0 41 107.0 L63-25 0(1) 40 74.3

Tab. 5. Shrnut´ı v´ ysledk˚ u statistick´ ych test˚ u pro gener´ atory zaloˇzené na Tribonacciovˇe slovˇe a r˚ uzn´ ych kombinac´ıch LCG z tabulky 2


221

6. Otevˇ ren´ e probl´ emy a dalˇ s´ı v´ yzkum Otevˇren´ ych problém˚ u z˚ ust´ av´ a mnoho. Co se t´ yˇce kombinatorické ˇcásti ˇclánku, bylo by dobré naj´ıt dalˇs´ı velké tˇr´ıdy slov s dobˇre rozm´ıstˇen´ ymi v´ yskyty a pˇredevˇs´ım by bylo dobré vˇedˇet, které pevné body morfism˚ u maj´ı vlastnost DRV. Také se zdá smysluplné studovat vlastnost DRV jen pro nˇekteré speci´ aln´ı moduly, kdy v definici vlastnosti DRV uvaˇzujeme jedno konkrétn´ı m m´ısto libovolného modulu. V souvislosti se statistick´ ymi testy je pole p˚ usobnosti jeˇstˇe vˇetˇs´ı – kromˇe aperiodicity a absence mˇr´ıˇzkové struktury nen´ı dosud ˇz´ adn´ y dalˇs´ı u ´spˇech v testech vysvˇetlen teoreticky. Samozˇrejmˇe pokraˇcujeme také ve statistick´ ych testech, kdy kombinujeme jiné neˇz LCG generátory a v´ ysledky porovn´ av´ ame s obdobnˇe rychl´ ymi PRNG. ˇ 13-03538 Podˇ ekov´ an´ı. Prvn´ı z autor˚ u dˇekuje za finanˇcn´ı podporu grantu GACR ˇ a L’Oréalu Cesk´ a republika za stipendium Pro ˇzeny ve vˇedˇe.

Literatura ´ , L’.: Nahlédnut´ı pod pokliˇcku kombinatoriky na nekoneˇcn´ [1] Balkova ych slovech. PMFA 56 (2011), 9–18. ´ , L’., Bucci, M., De Luca, A., Puzynina, S.: Infinite words with well dis[2] Balkova tributed occurrences. J. Karhum¨ aki, A. Lepist¨ o, L. Zamboni (eds): Combinatorics on Words, LNCS 8079, Springer, 2013, 46–57. ´ , L’., Bucci, M., De Luca, A., Hladky ´ , J., Puzynina, S.: Pseudorandom [3] Balkova number generators based on infinite words. Zasl´ ano do Math. Comp. (2013), dostupné z arXiv: 1311.6002. [4] Doty-Humphrey, C.: Practically Random: C++ library of statistical tests for RNGs. Dostupné z: https://sourceforge.net/projects/pracrand [5] L’Ecuyer, P., Simard, R.: TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Software 33 (4) (2007). [6] Guimond, L.-S., Patera, J.: Proving the deterministic period breaking of linear congruential generators using two tile quasicrystals. Math. Comp. 71 (237) (2002), 319–332. [7] Guimond, L.-S., Patera, J., Patera, J.: Combining random number generators using cut-and-project sequences. Czechoslovak J. Phys. 51 (2001), 305–311. [8] Guimond, L.-S., Patera, J., Patera, J.: Statistical properties and implementation of aperiodic pseudorandom number generators. Appl. Numer. Math. 46 (3–4) (2003), 295–318. ´ J.: Random number generators based on the aperiodic infinite words. Do[9] Hladky stupné z: https://github.com/jirka-h/aprng [10] Marsaglia, G.: Random numbers fall mainly in the planes. Proc. Natl. Acad. Sci. USA 61 (1) (1968), 25–28. [11] Morse, M., Hedlund, G. A.: Symbolic dynamics. Amer. J. Math. 60 (1938), 815–866. [12] Patera, J.: Generating the Fibonacci chain in O(log n) space and O(n) time. Phys. Part. Nuclei 33 (2002), 118–122.

222


Pokroky matematiky, fyziky a astronomie

Recommend Documents