Generátor pseudonáhodných čísel: Porovnání verzí
Smazaný obsah Přidaný obsah
m Bot: Odstranění 20 odkazů interwiki, které jsou nyní dostupné na Wikidatech (d:q1623338) |
Dopsání článku z anglického originálu značka: odkaz do cizojazyčné Wikipedie |
||
Řádek 8:
Pro generování pseudonáhodných čísel na číslicových [[počítač]]ích existuje celá řada různých [[Algoritmus|algoritmů]]. Nejčastěji používané generátory využívají princip [[Lineární kongruentní generátor|lineárního kongruentního generátoru]]. Moderní metody, kromě již vzpomínaného Blum-Blum-Shub generátoru, zahrnují např. [[Mersenne twister]].
== Periodicita ==
Generátor pseudonáhodných čísel může začít z jakéhokoliv výchozího stavu použitím [[Random seed|random seed]] (náhodné číslo - počáteční stav). Poté vždy vyprodukuje stejnou sekvenci čísel, pokud je inicializován se stejným počátečním stavem. Perioda generátoru pseudonáhodných čísel je definována jako maximum nad všemi počátečními stavy délky neopakující se sekvence. Perioda je omezena velikostí stavu měřeného v bitech. Nicméně od té doby, co se délka periody potencionálně zdvojnásobuje s každým stavovým bitem. Potom je snadné vytvořit generátor pseudonáhodných čísel s periodou dostatečně dlouhou pro praktické aplikace.
Pokud vnitřní stav generátoru pseudonáhodných čísel obsahuje ''n'' bitů, pak jeho perioda nemůže být delší než 2<sup>n</sup> výsledných stavů, ale může být mnohem kratší. Pro některé generátory je možné délku periody vypočítat bez procházení skrze celou periodu. [[Linear feedback shift register|Linear Feedback Shift Registers]] jsou obvykle voleny s periodou 2<sup>n</sup>-1.[[Linear congruential generator|Linear congruential generators]] mají periodu, která může být vypočítána faktorizací. Přestože generátor pseudonáhodných čísel bude opakovat výsledky, poté co dosáhne konce periody, opakovaný výsledek nezaručuje dosažení konce periody, poněvadž jeho vnitřní stav může být větší než výsledný. To je zřejmé zejména u generátoru pseudonáhodných čísel s 1-bitovým výstupem.
Většina algoritmů pseudonáhodných generátorů produkuje sekvenci s rovnoměrným rozdělením.
== Problémy s deterministickými generátory ==
V praxi výstup z mnoha běžných generátorů pseudonáhodných čísel vykazuje [[:en:Artifact (error)|anomálii]], která způsobuje jejich selhání při statistické detekci vzoru.
Například:
* kratší než očekávané periody pro některé výchozí stavy (takové stavy mohou být nazvány "slabými", v tomto kontextu)
* chybějící rovnoměrnost rozdělení pro velké množství generovaných čísel
* korelace úspěšných hodnot
* slabá dimensionální distribuce výsledné sekvence
* rozdíl mezi tím, jak jsou určité hodnoty distribuovány od těch s náhodnou distribucí
== Literatura ==
| |||