[ARHIIV] mängumeistrid
Pole sisse logitud. [Logi sisse ]
Mine lehekülje algusesse
Prinditav versioon | Telli teema e-mailile | Lisa lemmikutesse  
π statistiline arvutus.
h0lx
Kohalik sitapea
Avatar

Liitunud: 10.4.2006
Postitusi: 1826
[EEMAL]




postitati 19.10.2009 20:12 Tsiteeri
π statistiline arvutus.



Täna tuli isu midagi programmeerida, arutasin oma soovi sõbraga, tahtsin midagi CPU intensiivset progreda, ise kritseldasin loengus algoritmi, mis arvutaks piid piirväärtuse

kaudu, sõber aga rääkis mulle Monte Carlo meetodist. Koju jõudes oli mul algoritm välja mõeldud, kodus paberil optimeerisin ja asusin kirjutama. See on ka ideaalne moodus oma

arvuti jõudluse testimiseks.

Monte Carlo meetod:

http://img207.imageshack.us/img207/8006/mcp1.gif

Võtame ruudu, milles on ka siseringjoon, nende kujundite pindalade suhe on:
Kood:

(pi*r^2)/(2r)^2 => pi*r^2/4r^2 => pi/4


Seega, kui ühtlase tihedusega panna suvalisi punkte ruudu peale, siis statistiliselt:
Kood:

rp - punktide arv, mis on ringi sees
kp - kogu punktide arv

4*rp/kp=~pi


Algoritm:
Võtame ruudu küle pikkuseks 2 ühikut, seega on ringi raadius 1. Sellest järeldub, et kui punkt on ringi keskpunktile lähemal, kui 1 ühik, asub ta ringi sees. Seega:
http://www.purplemath.com/modules/xyplane/dist07b.gif<1
Astendame mõlemaid võrratuse pooli 2ga, saame:
Kood:

(x1-x2)^2+(y1-y2)^2<1

Võtame ringi keskpunktiks (0;0), seega kaugus keskpunktist oleks:
Kood:

x^2+y^2<1


*Siinkohal märgin ära, et ringjoone võrrand on:

Kood:

x^2+y^2=r


Seega jääb üle lihtsalt tekitada punkte, mille koordinaadid jäävad lõigule [-1;1] ja vaadata, kas nende punktide koordinaatide summa on mitterangelt väiksem, kui 1. Nende

punktide arvu jagades kogupunktide arvuga ja korrutades neljaga saame ligikaudse pii väärtuse.

Programm:
Programmi lisasin manusena, kaasas on ka lähtekood. Programmi parameetriteks on 10 astendaja, mitu punkti asetatakse ruudule ja mitme iteratsiooni tagant staatus väljastatakse.

Kaasasolevat bat faili jooksutades arvutatakse miljardi punktiga ja iga miljoni iteratsiooni järel väljastatakse staatus. Huvitav oleks teada, kui kaua erinevate masinate peal

selleks aega kulus. Minu Intel i5 750 peal, 2.67 GHz juures kulub sellise arvutuse jaoks 49 sekundit, kasutades selleks ainult üht tuuma.

Mis edasi?
Planeerin teha multithreadingu suppordi, samuti kavatsen suurendada võimalike iteratsioonide arvu ja jagatise täpsust.

--

Changelog:
1.0 - Algne release
1.1 - Viskasin iostreami kõrvale, kasutasin hoopis cstdiod, võitsin selle ja -s flagiga meeletult suuruses, exe faili suurus on nüüd 6kb(enne oli ca 500)

Lisatud fail: MCP.rar (3.5kb)
74 korda tõmmatud
Platform II: -DMI-; H0lx&jorssJõulumäng I: h0lx&jorss
Vaata kasutaja profiili Otsi kasutaja postitusi Saada privaatsõnum
simmo
Level 10
Avatar

Liitunud: 6.1.2006
Postitusi: 720
[EEMAL]




postitati 20.10.2009 14:12 Tsiteeri


Sain 75 sekundit. Endal peaks olema Intel Core 2 Quad 2.66 GHz.

Vaata kasutaja profiili Saada kasutajale e-mail Külasta kasutaja kodulehte Otsi kasutaja postitusi Saada privaatsõnum Vaata kasutaja MSN-i
Peeter
Level 9
Avatar

Liitunud: 17.7.2006
Postitusi: 607
[EEMAL]




postitati 20.10.2009 21:22 Tsiteeri


Intel Pentium Dual Core E5200, 250GHz.

74 sekundit.
Strateegia II: Peeter ja rallitajaRPG III: Peeter<br>Jõulu 2008 II: PeeterEmo3: emoemo<br>Aktsioon I (2009): PeeterVabateema I: veka&pets
Vaata kasutaja profiili Saada kasutajale e-mail Külasta kasutaja kodulehte Otsi kasutaja postitusi Saada privaatsõnum Vaata kasutaja MSN-i
valter
1


Liitunud: 19.1.2005
Postitusi: 1553
[EEMAL]




postitati 20.10.2009 21:59 Tsiteeri


99s (39 protsessi lahti) Intel Core 2CPU 1.8GHZ, GForce 7300SE
http://www.dmgamez.pri.ee/GRONGO1/uss_walk.gif
Ralli I: dm11Veresaun III: dm11<br>Emo1: icedude, valter8bit I: võistlus kestabAktsioon III (2009): -<br>Aasta mäng 2009: Pilvemees, valter<br>Vabateema II: valter
Vaata kasutaja profiili Külasta kasutaja kodulehte Otsi kasutaja postitusi Saada privaatsõnum
icedude
Mr. tl;dr
Avatar

Liitunud: 15.12.2008
Postitusi: 456
[EEMAL]




postitati 21.10.2009 10:13 Tsiteeri


ma vaatan sul on seal ruutjuur ka. Ma loodan, et sa ei kasuta arvuti enda ruutjuurt. Tee ise ruutjuure võrrand. Kasuta seda mida kasutati quake mootoris, ja sa saad kõik ruutjuure võrrandid 2x kiiremaks. Kui ise seda tööle ei saa või netist ei leia siis ma otsin arvutist ülesse ja postitan. Aga kui leiad ülesse siis kasuta double mitte float konstanti. Doublega on täpsem. Mul endal on float.iga see kiire ruutjuure algoritm, et siis kui ma sellega mässasin siis ma ei jaganud matsu välja selle algoritmi tähtsust double konstandiga ja enam pole seda otsinud ka tegelt. Float ajab asja ilusti ära...aga kui sama kiirusega saab täpsemalt siis...double on päris ahvatlev. Tegelt quake mootoris kasutati pöörd ruutjuure võrrandit normaalide leidmiseks, aga sama asi on ka lihtsalt ruutjure leidmiseks. Ma ise kasutan, ja minu masinapeal ainult ruutjuure arvutmaise test 2x kiirem. (Dualcore 1,8ghz).
Emo1: icedude, valter8bit III: võistlus kestab<br>
Vaata kasutaja profiili Saada kasutajale e-mail Otsi kasutaja postitusi Saada privaatsõnum
h0lx
Kohalik sitapea
Avatar

Liitunud: 10.4.2006
Postitusi: 1826
[EEMAL]




postitati 21.10.2009 14:45 Tsiteeri


Sa, icedude, üldse lugesid teksti läbi ja sourcet vaatasid?
Platform II: -DMI-; H0lx&jorssJõulumäng I: h0lx&jorss
Vaata kasutaja profiili Otsi kasutaja postitusi Saada privaatsõnum
Caupo
Caupo
Avatar

Liitunud: 19.7.2007
Postitusi: 1544
[EEMAL]




postitati 21.10.2009 15:42 Tsiteeri


2.0 Ghz Celeron - 255 sekundit

Peeter - Blood Money --- Delayed during tragic technical issues!
Kaklusmäng II: RallitajaStrateegia II: Peeter ja rallitajaRPG II: RallitajaJõulu 2008 I: Rallitaja8bit II: võistlus kestabAktsioon II (2009): Rallitaja
Vaata kasutaja profiili Saada kasutajale e-mail Külasta kasutaja kodulehte Otsi kasutaja postitusi Saada privaatsõnum Vaata kasutaja MSN-i
-Limus.-
3 varikontot!


Liitunud: 14.5.2009
Postitusi: 52
[EEMAL]




postitati 21.10.2009 17:30 Tsiteeri


94 sekundit amd mx2

Vaata kasutaja profiili Saada kasutajale e-mail Otsi kasutaja postitusi Saada privaatsõnum Vaata kasutaja MSN-i
h0lx
Kohalik sitapea
Avatar

Liitunud: 10.4.2006
Postitusi: 1826
[EEMAL]




postitati 28.10.2009 23:31 Tsiteeri


Uus versioon - 1.1
Platform II: -DMI-; H0lx&jorssJõulumäng I: h0lx&jorss
Vaata kasutaja profiili Otsi kasutaja postitusi Saada privaatsõnum
icedude
Mr. tl;dr
Avatar

Liitunud: 15.12.2008
Postitusi: 456
[EEMAL]




postitati 29.10.2009 09:38 Tsiteeri


Tsitaat:
Tsitaat: h0lx
Sa, icedude, üldse lugesid teksti läbi ja sourcet vaatasid?


LOL, my bad. Kui ma nüüd tagantjärgi vaatan siis mitte eriti hoolikalt:D. Aniway...ju mul oli siis järelikult jube suur tahtmine midagi kirjutada...pointless või pointful.
Emo1: icedude, valter8bit III: võistlus kestab<br>
Vaata kasutaja profiili Saada kasutajale e-mail Otsi kasutaja postitusi Saada privaatsõnum
Peeter
Level 9
Avatar

Liitunud: 17.7.2006
Postitusi: 607
[EEMAL]




postitati 29.10.2009 11:52 Tsiteeri


Pentium III, 996 MHz
255.
Strateegia II: Peeter ja rallitajaRPG III: Peeter<br>Jõulu 2008 II: PeeterEmo3: emoemo<br>Aktsioon I (2009): PeeterVabateema I: veka&pets
Vaata kasutaja profiili Saada kasutajale e-mail Külasta kasutaja kodulehte Otsi kasutaja postitusi Saada privaatsõnum Vaata kasutaja MSN-i
Crypton

Avatar

Liitunud: 18.12.2005
Postitusi: 1604
[EEMAL]




postitati 29.10.2009 18:46 Tsiteeri


Ma jäin postis olevat koodi vaatama.

Mulle justkui tunduks et
http://img194.imageshack.us/img194/6008/mcp2.gif
võrratuse astendamisel (ruutu võtmisel) mõlemad pooled, ei võrduks:
(x1-x2)^2+(y1-y2)^2<1
vaid hoopis
(x1^2 - x2^2) + (y1^2 - y2^2) < 1
(ning x1 pole mitte 1*x vaid x indeksiga 1)

Või olen midagi märkamata jätnud.

Anyway, mul tegi seda üsna kaua. Prose ei läinud üle 800 MHz. (kasutan AMD Phenom II 3,2 GHz, millel on see Cool 'n' Quiet peal - ühesõnaga väga see mu prose ei koormanudki just...)

Maze I: CryptonRalli III: Crypton<br>
Vaata kasutaja profiili Külasta kasutaja kodulehte Otsi kasutaja postitusi Saada privaatsõnum
h0lx
Kohalik sitapea
Avatar

Liitunud: 10.4.2006
Postitusi: 1826
[EEMAL]




postitati 29.10.2009 18:54 Tsiteeri


Denderil on tuline õigus, aga viga on hoopis minu joonistatud valemis, peaks olema hoopis nii:
http://www.purplemath.com/modules/xyplane/dist07b.gif
Tõenäoliselt tuli viga õhtul väsinud peaga teksti koostades ja pilti joonistades, kuna sellest edasi on kõik nii nagu peab, millest eeldan, et mu esialgsed arvutused olid korrektsed.(mida kinnitab ka tulemuse suhteliselt suur täpsus)
Platform II: -DMI-; H0lx&jorssJõulumäng I: h0lx&jorss
Vaata kasutaja profiili Otsi kasutaja postitusi Saada privaatsõnum
Crypton

Avatar

Liitunud: 18.12.2005
Postitusi: 1604
[EEMAL]




postitati 29.10.2009 19:54 Tsiteeri


mm, ja jaa, see samune d - punkti kaugus. :)
nuh siis on hea, kui ainult joonises viga, peaasi et programmis asi tõene oleks.

Ma arvan et ma kasutan seda materjali veel uurimiseks, kuna mind hirmsasti huvitab kuidas neid samu matemaatilisi võrdusi reaalselt programmides kasutada. Näituseks erinevaid sirgevõrrandeid/võrratusi/funktsioone jms.

On selline päris hea kokkuvõtlik materjal, millega alustada (y).

Maze I: CryptonRalli III: Crypton<br>
Vaata kasutaja profiili Külasta kasutaja kodulehte Otsi kasutaja postitusi Saada privaatsõnum
Kazpar
$ QliMax $
Avatar

Liitunud: 27.3.2009
Postitusi: 507
[EEMAL]




postitati 29.10.2009 20:17 Tsiteeri


45 sec.
Intel Core 2 Duo E8400 (3,0GHz, 6MB)
Vabateema II: valter
Vaata kasutaja profiili Otsi kasutaja postitusi Saada privaatsõnum
timoolen
Level 3
Avatar

Liitunud: 22.12.2007
Postitusi: 58
[EEMAL]




postitati 11.11.2009 18:00 Tsiteeri


75 sek
Intel Dual E2200 2,2ghz

Kahju et teist tuuma ei kasuta, tuleks aeg ~poole väiksem

Vaata kasutaja profiili Otsi kasutaja postitusi Saada privaatsõnum Vaata kasutaja MSN-i

Hetkel loevad seda teemat:
Mitte ühtegi - 1 külaline

Mine lehekülje lõppu





Foorumi algbaas põhineb XMB mootoril, modifitseeritud Valter Pundi poolt
Kodulehekülg on tehtud Valter Pundi poolt vpundi ät gmail punkt komm