WebSupport.sk
UnlimitedHosting
|
CustomHosting
|
FreeWeb.sk
Takze dnes sa Vam pokusim rozpisat, ako si vypocitat Ludolfovo cislo za pomoci bashu a nahodnych cisel. Pri robeni toho kratkeho skriptu som sa nesmierne zabavil a vysledok ma dokonca aj prekvapil (odchylka od realneho pi je vacsinou mensia, ako 2%, ale o tom potom).
Na vypocet je potrebne ovladat princip Monte Carlovej metody, ktoru teraz troska detailnejsie opisem.
Predstavte si dokonaly stvorec a v nom vpisanu kruznicu. Tento utvar si rozdelime na kvadranty a budeme pracovat iba s jednym. Ak ste si to predstavili spravne, vyslo Vam nieco taketo :
celkova plocha
kvadrant:
A ideme na dalsie predstavovanie (fakt uz posledne slubujem) Predstavte si , ze ten kvadrant je terc. A vy do neho hadzete sipky (berieme v uvahu predpoklad, ze vzdy trafite aspon terc (teda cely kvadrant).
Nasleduje matematika
obsah modrej casti : 1/4*π*r^2 (teda obsah stvrtiny kruhu)
obsah celeho kvadrantu = r^2 (teda obsah kocky)
Teda ak vydelim obsah modrej casti a obsah celeho kvadrantu, tak mi vyjde 1/4*π
Uz Vam je asi jasne, kam to smeruje, ale aj tak to dokoncim :) . Takze stale hadzeme sipky a pocitame : 4*(Sipky, ktore trafili modru cast/celkovy pocet hodenych sipok ) = π.
Pricom cim viac hodenych sipok, tym presnejsi vysledok. Ale komu by sa chcelo hadzat sipky?
A presne na toto mame bash (alebo akykolvek iny programovaci jazyk), kde si urobime simulaciu hadzania sipok.
Takze nasleduje zdrojovy kod pre bash s commentami, takze by malo byt jasne, co sa kde robilo.
#!/bin/bash
#premenne
clear
strely_max=100000 #pocet hodeni na terc
velkost=10000 #velkost kvadrantu
nasobok=4
declare -r REAL_PI=3.141592654 #realne pi na 9 desatinnych miest
#nahodny generator cisel
generator ()
{
NAHODA=$(head -n 1 /dev/urandom | od -N 1 | awk '{print $2}')
RANDOM=$NAHODA
let "nahcis = $RANDOM % $velkost" #aby mi nahodne cislo neprekrocilo velkost kvadrantu
echo $nahcis
}
#vypocet prepony (pytagorova veta)
vypocet ()
{
prepona=`echo "sqrt ( $1 * $1 + $2 * $2 )"|bc`
}
#mensie premenne
strely=0 #aktualny pocet striel
terc=0 #pocet trafenych v terci
Pi=0
error=0 #na vypocet odchylky
#hlavny cyklus
while [ $strely -le $strely_max ] #teda program bude behat pokial sa nevystrielaju vsetky sipky
do
x=$(generator) #priradi x nahodne cislo
y=$(generator) #priradi y nahodne cislo
vypocet $x $y #a vypocita preponu
((strely++))
if [ $prepona -le $velkost ] #zhodnoti ci sipka trafila modru cast alebo nie
then
echo -n "TERC "
((terc++))
else
echo -n "VEDLA"
fi
pi=$(echo "scale=9; ($nasobok*$terc/$strely) " | bc) #pocita pi s presnostou 9 desatinnych
error=$(echo "scale=9; $pi - $REAL_PI" | bc) #pocita odchylku ciselne (ale nevypisuje)
pct_error=$(echo "scale=2; 100.0 * $error / $REAL_PI" | bc) #prepocita to na percenta
echo -n " Pi ~ $pi"
echo -n " pokus cislo $strely"
echo -n " v percentach ($pct_error% error)" #a vypise
echo
done
Zaujimave je, ze na domacom laptope mi to pocita s <2% odchylkou a v robote mi to pocita s odchylkou ~4%. Asi ma fedora a gentoo iny /dev/urandom (kidding) :) .
Cim viac sipiek sa hodi, tym vacsia je presnost . Niekde medzi 50-100tisic mi ho uz generovalo s presnostou na 3 desatinne miesta (teda ~0,1% odchylka).
Takze dufam, ze ste to pokladali za nieco aspon trocha zaujimave, je to moj prvy prispevok na blackhole, takze bear with me :)
<sixeR> KURVA
<sixeR> zaspal som na posteli, zaspal
<sixeR> a zobudil som sa tak, ze pod sebou vidim kaluz krvi, nadomnou otec
<sixeR> a rozjebay xicht
<kab-el> ??
<kab-el> ti rozbil ksicht ked zistil, ze si buzerant?
<sixeR> kabel ty kokot :D
<sixeR> ja tu mam ohrozenie zivota 3000, strata krvi
<sixeR> lahky otras mozgu pomaly
|
webhosting by:
WebSupport.sk
|
UnlimitedHosting | CustomHosting | FreeWeb.sk |
Comments
Re: Vypocitajme si Pi pomocou nahodnych cisel
hmm... hned som si povedal, ze ten nick je mi nejaky znamy :D... Inak pekny clanok Lasperic to treba uznat. Skoda, ze nemam linux, teda program nemozem otestovat, ale zakladnu ideu som pochopil. Je sice pravda, ze na presnejsi vypocet by sa dali prejst jednotlive casti kvadrantu zaradom ale tento priklad sluzi skor na ukazku metody Monte Carlo ako na vypocet cisla PI. Dalo by sa povedat, ze metoda Monte Carlo je akysi kompromis medzi presnostou vysledku a dlhym casom vypoctu.
Mozno skusim aj ja v buducnosti napisat nejaky zaujimavy clanok, akurat mam "rozpracovany" jeden projekt :D
Re: Vypocitajme si Pi pomocou nahodnych cisel
Ak si to chces vyskusat, staci ti aj CygWin - emulator konzoly pre windows...
Resp. LiveCD linuxu ;)
--
The best way to predict future is to invent it...
Re: Vypocitajme si Pi pomocou nahodnych cisel
Obyčajne ma odrádzajú príspevky písané štýlom "Takze dnes sa Vam pokusim rozpisat", "A ideme na dalsie predstavovanie (fakt uz posledne slubujem)", ale keďže dnes sa jedná o konštantu π, ktorej numerický výpočet som mierne študoval, prečítal som si to a vyjadrujem sa k téme:
Máš diskrétnu plochu (pri výpočte používaš plochu s konečným počtom nedeliteľných elementov - kvadrant má R*R bodov), šípky sa môžu trafiť iba do R*R možných miest. Preto ak prejdeš všetky tieto body, dostaneš najpresnejši výsledok. Akýkoľvek väčší počet ti tvoj výsledok viac neupresní, pretože sa s bodmi iba opakuješ. Najrýchlejšie dostaneš výsledok s touto presnosťou, keď prejdeš všetky tieto body zaradom.
Náhodné určovanie bodov by mohlo byť viac efektívne v spojitom priestore, ale aj tam si myslím, že pravdepodobnosť najväčšej presnosti výsledku by bola najväčšia, keby si jednotlivé časti kvadrantu prešiel zaradom.
Re: Vypocitajme si Pi pomocou nahodnych cisel
To ze plocha je diskretna by ani nevadilo - vsetko v pocitaci je diskretne napokon a da sa hovorit len ze 'nejake cislo pozname s nejakou presnostou'.
K tejto metode je ovsem nutne povedat to, co sa dozviete aj na zakladnej prednaske k pravdepodobnosti a statistike - ze naroky na pocet pokusov kvadraticky stupaju s pozadovanou presnostou.
Presnejsie: majme nahodnu velicinu X, ktora nadobuda hodnoty 1(trafim sa do stvrtkruhu) a 0 (netrafim), so strednou hodnotou m, ktora nejak suvisi s pi. Potom odhad strednej hodnoty m` je nahodna velicina s normalnym rozdelenim so strednou hodnotou m a rozptylom nepriamo umernym odmocnine z n.
Cize 100 krat viac pokusov zmensi rozptyl odhadu (a teda nepresnost) len 10 krat a teda na dosiahnutie nejakej slusnej presnosti je tato metoda nevhodna. (v pripadne nepresnosti ma opravte)
Ale inak je to samozrejme celkom zaujimave ;)
Re: Vypocitajme si Pi pomocou nahodnych cisel
Na prvy odstavec ti asi len napisem , ze je to urcity osobity styl vyjadrovania sa a viem ze nie je kazdemu po voli , pokusim sa koncept dalsieho prispevku upravit aby bol viac vseobecny a vyhovoval mozno viacerim jedincom.
K aktualnej teme , ano som si vedomy ze ak by som zobral vsetky body zaradom tak by mi vyslo najpresnejsie pi (teda dokonca realne pi ak sa nemylim), ale mna najviac zaujala moznost vypoctu zapomoci nahodnych cisel preto som to zobral touto cestou.
A nakoniec k vyjadreniu ze presnost nestupa s poctom striel, no mozno som sa zle vyjadril a tak to bolo trocha zavadzajuce, ale myslel som to viac tak ze cim viac striel je , tym sa vysledok ustabilnuje. Teda napriklad pri hode 1-500 sa ti percentualna odchylka pohybuje v rozmedzi ~x+-10% kdezto pri hode 50000-10000 sa ti odchylka ustaluje na tom x (je jedno o kolko sa x rozlisuje od pi) a vychyluje sa od toho x na +-0,1%. (aj ked pri tychto vyssich cislach som dostaval celkom slusnu podobnost s pi , ale mozno to bola len nahoda).
Ale inak dakujem za konstruktivnu kritiku.
Re: Vypocitajme si Pi pomocou nahodnych cisel
teda dokonca realne pi ak sa nemylim
tak to sa teda mylis, sam si napisal, ze vysledok je 4*(Sipky, ktore trafili modru cast/celkovy pocet hodenych sipok ), teda racionalne cislo. ;-)
==
Things are rarely just crazy enough to work, but they're frequently just crazy enough to fail hilariously.
Re: Vypocitajme si Pi pomocou nahodnych cisel
uhm .. Jo mas pravdu to vyjde racionalne cislo. Tak som sa zmylil .. kto si to ma v hlave prepocitavat v piatok nadranom? ;-)
Re: Vypocitajme si Pi pomocou nahodnych cisel
Viem, ze pretieklo vela vody od kedy bol tento clanok napisany, no neda mi nevyjadrit sa k nemu.
Princip metody je v celku zaujimavy a s chutou som si to precital.
K implementacii, nvm ci bolo najstastnejsie nieco taketo programovat v bash-i.
V otazke presnosti tu hrajú podla mna dva faktory. Prvým je presnost desatinnych cisel, ktora udava strop presnosti vypoctu (Pri float32 je korektnych mozno 7-8 desatinnych miest). Ďalším faktorom moze byt nedokonalosť pseudo generatora nahodnych cisel (o tom sa tu dost popisalo pri teme o oklamani kasin, nebudem rozoberat). Ale v celku sa mi clanok pacil, a tento princip pri kodeni nejakeho benchmarku mozno aj vyuzijem.
Re: Vypocitajme si Pi pomocou nahodnych cisel
V prvom rade som rad ze sa ti clanok pacil :) k tomu bashu , mozno to nebola najstastnejsia ale skor mi islo o princip (aj ked funkcnost nebola az tak zla) asi to skusim v perle a porovnam vysledky mozno to prekvapi :)