Naključna števila so števila, ki se brez nekega smisla ali pravila podana z nekim zaporedjem. V nobenem primeru ne moremo napovedati naslednjega števila. Taka števila dobimo s pomočjo pojavov v naravi in računalniški tehnologiji. Praviloma so porazdeljena na pol zaprtem intervalu od 0 do 1 – [0,1). Takšna števila pravzaprav niso naključna števila ampak so psevdo-naključna števila. To pomeni, da so napovedljiva na znano pravilo, po katerem so narejena. Psevdo pa iz slovarja slovenskega knjižnega jezika pomeni:

psevdo... predpona v sestavljenkah

(e) nanašajoč se na a) lažen,

navidezen: psevdodemokracija,

psevdoznanstven b) nepravi, nepristen:

psevdogotika, psevdonaroden

Edini način za res naključna števila pa je potrebna uporaba fizikalnega procesa, ki je sam po sebi naključen. Primer takega načina je metanje kovanca ali kocke.

kocka

100 'naključno' izbranih števil med 0 in 4096 = 2^12

Iskanje naključnih števil segajo v leto 1908. Začel je angleški matematik, statistik in kemik William Sealy Gosset.Uporabljal je opazovalne metode. Primer take metode so telefonske številke, ki so bile klicane v nekem poljubnem času t. Naključna števila je uporabljal za njegove študije Studentove t-porazdelitve. Studentova porazdelitev je zvezna verjetnostna porazdelitev, ki jo je kasneje razvil ameriški statistik in teoretik Harold Hotelling ime pa je obdržala. Več o Studentovi t- porazdelitvi najdete na: http://sl.wikipedia.org/wiki/Studentova_t-porazdelitev

Na opazovanjih temeljijo tabele, v katerih so zapisana zaporedja naključnih števil. Primer take tabele je Tippettova tabela,ki je izšla v knjižni obliki, leta 1927. Vsebovala je 5200 osemmestnih naključnih števil. Leta 1955 pa je izšla tabela RAND Corporation z 125000 osemmestnih naključnih števil. Iz njih lahko »vzamemo« nek del in tako dobimo naključno podana števila.

Generatorji, tvorijo nova števila iz danih števil, po določenem postopku.

Poznamo pa različne generatorje za iskanje naključnih števil:

- Generator ki temelji na kvadriranju n mestnega števila,

- Generator, ki temelji na množenju dveh n mestnih števil,

- Mešani generator, ki temelji na množenju in seštevanju

- Linearen kongruenten generator - LCG, ki temelji na množenju in seštevanju, kot rezultat pa vrača ostanek pri deljenju.

Vsi razen LCG-ja generatorji temeljijo na rezanju robnih cifer. Začetno število dolžine n se imenuje seme. Delujejo za 2n mestno število, nato pa na levi in desni strani »odrežejo« n/2 cifer. Ti pa niso »najboljši«, saj se hitro izrodijo, t.j. da začnejo vračati število 0 ali pa neko drugo število. Niso pa tako uspešni saj RN(i) računamo iz RNM(i).Sposobnejši od njih je linearni kongruentni generator, ki je eden izmed najstarejših in najbolj znanih psevdonaključnih algoritmov.

• KRITERIJI KVALITETE NAKLJUČNIH GENERATORJEV:

- Učinkovitost: da generator vrne naključna števila ob majhni porabi časa in prostora

- Uniformnost : verjetnost, da je generirano določeno število, mora biti enako verjetnosti generiranja poljubnega drugega števila.

- Neodvisnost: če poznamo začetno vrednost, ne moremo napovedati naslednjega števila

- Dolga perioda naključnega zaporedja: da se zaporedje ponovi šele čez n členov

Ideja ja da s pomočjo kvadriranja iz n mestnega števila dobimo 2n mestno število. Nato pa z leve in desne odrežemo toliko števk, da spet dobimo n mestno število.

• Enačbi: RNM(i + 1) = RN(i)^2 in

RN(i + 1) = Reži(RNM(i + 1)), kjer i teče od 0 naprej in RN0 = seme. Reži je operacija, ko 2n mestnemu številu spredaj in zadaj odrežemo n/2 števk.

• POSTOPEK:

- Dano je n mestno število x

- Izračunamo kvadrat števila x ( x^2)

- Če izračunano število ni 2n mestno mu spredaj dodamo ustrezno število ničel (0)

- Z leve in desne odrežemo n/2 števk, da dobimo spet n mestno število. To je novo generirano število in postopek lahko ponovimo.

Generator pa se izrodi, saj začne vračati število 0. Da generator nebi v neskončnost vračal smo 0, bi lahko to popravili tako, da bi generator avtomatsko poskrbel za izbiro novega semena, takoj ko bi bilo novo generirano število enako nič.

• V tem primeru so bila generirana naslednja naključna števila: [13, 16, 25, 62, 84, 5, 2, 0, 0, ...]
• V tem primeru vidimo, da generator vrne naključna števila ob majhni porabi časa in prostora. Če nebi vedeli, da deluje po principu kvadratnega generatorja, bi lahko rekli, da so števila med seboj neodvisna. Velikost periode pa ni velika, saj začne generator po 7 koraku vračati še samo število nič.

Generator s pomočjo množenja je boljši od generatorja, ki temelji na kvadriranju, saj ima generator množenja kar dve semeni, ki se med seboj množita in tako dobimo novo naključno število. Tudi tu se generator izrodi in začne vračati število 0.

• Enačbi: RNM(i + 1) = RN(i) * RN(i – 1) in

RN(i +1) = Reži(RNM(i + 1)),

kjer je RN(0) = seme1,RN(1) = seme2, i pa teče od 1 naprej. Reži je operacija, ko 2n mestnemu številu spredaj in zadaj odrežemo n/2 števk.

• POSTOPEK :

- Dani sta dve semeni (x,y)

- Semeni zmnožimo (x * y)

- Če izračunano število ni 2n mestno mu spredaj dodamo ustrezno število ničel (0)

- Z leve in desne odrežemo n/2 števk, da dobimo spet n mestno število. To je novo generirano število. Npr.: z

- Nato novo generirano število zmnožimo z drugim semenom (y * z)

- nato postopek ponovimo.

primer delovanja generatorja s pomočjo množenja

• V tem primeru so bila generirana naslednja naključna števila: [1988, 1977, 9302, 3900, 2778, 8342, 1740, 5150, 9610, 4915, 2331, 4568, 6480, 9188, 1831, 8232, 727, 9846, 1580, 5566, 7942, 2051, 2890, 9273, 7989, 819, 5429, 4463, 2296, 2470, 6711, 5761, 6620, 1378, 1223, 6852, 3799, 307, 1662, ...,1622, 4174, 7702, 1481, 4066, 217, 8823, 9145, 6863, 7621, 3029, 840, 5443, 5721, ...]

• V našem primeru generator vrača naključna števila ob majhni porabi časa in prostora. Če nebi vedeli, da deluje generator po principu množenja naslednjega števila nebi mogli napovedati. Perioda pa se razlikuje tudi od tega koliko mestno število vzamemo za seme.Za ta primer vem, da ima periodo več kot 60.

Izhajamo iz operacij množenja in seštevanja, zato mu lahko pravimo mešani generator. Pri njem pa potrebujemo eno seme, ter še dve konstanti k in N. Pri njem se lahko zgodi, da bo naslednje pridobljeno število 0. Prav tako je lahko generirano število enako enemu od prej generiranih števil. To pa seveda pomeni, da se bo v zaporedju ta del zaporedja nenehno ponavljal. Z ustrezno izbiro konstant, bi dobili že dovolj »dobro« zaporedje naključnih števil.

• Enačbi: RNM(i + 1) = k * RN(i) + N in

RN(i + 1) = Reži(RNM(i + 1)), kjer je RN0 = seme, i pa teče od 0 naprej. Reži je enaka operacija kot v prejšnjih primerih.

• POSTOPEK :

- imamo seme (x) in dve konstanti (k in N)

- seme zmnožimo z k nato pa prištejemo še N ((k * x )+ N)

- Če izračunano število ni 2n mestno mu spredaj dodamo ustrezno število ničel (0)

- Z leve in desne odrežemo n/2 števk, da dobimo spet n mestno število. To je novo generirano število, postopek lahko ponovimo z novim generiranim številom.

primer delovanja mesanega generatorja

• V tem primeru so bila generirana naslednja naključna števila: [2641, 898, 305, 104, 35, 12, 4, 1, 0, 0,...]

• V tem primeru se je zaporedje generiralo v nič že po sedmem koraku, ne glede na to, da je bilo začetno število štiri mestno. Porabi malo časa in prostora. Naslednjega člena ne bi mogli napovedat, če ne bi poznali principa, po katerem deluje. Velikost periode pa ni velika, saj začne generator po 7 koraku vračati še samo število nič.

Je izboljšava generatorja, ki temelji na kvadriranju. Predlagal ga je Lehmer leta 1948.Z njim so odpravili napake, ki so se pojavljale pri generiranju z rezanjem robnih cifer. Kongruenca označuje relacijo med dvema številoma. Velja, da sta števili kongruentni, če je ostanek pr deljenju teh dveh števil z istim deliteljem enak.

• Enačba: RN(i + 1)= (a * RN(i) + b) (mod m)

Za njegovo delovanje potrebujemo seme, ter konstante a, b in m, ki označuje modul. Modul je ostanek pri deljenju. V različnih programskih jezikih, kjer je LCG že definiran, ga kličemo v obliki LCG(m,a,b,RN(0)). RN(0) podamo v obliki semena. Tega pa lahko fiksiramo znotraj generatorja ali pa ga poda sam uporabnik.

• POSTOPEK :

- Imamo seme (x), konstante (a, b in m)

- Zmnožimo a * x in prištejemo b , nato pa delimo še z m

- ostanek pri deljenju je novo generirano število. Postopek lahko ponovimo. Števili RN(i) in RN(i + 1), sta kongruentni, če sta manjši od števila m. Če ju delimo z a, je ostanek deljenja enak b.

• Metoda, ki po principu LCG išče naključna števila:

  Linearni kongruentni generator

Primeri uporabe LCG

• Pri prvem primeru bi res lahko rekli, da so števila izbrana naključno, brez kakršnega določenega zaporedja. Perioda v tem primeru pa je večja od 100. Poglejmo pa še kongruenco dveh zaporednih števil. Vzemimo drugo in tretje število, se pravi 169 in 2197, obe sta manjši od m. Ko ju delimo z a, ki je v tem primeru enak 13, dobimo ostanek 0, to pa je ravno število b. Tako vidimo,da sta števili res kongruentni.

• V drugem primeru na istem generatorju pa vidimo, da števila niso prav nič naključna. Enako velja za tretji primer. Saj se ponavlja par (1,0). Tukaj pa generator 'propade', saj števila niso naključna, Perioda je največ dve, in če poznamo prva dva člena, bi ostale člene lahko napovedali.

Iz tega je razvidno, da moramo res paziti kakšne podatke vnašamo v program. Najboljše rezultate dobimo, če za seme vzamemo čim manjše število. Za konstanto a in m čim večje število, veljati pa mora, da je m večje od a. Za konstanto b pa nekaj povprečnega, lahko tudi 0.

V Pythonu je že sprogramiran program, za iskanje naključnih števil. Deluje po Mersenne Twister-jevem principu, ki vrača 53 bitna realna števila in ima periodo 2^19937 – 1, temelji na matriki linearnih ponovitev.

V Pythonu moramo uvoziti knjižnico RANDOM z metodo RANDINT, ki vrača n števil z intervala od a do b.

• Metoda, ki deluje na vgrajeni funkciji :

  Metoda, ki vne n naključnih števil

Primeri 100 in 200 naključnih števil

• Vidimo, da se nekatera števila v obeh primerih ponovijo. Vendar zanj ne poznamo postopka, kako se števila generirajo.
• Ta generator, ki je že vgrajen v Paython nam v zelo hitrem času vrne naključna števila. Naslednjega števila ne znamo v naprej napovedati.

http://graph-srv.uni-mb.si/Ares/Poglavje%202.htm

http://wiki.fmf.uni-lj.si/wiki/Generator_naklju%C4%8Dnih_%C5%A1tevil

http://en.wikipedia.org/wiki/Mersenne_Twister

Prosojnice - Slučajnost iz fmf učilnice http://ucilnica.fmf.uni-lj.si/course/view.php?id=203