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 2¹⁹⁹³⁷-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_i, za určitý časový okamih Δt. Celá procedúra je trikrát zopakovaná a je vygenerované číslo S_ii a S_iii. Posledný (najmenej signifikantný) bit získaný z binárneho zápisu súčtu S_i+S_ii+S_iii 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 x₀ 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

z_n = (x_n + y_n) mod m

kde x_n resp. y_n 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

• DEÁK, István. Random number generators and simulation. [s.l.] : [s.n.], 1990. ISBN 963-05-5316-3.

Externé odkazy

• Náhodné čísla v MS Excel Archivované 2011-01-22 na Wayback Machine
• pHp generátor náhodných čísel
• Random number generator – The pLab project (po anglicky) Archivované 2011-04-14 na Wayback Machine