Generátor náhodných čísiel

**Generátor náhodných čísel** je zariadenie alebo procedúra, ktorá generuje čísla ktoré naozaj sú alebo len pripomínajú náhodné čísla.

## Úvod
Jedna z najdôležitejších metodológií k riešeniu problémov v operačnom výskume, numerickej analýze, rôznych simuláciách, rozhodovaní, počítačovej grafike, kryptológií, dátovej komunikácií, internet bankingu a štatistike je nasadenie experimentov, či postupov založených na náhode. Príkladom z histórie je Archimedes zo Syrakúz, ktorý sa takto pokúšal aproximovať hodnotu π.

Metóda náhodných experimentov prešla od roku 1940 rýchlym vývojom vpred. Obrovský rozmach počítačov a nárast výpočtových kapacít, dovolil generovanie skutočne veľkého množstva vysokých náhodných čísel. 
Na začiatku sa nová metóda používala hlavne na riešenie problémov, ktoré boli spojené s jadrovými elektrárňami a vývojom atómovej bomby v projekte Manhattan. Čoskoro sa ale zistilo, že tieto metódy sa hodia aj na riešenie veľkého množstva ekonomických, matematických a fyzikálnych problémov.

John Von Neuman, ktorý sa považuje za otca myšlienky, nazval tieto metódy Monte Carlo.

## Rozdelenie generátorov náhodných čísel
Hardwarové generátory založené na snímaní fyzikálneho deja, inak sa označujú ako TRNG (True Random Number Generator) – generátory skutočne náhodných čísel. Z televízie  napríklad poznáme zariadenie na žrebovanie čísel športky.

Generovanie náhodných čísel na základe určitých algoritmov, inak sa označujú ako PRNG (Pseudo-Random Number Generator) – generátory pseudonáhodných čísel.

Tabuľky náhodných čísel

*(Pri preklade do slovenčiny vznikajú nepresnosti, preto sa odporúča používať výrazy TRNG a PRNG.)*

## Základné vlastnosti generátorov náhodných čísel
* dlhá perióda, v ideálnom prípade nekonečne dlhá, v súčasnosti napr. generátor Mersenne Twister dosahuje periódu 219937-1
* rovnomerné a s rastúcou dĺžkou sekvencie čoraz lepšie zaplnenie intervalu (pokiaľ možno malo by platiť aj pre ľubovoľné subsekvencie)
* opakovateľnosť,čiže schopnosť opakovane generovať tú istú sekvenciu pseudonáhodných čísel pomocou jednoducho špecifikovaných počiatočných podmienok
* čas generovania je zanedbateľný oproti času operácií ktoré vytvorenú sekvenciu používajú
* požiadavky na pamäť a portabilita – implementácia nenáročná na pamäť a vo vyššom programovacom jazyku
* dobré štatistické vlastnosti, čo znamená, že generátor musí úspešne zdolať súbor štatistických testov, teoretických (ak sú k dispozícii) 

## Výhody a nevýhody TRNG a PRNG generátorov
### TRNG (True Random Number Generator)
Hlavná výhoda TRNG je nemožnosť predpovedať, alebo odhadnúť generovanú postupnosť. Generátor je neperiodický a vyznačuje sa zložitejšou štruktúrou. Pri získavaní náhodných čísel musíme počítať s hardwarovým zdržaním.

### PRNG (Pseudo-Random Number Generator)
Medzi hlavné výhody PRNG patrí jednoduchosť a rýchlosť. Nevýhodou je, že po určitom čase bude generátor poskytovať rovnaké výstupy. Preto pri jeho konštrukcii prevláda snaha o čo najväčšie predĺženie tejto periódy, ideálne na nekonečne dlho.
Neutrálnou vlastnosťou je schopnosť generátora poskytovať rovnaké výstupy z rovnakého počiatočného vstupu. (tzv.seed). Táto jeho schopnosť sa napríklad využíva, ak chceme meniť parametre simulácie, v ktorej požadujeme rovnaké vstupné dáta.

## Generátory TRNG (prirodzene náhodných čísel)
môžeme získať priradením číselnej hodnoty fyzikálnemu javu, alebo stavu fyzikálneho systému, či fyzikálnej veličiny v danom okamihu nám môže poskytnúť vhodný zdroj náhodných čísel. Je potrebné vybrať taký fyzikálny jav, u ktorého sa predpokladá náhodné správanie.

Napríklad 
* radiový šum,
rôzne druhy radiácie : 
* Ionizujúce žiarenie,
* Žiarenie gama,
* Röntgenové žiarenie,
* Rádiové žiarenie
* Kozmické žiarenie.

Za vhodný zdroj náhodných dát môžeme považovať aj pohyb atómov, prúdenie vody, premenlivú teplotu prostredia atď. Pri získavaní prirodzených náhodných čísel používame rôzne na to uspôsobené meradla a iné mechanické prostriedky. Nevýhodou tohto prístupu môže byť porucha prístroja, ktorú môžeme odhaliť až po dlhom čase. Obzvlášť nepríjemné je, ak táto chyba spôsobí nejaké vážne nedostatky vo výpočtoch.

### Získavanie prirodzene náhodných čísel
#### Generátor založený na využití šumu

Za zdroj náhodných dát možno považovať sústavu, ktorá sa skladá z telefónnej linky alebo tranzistoru, na ktorých vzniká rádiový šum a určitého signálneho zariadenia. Toto zariadenie je schopné registrovať udalosti, kedy šum prekročí predom stanovenú kritickú hranicu *c*. Po dobu na začiatku presne stanoveného času *Δt*. Pri prekročení kritickej hranice šumu zapíšeme 1, v opačnom prípade 0.  Týchto zariadení môžeme mať niekoľko v paralelnom zapojení. Pri správnom výbere času *t* a hranice *c*, môžeme získať náhodné číslo o veľkosti *k* bitov v rovnomernom rozložení {0,1}.

#### Generátor založený na využití gama žiarenia
Iným zdrojom prirodzene náhodných čísel je prístroj, ktorý je založený na náhodnom emitovaní gama častíc.

Skladá sa z :
* generátor gama častíc
* *X* detektorov gama častíc
* časový spínač

Určitá časť emitovaných gama častíc od prvého signálu časového spínača až po druhý signál je registrovaná prým detektorom gama častíc.

Od druhého k tretiemu časovému signálu sú emitované častice zachytené druhým detektorom.

Od tretieho signálu k štvrtému sú častice zachytené na treťom detektore atď. až po *X*.

Signál registrovaný *i*-tym detektorom označím *S<sub>i</sub>*, za určitý časový okamih *Δt*.  Celá procedúra je trikrát zopakovaná a je vygenerované číslo *S<sub>ii</sub>* a *S<sub>iii</sub>*. 
Posledný (najmenej signifikantný) bit získaný z binárneho zápisu súčtu *S<sub>i</sub>*+*S<sub>ii</sub>*+*S<sub>iii</sub>* je v tomto prípade považovaný za náhodný bit. Potom tento spôsob ponúka *X* náhodných bitov v jednom kroku v čase 3Δt.

#### Využitie náhodných udalostí vo vesmíre
Z pohľadu generovania náhodných čísel je zaujímavý projekt spoločnosti Yuzoz. Tá sa v minulosti pripravovala na spustenie služby generovania náhodných čísel s využitím náhodných úkazov vo vesmíre. Podľa slov zakladateľa Jeff Manbera, za zdroj dát by mali slúžiť údaje o solárnej aktivite, kozmickom prúdení. Projekt počítal s komerčným využitím. V súčasnosti je projekt už zastavený.

## Generátory PRNG (pseudo náhodných čísel)
### Kongruenčný generátor
pseudonáhodné čísla sú generované algoritmom v digitálnych počítačoch. Získané čísla sú kompletne deterministické, pretože sú generované na základe algoritmu a hodnoty nejakého parametru, s možnosťou výberu počiatočnej hodnoty, ktorá determinuje celú sekvenciu. V praxi nás uspokojí skutočnosť, že tieto čísla vyzerajú ako by boli z náhodného zdroja.

#### Lineárny kongruenčný generátor
hodnoty sú generované pomocou vzťahu

x*n* = (ax*n*-1+c) mod *m*
kde operácia mod je zvyšok po celočíselnom delení, a, c, m sú konštanty. Počiatočná hodnota x0 sa nazýva seed (semienko - násada do generátora).

#### Inverzný kongruenčný generátor
* Maximálne dosiahnuteľná perióda je m
* Inverzný prvok sa počíta inverzným Euklidovým algoritmom na nájdenie celočíselných riešení rovnice 1=⋅+⋅mkxx
* Sú vhodné na použitie pre paralelné algoritmy.

### Metódy zlepšenia vlastností PRNG
#### Skladaním aritmetických výstupov z niekoľkých generátorov
zn = (xn + yn) mod *m*
								
kde xn resp. yn sú výstupy z pôvodných generátorov. Vhodné je voliť nesúdeliteľné veľkosti periód jednotlivých generátorov.
 
#### Premiešavanie (shuffling)
Metóda na dodatočné zlepšenie vlastnosti generátora pseudonáhodných čísel. Je založená na využití existujúceho generátora, ktorý pre premiešavací algoritmus generuje semienka (seeds) a mení tak poradie vstupných hodnôt. Existuje niekoľko modifikácií tejto metódy.
Prvých k hodnôt  uložíme do poľa a (k+1)-tu hodnotu do pomocnej premennej idx. Výstupné hodnoty potom generujeme v dvoch krokoch nasledovne:
* pomocou premennej idx vyberieme hodnotu z poľa ktorá bude našim výstupom a na uvoľnené miesto vložíme novú vstupnú hodnotu
* výstupnú hodnotu okopírujeme do premennej idx.
## Pozri aj
* náhoda
* náhodné číslo
* generátor
* pseudonáhodné číslo

## Zdroje a referencie
* 


## Externé odkazy
* Náhodné čísla v MS Excel 
* pHp generátor náhodných čísel
* Random number generator – The pLab project  

Kategória:Algoritmy