[ filmil @ 27.01.2004. 16:27 ] @
Upravo mi je zatrebalo, pa ko velim da podelim s vama...

Napisati algoritam koji generiše slučajni vektor uniformno raspodeljen u
krugu poluprečnika 1. Hint: u pitanju je algoritam, vreme izvršavanja
mora biti predvidivo dugo.

f
[ Milos Stojanovic @ 27.01.2004. 17:50 ] @
Možeš li malo da pojasniš ? Verovatno ne razumem zadatak, ali čemu algoritam kada se ova raspodela računa lako iz formule slučajne promenljive neprekidnog tipa?
[ filmil @ 27.01.2004. 22:00 ] @
Citat:
kada se ova raspodela računa lako iz formule slučajne promenljive


Nisam rekao da je teško izračunati, već da mi je zatrebalo i da sam primetio da ovde odavno (ako uopšte!) nije bilo reči o generisanju raznih raspodela, pa sam samo isporučio pitanje. Ne može da šteti, a ako ne šteti, onda možda koristi.

Da pojasnim. Potreban je program koji generiše slučajni vektor (X,Y) čija je raspodela uniformna na krugu poluprečnika 1. Pritom su X i Y promenljive koje označavaju koordinate slučajno izabrane tačke u Dekartovom pravouglom koordinatnom sistemu.

f


[ -zombie- @ 28.01.2004. 05:34 ] @
ili ja ne razumem postavku, ili se ovo svodi na slučajno generisanje ugla vektora (između 0 i 2pi) i inteziteta (između 0 i 1) i računanje njegovih kordinata pomoću arctg-a.

koje je od ta dva? ;)


(ovo sve naravno pod pretpostavkom da nam je već na raspolaganju Rand() funkcija koja nam vraća slučajne realne brojeve uniformno raspoređene između 0 i 1 -- ili bar dovoljno dobra aproksimacija iste ;)
[ srki @ 28.01.2004. 06:02 ] @
Ali pretpostavi da nemas Rand() funkciju. Mislim da je na to mislio Filip. Filipe, ispravi me ako gresim. Ja imam nekoliko ideja ali necu da trcim pred rudu jer ne znam tacno sta se trazi u zadatku.
[ -zombie- @ 28.01.2004. 06:16 ] @
pa tek pod tom pretpostavkom nisam siguran da razumem postavku zadatka.

generisanje (pseudo)slučajnih (realnih) brojeva sa uniformnom raspodelom je poznat problem za koji je razrađeno već nekoliko (manje ili više) dovoljno dobrih rešenja, pa je na tu temu malo glupo raspravljati, osim ako se neko nije specifično bavio izučavanjem i istraživanjem u toj oblasti.

a ako je to poJenta cele priče, zar ne bi filip onda jednostavno rekao "hajde da raspravljamo o generisanju slučajnih brojeva", umesto što je priču zavio u problem sa vektorima (koji se lako svodi na to).
[ Reljam @ 28.01.2004. 06:52 ] @
Citat:
-zombie-:
ili ja ne razumem postavku, ili se ovo svodi na slučajno generisanje ugla vektora (između 0 i 2pi) i inteziteta (između 0 i 1) i računanje njegovih kordinata pomoću arctg-a.
Hm, to nece raditi - raspodela je neuniformna, ima suvise tacaka blizu 0,0.
Brute force resenje koje je mozda dovoljno dobro da se izgenerisu dve koordinate u opsegu (-1,1) i ukoliko padaju van kruga (x*x+y*y>1) da se ponovi postupak.
[ noviKorisnik @ 28.01.2004. 07:35 ] @
Citat:
Reljam:
...raspodela je neuniformna, ima suvise tacaka blizu 0,0.

Kakva je raspodela ako se korenuje dobijena vrednost intenziteta vektora?
[ filmil @ 28.01.2004. 08:51 ] @
Citat:
(ovo sve naravno pod pretpostavkom da nam je već na raspolaganju Rand() funkcija koja nam vraća slučajne realne brojeve uniformno raspoređene


Pretpostavi najpre da ti je data funkcija Rand() koja vraća pseudoslučajne brojeve sa uniformnom raspodelom na [0,1].

A kad to središ, pretpostavi da ti je data samo funkcija GausRand() koja vraća slučajnu promenljivu koja je raspodeljena prema standardnoj normalnoj raspodeli .

f




[Ovu poruku je menjao filmil dana 28.01.2004. u 11:05 GMT]
[ filmil @ 28.01.2004. 08:55 ] @
Citat:
Brute force resenje koje je mozda dovoljno dobro da se izgenerisu
dve koordinate u opsegu (-1,1)


Upravo sam zato rekao da se traži algoritam, što znači da mora
imati predvidljivo vreme izvršavanja. U ovom slučaju je vreme
izvršavanja slučajna promenljiva sa geometrijskom raspodelom ako se
generisanje broja uzme za jediničnu operaciju, jer se eksperiment
ponavlja sve do prvog uspeha.

f
[ srki @ 28.01.2004. 09:41 ] @
Citat:
Reljam:
Citat:
-zombie-:
ili ja ne razumem postavku, ili se ovo svodi na slučajno generisanje ugla vektora (između 0 i 2pi) i inteziteta (između 0 i 1) i računanje njegovih kordinata pomoću arctg-a.
Hm, to nece raditi - raspodela je neuniformna, ima suvise tacaka blizu 0,0.

Reljam, mislim da si malo vise razmiljao prakticno nego sto treba jer si u D3D vodama pa si onda gledao da taj vektor pretstavis sa x i y gde su x i y celi brojevi jer pretstavljaju pixele. Ali filmil to nigde nije pomenuo pa onda x i y isto mogu a budu float a onda ima maltene isto tacaka oko (0,0) kao i oko (0.1,0.1) jer broj tacaka zavisi od broja znacajnih cifara.
Ako imamo funkciju Rand() onda bih i ja uradio kao zombie. Filmile?

[Ovu poruku je menjao srki dana 28.01.2004. u 23:48 GMT]
[ Reljam @ 28.01.2004. 09:42 ] @
Pa i ima predvidivu duzinu izvrsavanja - naci ce uspesnu tacku u 3.14 / 4 slucaja, sto je 0.785. Prvi uspeh ce biti posle 1.27 pokusaja, sto je dovoljno dobro. Vrlo je verovatno da ce neki pametniji algoritam duze da se izvrsava od ovoga - jednostavnost ima svojih vrlina :).
[ srki @ 28.01.2004. 09:50 ] @
Ali problem sa tim je sto to nije uniformna raspodela vektora. U stvari mozda i jeste ali problem je u tome kako je definisan vektor. Da li preko duzine i ugla ili preko dve tacke.
[ Reljam @ 28.01.2004. 09:58 ] @
Raspodela je uniformna koliko i generator koji se koristi, a svejedno je kako se vektor definise - uvek mozes da prebacis iz jednog sistema u drugi.

A da odgovorim na tvoju poruku od malopre: ako koristis zombijev metod (ugao=rand, r=rand), bez obzira da li su brojevi fp ili int, imaces vise tacka oko 0. Ako bi nacrtao te tacke, dobio bi koncentricne krugove i radijalne linije. Broj jednih i drugih zavisi od broja bitova u slucajnom broju.

Ako koristis moju metodu (x=rand(-1,1), y=rand(-1,1), provera), dobices resetku cija gustina zavisi od broja bitova u slucajnom broju ali ce raspodela biti uniformna. Zbog toga i mislim da je to bolje resenje.
[ jablan @ 28.01.2004. 10:12 ] @
Citat:

Upravo sam zato rekao da se tra�i /algoritam/, �to zna�i da mora
imati predvidljivo vreme izvr�avanja. U ovom slu�aju je vreme
izvr�avanja slu�ajna promenljiva sa geometrijskom raspodelom ako se
generisanje broja uzme za jedini�nu operaciju, jer se eksperiment
ponavlja sve do prvog uspeha.


Hmm, možda može da se nađe neko "mapiranje" ostatka kvadrata na krug, to
jest da se umesto ponovnog generisanja izvrši neka funkcija nad koordinatama
koje ispadaju tako da upadnu, naravno uniformno?

A, ako i ne može da se nađe takva funkcija, možda možeš da dobiješ dovoljno dobar kompromis tako što ponavljaš generisanje maksimalno n puta (umesto beskonačno), a ako ni posle n-tog puta ne dobiješ tačku koja upada u krug, uradiš neko neuniformno mapiranje. Programersko rešenje.


[Ovu poruku je menjao jablan dana 28.01.2004. u 12:20 GMT]
[ srki @ 28.01.2004. 10:18 ] @
Citat:
Reljam:
Raspodela je uniformna koliko i generator koji se koristi, a svejedno je kako se vektor definise - uvek mozes da prebacis iz jednog sistema u drugi.

Nije svejedno. Ako definises vektor kao sto si ti definisao tako ces imati manje vektora ciji je vrh udaljen 0,5 ili manje od koordinatnog pocetka nego vektora ciji je vrh udaljen 0,5 i vise od koordinatnog pocetka. Znaci bitno je kako se bira vektor.
[ Reljam @ 28.01.2004. 17:14 ] @
Srki, nisam te najbolje shvatio, da li mozes da razjasnis to sto si rekao? Stvarno mi se cini da bi na ovaj nacin raspodela bila uniformna, ali mozda gresim, zato molim te kazi na sta mislis.
[ -zombie- @ 28.01.2004. 20:12 ] @
hehe.. ipak ispade zanimljiv problemčić ;)

relja me je dobro ispravio, mada.. ja sam oko rešenja očigledno razmišljao više kao matematičar nego kao programer (što mi se nije odaavno desilo -- ja sam ipak primarno programer ;), pa sam zato dao ono rešenje. ono naime jeste matematički tačno. tj može se dokazati da u krugu postoji jednak broj tačaka čije je rastojanje do centra kruga manje od polovine poluprečnika, sa onima čije je rastojanje veće od te vrednosti.. :-P

(ako vas zanima ovaj paradox, pogledajte skorašnju raspravu u forumu matematika, valjda pod nazivom "još (malo) verovatnoće" ;)


no, ako razmislim kao praktičan programer znam da mi nemamo dovoljno dobru aproximaciju neprekidnog skupa realnih brojeva, pa ovakve pretpostavke otpadaju.

zato mi sad pade na pamet ovakvo rešenje: x dodelimo vrednost slučajno izabranog broja iz skupa [0, 1], a y vrednost kvadratnog korena slučajno izabranog broja iz skupa [0, 1-x2]. nisam sto posto siguran u ovo, tako da ću kasnije razmisliti još malo, da to i dokažem (ili opovrgnem), ali imam osećaj da rešenje nije loše.. ;)


(a možda bolja varijacija na ovo poslednje, da i x dodelimo vrednost kvadratnog korena broja slučajno izabranog iz skupa [0, 1]?)
[ srki @ 28.01.2004. 21:48 ] @
Problem je sto funkcija Rand() ne vraca uniformnu raspodelu nad diskretnim skupom nego racuna tako kao da je skup od 0 do 1 neprekidan jer bi inace vracala mnogo vise brojeva oko 0,0. Zato ne znam tacno na kakvu se unoformu raspodelu misli. Da li nad diskretnim skupom realnih brojeva ili neprekidnim?
[ Milos Stojanovic @ 29.01.2004. 00:37 ] @
Zar se onda ovo ne svodi na generisanje slučajnog broja između i , jer ovo možemo formulisati kao nalaženje realnog broja koji je u stvari tangens ugla izmedju vektora i x-ose
Citat:
Da li nad diskretnim skupom realnih brojeva ili neprekidnim

Koliko ja znam, kompjuterski je nemoguće napraviti model skupa neprekidnih realnih brojeva, tako da bismo morali da se zadovoljimo nekim diskretnim skupom.

Citat:
može se dokazati da u krugu postoji jednak broj tačaka čije je rastojanje do centra kruga manje od polovine poluprečnika, sa onima čije je rastojanje veće od te vrednosti

Pa da. I jednih i drugih ima beskonačno mnogo. :) Ne znam zašto od polovine poluprečnika. Može i od 1/10 :)
[ srki @ 29.01.2004. 02:08 ] @
Citat:
thetrooper:
Citat:
Da li nad diskretnim skupom realnih brojeva ili neprekidnim

Koliko ja znam, kompjuterski je nemoguće napraviti model skupa neprekidnih realnih brojeva, tako da bismo morali da se zadovoljimo nekim diskretnim skupom.

Ma jeste nemoguce ali mozes da gledas kao da je neprekidan pa da aproksimiras slucajnu vrednost na najblizu mogucu realnu koju racunar moze predstaviti. Da nije tako onda bi funkcija Rand() najvise vracala vrednosti oko broja 0.
[ leka @ 29.01.2004. 12:18 ] @
Sto se tice uniformnih generatora slucajnih brojeva i teorije u vezi
njih, priznajem da sam maltene totalno neupucen. Iako je primena RNG-a
veoma siroka, covek prosto nema vremena za sve.
No, s obzirom da na IRC-u cesto diskutujem sa pametnijim ljudima od
sebe, uvek nesto novo naucim. Tako sam jednom davno cuo za gospodina
Pierre L’Ecuyer-a (http://www.iro.umontreal.ca/~lecuyer) profesora na
Univerzitetu u Montreal-u. I procitao sam jedan clanak na ovu temu, a za
ovu priliku sam ga nasao (ubio sam se trazeci):
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf . Takodje
prilazem i C kod koji sam koristio u par navrata.
Code:

/* uniform [0,1] random number generator
developed by Pierre Lecuyer based on a clever
and tested combination of two linear congruential
sequences
*/

/*
s1 and s2 are the seeds (nonnegative integers)
*/

#include <math.h>

double uni()
{
static long s1 = 55555;
static long s2 = 99999;
static double factor = 1.0/2147483563.0;
register long k,z;

k= s1 /53668;
s1 =40014*(s1%53668)-k*12211;
if (s1 < 0) s1 += 2147483563;
k=s2/52774;
s2=40692*(s2%52774)-k*3791;
if (s2 < 0) s2 += 2147483399;

/*
z = abs(s1 ^ s2);
*/
z= (s1 - 2147483563) + s2;
if (z < 1) z += 2147483562;

return(((double)(z))*factor);
}


Filipe, mislim da je vrlo lako odrediti vreme izvrsavanja ove funkcije. :)
[ filmil @ 29.01.2004. 12:27 ] @
Izvanredno, ali nam još uvek treba generator uniformno raspodeljenih
pravouglih koordinata u krugu. Ti si dao početnu implementaciju
za uniformno raspodeljenu slučajnu promenljivu od 0 do 1.

f
[ chupcko @ 29.01.2004. 12:41 ] @
Gledam i cudim se, sta li je ovde problem :)

Pola njih prica o generisaju slucajne promenljive sa uniformnom raspodelom, a pola o nekim transformacijama :).

E sada koliko sam ja shvatio problem je u tome da se napravi uniformni generator tacaka unutar nekog kruga.
Da budemo jos malo precizni, jel tako da je doupsteno koristiti neku funkciju koja daje uniformnu raspodelu unutar segmenta [0,1]. Takooooooooo jeeeeeeeee.

E da je u pitanu kvadrat, odavno bi se to resilo lako, lepo x=rand(); y=rand(); radi posao, ali mi ne zelimo kvadrat, zelimo krug.

Neko bi rekao: pa ajde daj uniformno po kvadratu, pa ce i na nekovom njegovom podskupu biti isto uniformno, pa cemo da secemo ako je izvan kruga, e to nece ici, jer ljudi zele algoritam u konacno mnogo koraka, bez petlji, jer ako u petlji cekamo da tacka padne unutar kruga, to moze da se desi posle bas puno koraka (jelte, ne mozemo da garantujemo da ce to da se desi bas u prvih 10 koraka), neko kakve je srece moze da nikada ne doceka, nema veze sto je uniformna raspodela, ona je uniformna u beskonacnosti, a konacno je diskretna :)))).

Dobro, ajde ne mora tako, sto ne bi iskoristili polarni kordinatni sistem, neka jedna promenjljiva ide od 0 do 2pi, a druga od 0 do 1 dobili bi lepo definisane tacke unutar kruga, ali ovakva raspodela nije bas uniformna, ili jeste :). Naravno tu su sada pale rasprave oko diskretnosti i nediskretnosti. da li je matrica ovakva ili ovakva ...

Nekako deluje logicno da ovako dobijen skup tacaka nije u uniformnoj rapodeli, jer blizu (0,0) ima vise tacaka gustina :)))).

E sada ispada da problem nije bas tako trivijalan, treba naci neko genijalno mapiranje segmenta [0,1] ili pak prozivoda vise segmenata [0,1] na krug. Dakle ajde da vidimo neke peanove krive ili sta vec :).

Dakle nije problem dobiti jednu uniformnu promenljivu iz segmenta [0,1], pitanje je samo da li statisticki zadovoljava uniformnost i na malim uzorcima :), nego je problem bas to, unutar kruga ....
[ leka @ 29.01.2004. 12:56 ] @

Pitanje koje se naravno postavlja sada je - ako je generisanje jedne
koordinate uniformno, da li je generisanje dve koordinate takodje
uniformno. Ja se, kao sto rekoh, takvim stvarima ne bavim, ali verovatno
je odgovor - DA.
Citat:
Izvanredno, ali nam još uvek treba generator uniformno
raspodeljenih pravouglih koordinata u /krugu/. Ti si dao početnu
implementaciju za uniformno raspodeljenu slučajnu promenljivu od 0 do
1.


Sto se tice onog koda gore, ja bih tu jos dodao racunanje ona dva seed-a
na osnovu UNIX timestamp-a ili neceg slicnog...

Pozdrav
[ srki @ 29.01.2004. 13:19 ] @
Citat:
filmil:
Izvanredno, ali nam još uvek treba generator uniformno raspodeljenih
pravouglih koordinata u krugu.

Znaci mi samo biramo tacku u krugu a verovatnoca da se nadje u nekom delu zavisi od povrsine tog dela, je l' tako?
Ok, ako je tako onda je lako.
Definisemo R kao rastojanje od (0,0) i Fi kao fil...kao ugao.
Ako su X i Y slucajne promenjive sa unoformnom raspodelom u [0,1] onda je R=sqrt(X) a Fi=2*Pi*Y

Dalje je lako izracunati koordinate.
[ filmil @ 29.01.2004. 13:30 ] @
Citat:
Dalje je lako izracunati koordinate.


Još samo kad bismo saznali i zašto je baš tako...

f

[ srki @ 29.01.2004. 14:06 ] @
Neka je F(r) funkcija raspodele promenljive R. Lako je videti da je
F(r)=0 za r<0
F(r)=r^2 za 0<r<1
F(r)=1 za r>=1
jer je funkcija raspodele F(r) u stvari verovatnoca da se promenljiva R bude izmedju 0 i r (tacnije -beskonacno do r). A ta verovatnoca je proporcionalna povrsini i zato imamo r^2 u drugom slucaju.

Dalje, poznata stvar iz verovatnoce je da ako imamo neku uniformnu pormenljivu X na intervalu [0,1] i neku promenljivu R sa funkcijom raspodele F(r) onda mozemo R izabrati kao invF(X).
Znaci dovoljno je generisati X i pomocu inverzne funkcije naci R.

Ako vam treba dokaz za ovo napisacu ali me mrzi sada da razmisljam. Mada cini mi se da sam prvi put to naucio dok sam bio na ETF-u iz knjige iz verovatnoce od Merklea, pa verovatno tu ima dokaz. Nisam siguran ali cini mi se da sam tu to prvi put video.