Generovanie (pseudo) náhodných čísel

Či už ide o šifrovanie alebo generovanie úrovní v hrách, potrebujeme v aplikáciách často používať náhodné čísla alebo aspoň čísla, ktorá sa ako náhodná tvárou. Čisto náhodné čísla klasický deterministický počítač generovať nedokáže, pretože sa riadi presnými pravidlami a nevie skrátka len tak "niečo streliť". To možno v praxi obísť generovaním tzv. Pseudonáhodných čísel, ktoré sú síce počítaná čisto predvídateľným spôsobom, však majú charakter náhodného šumu, čo nám väčšinou postačuje. Pre prípady, keď sú striktne vyžadujú čisto náhodné čísla, majú niektoré procesory obvody, ktoré také čísla dokáže generovať na základe zákonov kvantovej mechaniky. Tieto obvody ale nie sú príliš rýchle a bežne nie sú potrebné, preto sa tu budeme zaoberať číslami pseudonáhodných a odteraz kedykoľvek budem písať o náhodných číslach, myslím implicitne čísla pseudonáhodná.

Kongruentní generátor

Základom generovanie náhodných čísel je procedúra generujúce hodnoty v určitom intervale. Typicky sa používa tzv. Kongruentní generátor (existujú alternatívy ako napríklad Mersenne twister). Kongruentní generátor funguje na základe rovníc:

x ₀ = Z

x _{n + 1} = (A * x _n + C) mod M

Vidíme, že ide o vzorec pre postupnosť hodnôt, kedy prvú hodnotu (x 0), tzv. Seed, zvolíme (Z) a každú ďalšiu spočítame tak, že vezmeme aktuálnu hodnotu, vynásobíme ju zvolenú konštantou (A), pripočítame inú zvolenú konštantu (C) as výsledkom prevedieme operáciu modulo M (zvyšok po delení M). Konštanta M je tzv. Perióda. Ide o dôležité číslo, pretože najneskôr po m krokoch sa generovaná postupnosť začne opakovať. Musíme teda s týmto faktom počítať a voliť M vhodne vysoké.

Pri nevhodne zvolených parametroch môžeme u generovaných čísel vypozorovať určitú súvislosť (napr. Keď je zakreslíme ako body roviny, môžeme dostať priamku), preto existujú rôzne štatistické testy na určovanie kvality generátora. Vhodné hodnoty, ktoré využíva napr. Štandardná knižnica jazyka C sú M = 2 ^32, A = 1103515245, C = 12345.

Je zrejmé, že generátor bude vždy vytvárať rovnakú postupnosť v závislosti na počiatočnej hodnote (seedu). Pre každé spustenie aplikácie teda dostaneme vždy rovnaký výsledok, čo sa niekedy, napr. Pri simuláciách, hodí a inokedy, napríklad v hrách, nie. Pre dosiahnutie rôznosti postupnosťou sa preto typicky ako seed používa hodnota založená na aktuálnom čase - keďže program spúšťame v rôznych časoch, generovaná postupnosť bude zakaždým iná.

Akonáhle máme číslo vygenerované, je vhodné ho previesť do určitého intervalu, napr <0,1) (bez koncové jedničky, tá nemôže byť vygenerovaná). To urobíme samozrejme tak, že ho v plávajúcej rádovej čiarke, delí M.

Dôvod, prečo jedničku vo výstupe nechceme, vyplýva z požiadavky použiť túto funkciu pre generovanie celých čísel. Ak chceme funkciu použiť pre generovanie celých čísel v intervale <0, N>, tak jednoducho vynásobíme výstup generátora (teda číslo 0 až 1, bez koncovej jednotky) hodnotou N + 1 a číslo zaokrúhlime odseknutím desatinné časti.

Pre úplnosť uveďme príklad kongruentního generátora v jazyku C:

#include <stdio.h>

unsigned int x = 10341; // nahodila hodnota - seed

double muj_rand()  // vraci nahodnou hodnotu v rozsahu <0,1>
  {
    x = (1103515245 * x + 12345) % 4294967296;
    return x / ((double) 4294967296); // prevedeni do intervalu <0,1)
  }

int main()
  {
    int i;
    for (i = 0; i < 100; i++)
      printf("%lf\n",muj_rand());

    getchar();
    return 0;
  }

Generovanie rôznych pravdepodobnostných rozložení

Generátor sám o sebe produkuje čísla v rovnomernom rozložení, tzn. každé číslo z intervalu má rovnakú pravdepodobnosť byť vygenerované. To však nie vždy potrebujeme. Niekedy chceme generovať rozloženie normálne, exponenciálne či nejaké vlastné. V takom prípade klasicky vygenerujeme hodnotu v bežnom, rovnomernom rozložení a použijeme niektorú z metód pre prevod na iné rozloženie:

• inverzný transformácie - Pre použitie inverzné transformácie potrebujeme poznať distribučnú funkciu pravdepodobnosti daného rozloženie, čo je funkcia, ktorá hovorí, aká je pravdepodobnosť, že náhodná veličina nebude väčšia než daná hodnota, a ktorá sa značí F (x). Pokiaľ k tejto funkcii dokážeme zostrojiť inverznú funkciu F -1 (x), potom stačí vygenerovať náhodné číslo v intervale <0,1> a odovzdať ho ako argument tejto funkcii. Číslo, ktoré nám vyjde, je číslo v požadovanom rozložení. Dodajme, že inverzná funkcia k funkcii g (x) je funkcia, ktoré odovzdáme číslo a ona nám povie, aký argument musíme dať funkciu g (x), aby sme z nej toto číslo dostali (skrátka si osi x a y prehodí role).

Príklad inverzné transformácie

• vylučovacia metóda - Ide o pomerne priamočiaru metódu. Ak poznáme funkciu rozloženie hustoty pravdepodobnosti p (x), môžeme s použitím rovnomerného rozloženia generovať náhodne body v dvojrozmernom priestore, tzn. súradnice x a y, tak dlho, kým vygenerovaný bod nepadne pod graf funkcie, čo znamená, že číslo x je číslom vygenerovaným v danom rozložení. Hodnoty pre x samozrejme generujeme v intervale rozsahu funkcie hustoty pravdepodobnosti a hodnoty y v intervale odbore jej hodnôt, inak by sme sa výsledku nemuseli dočkať. Metóda nie je vhodná pre prípady, kedy je veľká pravdepodobnosť, že vygenerovaný bod padne mimo, čo znamená nové generovanie bodu a spomalenie algoritmu (takže napr. Funkcie s definičnom odborom všetkých reálnych čísel ako je normálne rozloženie). Uveďme krátky príklad pre ilustráciu:

double hustota_pravdepodobnosti(double x)

  // definicni obor funkce je zde od 0,2 po 1,5
  {
    ... // zde je definice funcke hustoty pravdepodobnosti
  }

double moje_rozlozeni()
  {
    double x, y;

    while (1)
      {
        x = muj_rand() * 1.3 + 0.2; // generuje x v rozsahu 0,2 az 1,5
        y = muj_rand() * 1.1; // generuje cislo v rozsahu 0 az 1,1

        if (y <= hustota_pravdepodobnosti(x))
          return x;
      }
  }

• centrálna limitná veta pre normálne rozdelenie - Táto teoréma hovorí, že súčet niekoľkých hodnôt v ľubovoľnom rozložení konverguje k rozloženiu normálnemu. Môžeme ju preto využiť vtedy, keď potrebujeme vygenerovať približne normálne rozloženie za pomoci rovnomerného. Princíp sa dá demonštrovať na prípade, kedy generujeme čísla 2 kockami - je len jeden spôsob, ako hodiť číslo 2 (1 na oboch kockách), ale je mnoho spôsobov, ako hodiť číslo 7 (1 + 6, 2 + 5, 3 + 4 atď.), číslo 7 má teda vyššiu pravdepodobnosť výskytu. Príkladom jednoduché funkcie môže byť táto:

double normalni_rozlozeni()
  {
    int soucet, i;

    for (i = 0; i < 10; i++) // 10x rovnomerne rozlozeni
      soucet += muj_rand() * 11; // cislo 0 az 10

    return soucet / ((double) 100);
  }

• kombinácie rôznych metód (pre zložitejšie rozloženie)

Záverom

Vidíme, že generovanie náhodných čísel nie je triviálnym problémom. Pri mnohých vedeckých simuláciách môže byť navyše táto akcia kritická a preto by sme si mali byť vedomí aspoň základných princípov fungovania náhodných generátorov, ktoré by tento článok mal pokrývať.

V ďalšej lekcii, Gaussova eliminácia a Gauss-Jordanova eliminácia , sa pozrieme už na ľahko pokročilejšie pojmy ako Gaussova a Gauss-Jordanov elimináciu.