Pri ustvarjanju programov velikokrat uporabljamo naključna števila oziroma funkcijo, ki se v javi imenuje Math.random(), v Pythonu random.random() in nam kot rezultat vrne naključno število. Seveda pa si računalnik ne mora izmislit naključnega števila, saj je vendarle stroj, tako naključna števila nekako izračuna. Nekaj algoritmov za izračun naključnih števil bomo omenili v nadaljevanju. Ker je prehod iz naravnih števil (z vključno številom 0) v decimalna števila enostaven, samo delimo z največjim številom, bomo v nadaljnjem besedilu govorili predvsem o naravnih številih, ki lahko zasedejo tudi manj pomnilnika. Običajno je rezultat funkcije za generiranje naključnih števi rezultat število v intervalu [0,1).

Predstavili bomo algoritme:

Kvadrat prejšnega števila

Algoritem K

Linearna kongruentna metoda

Matej Rožič

Leta 1946 je von Neuman predlagal algoritem, ki je temeljil na aritmetični operaciji. Predlagal je, da bi dobil naslednje »naključno« število kot vmesna števila v kvadratu predhodnega naključnega števila. Primer: Če je naključno 10 mestno število 5772156649, potem za izračun naslednika kvadriramo število 5772156649 in dobimo število 33317792380594909201. Nato vzamemo iz sredine (33317792380594909201) novo naključno 10 mestno število, ki je v tem primeru 7923805949. Seveda števila po takem algoritmu niso »naključna«, ker je vsako število določeno s predhodnikom. Algoritem ima tudi težavo, da se nekatera števila samopredvajajo kot na primer, ko enkrat dobimo število 0 potem so vsa naslednja naključna števila 0.

Algoritem za delovanje potrebuje prvo 10 mestno število X. Iz njega po korakih izračunamo naslednika.

Koraki so:

K1. [Izberemo število ponovitev] Število X delimo z 109, da dobimo najbolj obteženo števko rečemo ji število Y.

K2. [Izberemo naključen korak] Nastavimo število Z kot X/108 mod 10 (druga najbolj obtežena števka pri številu X). Sedaj gremo v korak K(3+Z) {ki je kot naključni korak v programu.

K3. [Zagotovimo, da je X ≥ 5•109] Če je X< 5•109 potem nastavimo X na X+5•109.

K4. [Sredinski kvadrat] Nadomestimo X z X2/105 mod 1010, to je sredina v kvadratu števila X.

K5. [Večkratnik] Nastavimo X kot vrednost 1001001001•X mod 1010.

K6. [Nepravi komplement] Če je X < 108 nastavimo X kot X+9814055677 drugače pa nastavimo X kot 1010-X.

K7. [Zamenjava vrstnega reda prvih pet števk z zadnjimi] Zamenjamo število X s številom 105•(X mod 105) + (X/105), kar je isto kot srednjih 10 števk izraza (1010+1)•X

K8. Enako kot K5.

K9. Povečamo vsako neničelno števko za 1.

K10. [99999 modulacija] Če je X < 105 potem nastavimo vrednost X na X2 +99999, v nasprotnem primeru pa nastavimo na X – 99999.

K11. [Normalizacija] Če je X<109 potem nastavimo vrednost X na 10X in ponavljamo, dokler številno ni večje kot 109.

K12. [Moderirana kvadratna sredina] Nadomestimo X z vrednostjo [X(X-1)/105] mod 1010 (to je srednjih 10 števk števila X(X-1).

K13. [Ponovitev] Če je Y>0, zmanjšamo Y za 1 in se vrnemo na korak K2. Če je Y=0 potem je število X novo naključno število.

Tak algoritem ima tudi težave, saj obstajajo števila, ki se samo generirajo. Tak primer števila je 6065038420.

Poglejmo korake pri izračunavanju novega "naključnega" števila po algoritmu K:

Največkrat se uporablja metoda, v kateri naslednje naključno število izračunamo s pomočjo deljenja po modulu mnogokratnika predhodnega naključnega števila , ki ga povečamo za neko število .

pri čemer je . Za to morajo biti izpolnjeni pogoji:

Vendar pa ima tak generator značilnost.

Poglejmo primer:

in potem dobimo zaporedje naključnih števil:

Opazimo, da ima zaporedje naključnih števil periodo, v našem primeru dolžine 4.

Mogoče je to zgolj slučaj. Poglejmo si še več primerov.

1. in , , Dobimo zaporedje

2. = 10 in , , Dobimo zaporedje

3. in , , Dobimo zaporedje

4. in , , Dobimo zaporedje

Opazimo, da imajo lahko zaporedja števil različno periodo od 1 v primeru 3 pa vse do 10 v primeru 4.

Če želimo uporabni generator naključnih števil potem potrebujemo takega z relativno dolgo periodo. V ta namen moramo uporabit »magična« števila , , in . O njihovih vrednostih v nadaljevanju.

Za poenostavitev enačb definirajmo:

Za nadaljnjo obravnavo lahko izključimo (), ki ni ravno generator naključnih števil, še slabše pa je . Torej lahko za praktični predlog predpostavimo, da je in .

Sedaj lahko posplošimo enačbo:

Kar predstavlja (n+k)-ti člen neposredno iz n–tega. Sledi, da je vsako podzaporedje sestavljeno iz k-tih elementov zaporedja zopet linearno kongruentno zaporedje z večkratnikom in prirastkom . Pomembna povezava z enačbo je, da je splošno zaporedje podano z , , in in se lahko preprosto izrazi če je in .

Glede na predhodno enačbo bomo imeli , zato splošna zaporedja izpolnjujejo

kjer je

Naš cilj je najti dober parameter , ki bo imel čim daljšo periodo, v ta namen mora biti število čim večje (sam ima lahko v periodi kvečjemu števil). Druga omejitev pa je hitrost delovanja. Radi bi, da je deljenje po modulu čim hitrejše (samo po sebi je deljenje nekoliko daljša operacija). Izkaže se, da je deljenje hitrejše, če je število velikosti besede v računalniku. Če z označimo velikost e–bitne besede v računalniku, potem je število omejeno z vrednostjo pri binarnih računalnikih ali z pri desetiških računalnikih. Da bi bila perioda čim večja je smiselno izbrati največje število, ki je manjše od vrednosti besede v računalniku.

Potem je potrebno dobro izbrati še večkratnik , da je učinkovitost najboljša. Da je ta pogoj izpolnjen, je najboljše, da sta števili in tuji in seveda . Pri tem je potrebno pazit, da obstaja povezava med dolžino periode in »dobrimi naključnimi« števili.

Primer : Če potem je naslednik enostavno izračunati kot

ki ima dolžino periode , vendar števila niso naključna (za 1 večje od predhodnika). Torej ni možno doseči dolžine periode . Kljub temu pa nekatere števila za dovoljujejo veliko izbir večkratnika . Dobre izbire nam povedo naslednji izreki:

izrek A

izrek B

izrek C

izrek D