Nenad Božidarević
Maj 2013.

Generisanje nasumičnih brojeva

Kao posledica bavljenja svojim diplomskim radom, došao sam do dela gde su mi bili potrebni nasumični brojevi (tema je određena primena genetskih algoritama, više o tome drugi put), pa sam odlučio malo ozbiljnije da ispitam razne mogućnosti za njihovo generisanje. Ispostavilo se da je u pitanju jedna veoma zanimljiva tema, čak i daleko opširnija nego što bi neko rekao na prvi pogled. Naravno, ono što je čini toliko zanimljivom jeste upravo njen naziv koji lako ume da nas zavara — nisu u pitanju nasumični brojevi, već “nasumični” (pseudonasumični) brojevi. O čemu se ovde zapravo radi?

Stvar je veoma jednostavna: nasumičnost ne postoji, a posebno ne u računarima. Čoveka možete priupitati da vam kaže proizvoljan broj, ali verovatnoća da taj čovek (ili žena) kao iz topa kaže devetmilionadvestapedesetišesthiljadatridesetisedam je daleko manja od verovatnoće da vam jednostavno kaže “osam”. Ukoliko se pogleda iz tog ugla, računari su zapravo mnogo bolji generatori nasumičnih brojeva, ali i dalje nisu savršeni.

Problem leži u tome što je u računarima sve determinističko, pa algoritam do nasumičnog broja mora da dođe na određen način koji je sve samo ne nasumičan. Jedan od jednostavnijih metoda je generisanje sekvence brojeva na sledeći način:

X_{n+1} = (aX_n + b)\ mod\ m

Očigledno, svaki od brojeva će biti iz intervala [0, m), gde će nasumičnost sekvence zavisiti od početne vrednosti koja se naziva seed (iliti seme), a neka vrednost će se u najboljem slučaju ponoviti nakon m generisanja (na osnovu trpanja golubova u rupe). Da bismo ovaj proces učinili “kvalitetnijim”, za seed se često koristi trenutno vreme (odnosno UNIX timestamp), pa drugo pokretanje programa nakon samo jedne sekunde može dati potpuno drugačije vrednosti. Mana ovog konkretnog pristupa je što se nakon prvog ponavljanja neke vrednosti cela sekvenca ponavlja; neki drugi pristupi nakon prvog ponavljanja vrednosti ipak daju drugačiju sekvencu, odnosno imaju mnogo veću periodu, jer i drugi parametri utiču na generisanje vrednosti. Složićete se, ipak, da ovakvo generisanje zapravo nije uopšte nasumično, ali je za potrebne mnogih i više nego dovoljno, dok za potrebe ostalih C++ nudi random_device generator koji se oslanja na adekvatan hardver, ukoliko je isti dostupan. Međutim, čak i ako imate dobar generator, to vas neće sprečiti da ga upropastite ukoliko ga uzmete zdravo za gotovo. Demonstrirajmo to na tri jednostavna primera.

Pročitaj ostatak teksta