Generator naključnih števil

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Generator naključnih števil je funkcija, vgrajena v večino programskih jezikov, ki vrne naključno število, praviloma enakomerno porazadeljeno na intervalu [0,1). Zares tako število ni naključno, ampak je psevdo-naključno število, saj tipični programski jezik nima dostopa do pravega vira naključnosti.

Mathematica v ta namen uporablja ukaz Random[ ].

V vsakdanjem življenju se pogosto uporabljajo naključna števila. Ampak ali so res naključna? Pravih naključnih števil je malo. Večinoma se pojavljajo števila, ki so na vpogled naključna in v resnici delujejo po določenem pravilu. To so že prej omenjena psevdo-naključna števila, ki si sledijo po točno določenem algoritmu in se po določenem času niz ponovi.

Vsak generator ima določene lastnosti, na podlagi katerih lahko rečemo, da je generator dober ali slab. Te lastnosti je potrebno preveriti s pomočjo statističnih testov. Pozitivno je, da so dobre statistične lastnosti niza, dolga perioda, čisto naključno seme za inicializacijo generatorja, hitrost in komplekstnost.

Vsebina

Zgodovina

del strani L.H.C. Tippettove tabele naključnih števil izdanih v knjižni obliki leta 1927(zapisano z roko)
Enlarge
del strani L.H.C. Tippettove tabele naključnih števil izdanih v knjižni obliki leta 1927
(zapisano z roko)
del strani tabele RAND Corporation izdane 1955 (zadnji zapis naključnih števil brez uporabe psevdo-naključnih algoritmov)
Enlarge
del strani tabele RAND Corporation izdane 1955 (zadnji zapis naključnih števil brez uporabe psevdo-naključnih algoritmov)

Začetki naključnih števil segajo vse do leta 1908, ko je matematik Wiliam Sealey Gosset uporabljal naključna števila za študij njegove Studentove t-porazdelitve. Uporabljal je opazovalne metode. Dober primer takšne metode so telefonske številke, ki so bile klicane v nekem času t. Naključen niz števil od 0 do 9 lahko sestavimo, tako da odrežemo predpono, ki se ponavlja, ostale številke pa napišemo eno za drugo. Takšna metoda opazovanja zna biti dolgotrajna in vsebovati mora dovolj dolgi niz števil, da lahko z njim generiramo največ možnih naključnih števil.


Na podlagi opazovanj so začeli zaporedja števil zapisovati v tabele, ki so jih izdajali v knjižni obliki. Leta 1927 je takšno knjigo izdal L. H. C. Tippett, ki je vsebovala zaporedje z 41600 številkami, kar je bilo dovolj za 5200 osemmestnih naključnih števil. Vendar je ta tabela še vedno vsebovala premalo števil. Zato sta Maurice George Kendall in Bernard Babington Smith leta 1939 izdala tabelo z zaporedjem 100000 števil, kar je bilo dovolj za 12500 števil. Leta 1955 je Rand Corporation izdala tabelo z zaporedjem kar 1000000 števil in je zadostovala za 125000 osemmestnih naključnih števil. Glavni problem take metode je prevelika poraba časa.


Več si lahko pogledate na spodnjih povezavah:


angleški wiki o Wiliamu Sealeyu Gossetu
angleški wiki o L. H. C. Tippettu
angleški wiki o Mauricu Kendallu
angleški wiki o RAND Corporation

Generatorji z rezanjem robnih cifer

Naključno zaporedje se začne z začetno vrednostjo, ki se imenuje seme ("seed"). To je n mestno celo število. Ti generatorji iz n mestnega števila generirajo 2n mestno število. Nato pa na vsaki strani odrežejo n/2 cifer. Po načinu generiranja 2n mestnega števila ločimo:

Delovanje teh generatorjev je dokaj enostavno in tudi niso najbolj uspešni, ker se hitro izrodijo. To pomeni, da začnejo vračati samo število 0.

Linearni kongruentni generatorji

Linearni kongruentni generator je predlagal Lehmer leta 1948. Z njim so odpravili napake, ki se pojavljajo pri generatorjih z rezanjem robnih cifer. Sama beseda kongruenca pomeni, da je ostanek pri deljenju dveh števil z istim deljiteljem enak. Kar je uporabljeno v enačbi:

RNi+1=aRNi + b(mod m)
a, b, m = številske konstante (definirajo generator)
LCG(m, a, b, RN0) = oznaka za linearne kongruentne generatorje

Naključno število RNi+1 se izračuna iz števila RNi. Število RN0 lahko fiksiramo ali pa ga poda uporabnik sam. Števili RNi+1 in RNi sta kongruentni, če sta manjši od števila m. Ko ju delimo s konstanto a, je ostanek pri deljenju enak b.

Prikaz delovanja algoritma:

Imamo podano npr.: seme=62, a=71, b=21 in m=51.

RN0=62
//vzamemo seme 62,
RN1=37
//vstavimo konstante v formulo in dobimo 71*62+21(mod 51)=4423(mod 51)=37,
RN2=47
//71*37+21(mod 51)=2648(mod 51)=47,
RN3=43
//71*47+21(mod 51)=3358(mod 51)=43,
RN4=14
//71*43+21(mod 51)=3074(mod 51)=14,
RN5=46
//71*14+21(mod 51)=1015(mod 51)=46,
RN6=23
//71*46+21(mod 51)=3287(mod 51)=23,
RN7=22
//71*23+21(mod 51)=1654(mod 51)=22,
RN8=2
//71*22+21(mod 51)=1583(mod 51)=2,
RN9=10
//71*2+21(mod 51)=163(mod 51)=10,
RN10=17
//71*10+21(mod 51)=731(mod 51)=17,
RN11=4
//71*17+21(mod 51)=1228(mod 51)=4,
RN12=50
//71*4+21(mod 51)=305(mod 51)=50,
RN13=1
//71*50+21(mod 51)=3571(mod 51)=1.
RN14=41
//71*1+21(mod 51)=92(mod 51)=41,
RN15=25
//71*41+21(mod 51)=2932(mod 51)=25,
RN16=11
//71*25+21(mod 51)=1796(mod 51)=11,
RN17=37
//zaporedje se prične ponavljati.

Najbolj znani linearni generatorji so:

Osebna orodja