Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Generator slucajnih brojeva ?

[es] :: Nauka :: Generator slucajnih brojeva ?

[ Pregleda: 13236 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

van t hoff

Član broj: 13138
Poruke: 230
*.blueisp.co.yu.



Profil

icon Generator slucajnih brojeva ?13.02.2005. u 17:29 - pre 232 meseci
Kako rade generatori slucajnih brojeva. Moj primjer, na casio digitronu imam opciju random, gdje mi on nasumice izbaci neki trocifren broj.
Kako to radi?

Generalno kako rade generatori slucajnih brojeva (pa i ovi na racunaru)?
 
Odgovor na temu

Dark Icarus
Goran Lalić
Beograd

Član broj: 19775
Poruke: 428
*.sbb.co.yu.



+2 Profil

icon Re: Generator slucajnih brojeva ?13.02.2005. u 19:41 - pre 232 meseci
To i mene živo interesuje... znam da se za svaki random (koji kompjuter koristi) koristi seed. Isti seed će uvek dati isti broj. E sada šta se dešava na putu seed -> rezultat, stvarno ne znam. Znam samo da ako kompjuteru ne daš seed on će iskoristiti system clock za seed.

I još jedna zanimljiva stvar... jednom prilikom sam dao kompjuteru da generiše mnogo uzastopnih brojeva zaredom, a svaki par brojeva sam koristio za koordinate jedne "zvezde" na ekranu. Začudilo me je to što su se zvezde raspoređivale na ekranu po očigledno pravilnim obrascima!!!

Onda sam shvatio da to sigurno ima veze sa tim što između dva poziva rnd() komandi proteknu skoro identični intervali vremena.
Znači postoji veza između pravilnosti seeda i pravilnosti outputa.

Kada sam rekao kompjuteru da generiše pseudorandom niz (svaki prethodni rezultat rnd-a se koristi kao seed za sledeći rnd) problem je nestao.
In a game of chess you must never let your opponent see your pieces - Zap
Brannigan
 
Odgovor na temu

Duck_
Darko Jovanović
Sremska Kamenica

Član broj: 43509
Poruke: 67
*.telekom.yu.

Sajt: www.google.com


Profil

icon Re: Generator slucajnih brojeva ?13.02.2005. u 22:30 - pre 232 meseci
Koliko ja znam postoji niz pseudoslučajnih brojeva koji izgleda otprilike ovako:

0,4523
0,1299
0,0030
0,9811
0,8231
i tako dalje. Pretpostavljam da se ovaj niz sastoji od 256 ili 512 brojeva.

Ovi brojeve je verovatno neki programer zapisao vrteći neki automat poput loto bubnja. Znači zaista su nastali slučajno.
Zovu se psedudoslučajni jer se u kompjuteru ne pojavljuju baš slučajno nego verovatno uvek istim redosledom.

U drugoj fazi ovi brojevi se množe sa trenutnim brojem milisekundi u kompjuterskom časovniku i tako se dobijaju SLUČAJNI brojevi.

U GWBASIC-u funkcija RND() je davala kao rezultat pseudoslučajni broj a ako je pre nje korišćena komanda RANDOMIZE onda je davala proizvod pseudoslučajnog broja i boja milisekundi tj. SLUČAJNI BROJ.

 
Odgovor na temu

Alef
Viktor Kerkez
Novi Sad

Član broj: 505
Poruke: 188
*.143.eunet.yu.



Profil

icon Re: Generator slucajnih brojeva ?13.02.2005. u 23:01 - pre 232 meseci
http://www.elitesecurity.org/tema/76012
http://www.elitesecurity.org/tema/1782
 
Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
*.yubc.net.



+27 Profil

icon Re: Generator slucajnih brojeva ?14.02.2005. u 13:19 - pre 232 meseci
Svojevremeno mi je trebao (a trebaće i opet, pre ili kasnije) dobar generator slučajnih brojeva, pa sam se tada malo informisao na tu temu.

Slučajni brojevi koje računar daje i nazivaju se pseudoslučajnim, jer u stvari uopšte nisu slučajni, već samo do određene mere imaju osobine slučajnih brojeva, tj. zadovoljavaju matematičke definicije i postupke za proveru slučajnosti datog niza brojeva.

Pseudoslučajni brojevi generišu se provlačenjem zadatog semena kroz neku matematičku formulu. Jedina slučajnost, dakle, može biti u semenu — u najprostijem slučaju to je trenutno vreme sa časovnika, a i sistem može pružati neki bazen entropije (npr. Linuks daje /dev/urandom). Takođe, te formule su takve, da će, za dato seme, posle izvesnog niza brojeva početi da ponavljaju iste brojeve (periodičnost).

Koliko mi je poznato, podrazumevani generator slučajnih brojeva u većini jezika jeste „linearni kongruentni“ (linear congruential) generator, jer je vrlo prost za implementaciju i njegove osobine su dobro matematički ispitane. Međutim, brojevi koje daje imaju slabe osobine slučajnosti, i periodičnost im je vrlo mala (relativno, naravno). Trenutno najbolji generator pseudoslučajnih brojeva (za nekriptografske primene) jeste „Mersenov obrtač“ (Mersenne Twister); relativno je nov (1998), ali se lako mogu naći implementacije za veliki broj programskih jezika.

Vrlo mi je interesantan Goranov primer. Prvo sam pomislio da se u prvom slučaju iskazala slaba slučajnost/periodičnost linearnog kongruentnog generatora, jer baš ljudsko oko lako zapaža pravilnosti u grafičkim prikazima koji bi trebalo da imaju slučajne oblike (zato se Mersenov obrtač i koristi puno u oblasti računarske grafike). Ali sam se onda urazumio, nije valjda generisao stotine hiljada zvezda za Ksenofobiju :) (bilo koji generator bi trebalo da se izbori sa bar nekoliko desetina hiljada brojeva)? Zapravo je uradio sledeće (pretpostavljam, naravno): generisao je seme (vreme sa časovnika) za svaki sledeći slučajan broj, a to upravo ne treba činiti, za bilo koji generator; slično seme (mali pomak časovnika) daje i slične prve slučajne brojeve u nizu (posebno kod linearnog kongruentnog generatora). Način na koji je rešio problem, upravo jeste način na koji linearni kongruentni generator normalno radi, tj. računa novi broj na osnovu prethodnog (seme je tu prvi broj u nizu).
 
Odgovor na temu

Dark Icarus
Goran Lalić
Beograd

Član broj: 19775
Poruke: 428
*.sbb.co.yu.



+2 Profil

icon Re: Generator slucajnih brojeva ?14.02.2005. u 21:23 - pre 232 meseci
Vrlo, vrlo moguće da je upravo to što kažeš... od tada pre svake implementacije rnd() i randomize() funkcija ja lepo pročitam MSDN help, sve lepo piše...

Ono što mene interesuje to je, koja je to funkcija kroz koju seed biva propušten? Ako je nasumicni_broj = f(seed) , onda mene interesuje baš ono f.

I inače bio je poveći broj zvezda u 2d sistemu (to je bila prvobitna podloga za ekran, crtao sam zvezde jednu po jednu kao tačkice), oko 300-400 na ekranu, i baš se lepo videla periodičnost. Povremeno su se raspoređivale u skoro geometrijskim obrascima (there's money to be made here somewhere, I'm sure...). Šteta što nisam sačuvao source, bila bi dobra demonstracija kako ne treba koristiti rnd funkciju.
In a game of chess you must never let your opponent see your pieces - Zap
Brannigan
 
Odgovor na temu

Sundance

Član broj: 7510
Poruke: 2559
*.sava.sczg.hr.



Profil

icon Re: Generator slucajnih brojeva ?16.02.2005. u 15:41 - pre 232 meseci
http://sigurnost.zemris.fer.hr/random/

Kad ste već spomenuli RNG, red bi bio i da spomenem Global Consciousness Project.

Šta mislite o ovome, ima li čovječanstvo "globalnu podsvijest" :>
 
Odgovor na temu

CimBac
Fax
Novi Sad

Član broj: 37332
Poruke: 157
*.nspoint.net.

Sajt: irrlicht.sourceforge.net


Profil

icon Re: Generator slucajnih brojeva ?17.02.2005. u 02:49 - pre 232 meseci
Citat:
Ono što mene interesuje to je, koja je to funkcija kroz koju seed biva propušten? Ako je nasumicni_broj = f(seed) , onda mene interesuje baš ono f.


Sto se tice funkcije mislim da bi trebao da pokusas sam da je napises. Nalupas nesto za pocetak, propustis kroz tvoj program koji ponovo napises, vidis sablon, doteras funkciju, vidis sablon, doteras funkciju...Sve dok ne bude bilo lako uocljivog sablona.

Citat:
Šta mislite o ovome, ima li čovječanstvo "globalnu podsvijest" :>

Navedeni clanak lepo govori ono sto ja pokusavam ljudima da objasnim :)
Potpuno se slazem.
 
Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
*.yubc.net.



+27 Profil

icon Re: Generator slucajnih brojeva ?17.02.2005. u 11:24 - pre 232 meseci
Citat:
Dark Icarus
Ono što mene interesuje to je, koja je to funkcija kroz koju seed biva propušten? Ako je nasumicni_broj = f(seed) , onda mene interesuje baš ono f.

Za linearni kongruentni generator funkcija je rekurentna:

f(x) := (a * x + b) mod m
r[k] = {f(s), k = 0; f(r[k - 1]), k > 0}

gde je s seme, r niz „slučajnih“ brojeva, a, b, m fiksirani celi (poveliki) brojevi. Upravo izbor a, b, m razlikuje jedan od drugog lin. kon. generatora.

Više o tome na Vikipediji (http://en.wikipedia.org/wiki/Linear_congruential_generator).
 
Odgovor na temu

Dark Icarus
Goran Lalić
Beograd

Član broj: 19775
Poruke: 428
*.sbb.co.yu.



+2 Profil

icon Re: Generator slucajnih brojeva ?19.02.2005. u 01:01 - pre 232 meseci
Hvala na informaciji!

Pa baš zato sam i pitao, jer sam jedno vreme razmišljao o pravljenju sopstvenog random sistema, u sklopu sa algoritmom za enkripciju, gde brzina same funkcije ne bi bila bitna.

Šta kažete na ovo: najveća perverzija koja mi je pala na pamet je da koristim neku formulu da na osnovu seeda generišem fraktalnu sliku. Onda bih koristio pseudonasumično izabrane piksele te slike kao novi seed.

(Ako nekog interesuje, enkripcija bi nastavljala ovako: za svaki bajt u enkriptovanom fajlu (na osnovu njegove pozicije i njegove vrednosti kao kumulativnog seeda), birao bih npr. pet pseudonasumično odabranih piksela sa slike, pa da ih propustim kroz seriju modifikujućih randomizacija.
Na kraju sve piksele sortiram u jednu dugačku liniju, ali ne po redu već ih pretumbam (opet, na osnovu interne funkcije pod kontrolom seeda)... onda liniju prelomim na n delova, (n zavisi od seeda (zar smo sumnjali)), sklopim redove jedan ispod drugog... i dobijemo gotovu sliku u bmp formatu koja naizgled ništa ne znači. :))


Batalio sam sve ovo jer mi nije neophodno, ali je simpatična (mada verovatno beskorisna) ideja koju ću da ostvarim ako ikada budem imao gomilu slobodnog vremena na bacanje. Znači nikad.

A u igrama ću se držati rnd funkcije jer mi se sviđa koliko je brza. Radio sam benchmark test i ispala je 10ak puta brža od prostih trigonometrijskih f-ja.
In a game of chess you must never let your opponent see your pieces - Zap
Brannigan
 
Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
*.yubc.net.



+27 Profil

icon Re: Generator slucajnih brojeva ?19.02.2005. u 17:14 - pre 232 meseci
Citat:
Dark Icarus:
Pa baš zato sam i pitao, jer sam jedno vreme razmišljao o pravljenju sopstvenog random sistema, u sklopu sa algoritmom za enkripciju, gde brzina same funkcije ne bi bila bitna.

Ako bi ipak nešto radio u tom pogledu, trebalo bi da pogledaš načine na koje se proveravaju karakteristike slučajnosti datog niza brojeva (ja se time nisam bavio). To što bi od semena do broja došao preko staza i bogaza ne mora obavezno da znači da će krajnja slučajnost biti na visokom nivou, nekakva šema može za čas da uleti :)

Citat:
A u igrama ću se držati rnd funkcije jer mi se sviđa koliko je brza. Radio sam benchmark test i ispala je 10ak puta brža od prostih trigonometrijskih f-ja.

Za računanje sledećeg slučajnog broja linearnom kongruentnom generatoru potrebno je samo po jedno množenje, sabiranje i deljenje, dok su „proste“ trigonometrijske funkcije u stvari vrlo zahtevne — moraju da daju rezultat tačan do na mašinsku preciznost, za šta je potreban veliki broj računskih operacija (računaju se preko Tejlorovih redova). Zato čak postoje posebne matematičke biblioteke kod kojih se može kontrolisati preciznost trigonometrijskih funkcija, kada maksimalna preciznost nije potrebna.
 
Odgovor na temu

Sundance

Član broj: 7510
Poruke: 2559
*.sava.sczg.hr.



Profil

icon Re: Generator slucajnih brojeva ?20.02.2005. u 00:00 - pre 232 meseci
Točno tako. Kompleksnost preslikavanja ne implicira uniformnost raspodjele rezultata. LCG-ovi su zasad brzi i efikasni, nemoj izmišljati toplu vodu :)

Inače, FPU modernijih proceva već odavno podržava fsin, fcos i sl. :>

Osim toga, win/.NET ima ugrađene APi-je i za generiranje kriptografski sigurnih slučajnih brojeva.
 
Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
*.sbb.co.yu.

ICQ: 282954730
Sajt: www.sietf.org


+7 Profil

icon Re: Generator slucajnih brojeva ?20.02.2005. u 00:18 - pre 232 meseci
Citat:
Inače, FPU modernijih proceva već odavno podržava fsin, fcos i sl. :>

Pa dobro, ali opet sve mora preko starog dobrog Tejlora, zar ne ? :)
ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪
 
Odgovor na temu

[es] :: Nauka :: Generator slucajnih brojeva ?

[ Pregleda: 13236 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.