abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 16:38 | Komunita

Byly zveřejněny videozáznamy přednášek a workshopů z letošní konference OpenAlt konané 5. a 6. listopadu v Brně. K videozáznamům lze přistupovat ze stránky na SuperLectures nebo přes program konference, detaily o vybrané přednášce nebo workshopu a dále kliknutím na ikonku filmového pásu. Celkově bylo zpracováno 65 hodin z 89 přednášek a workshopů.

Ladislav Hagara | Komentářů: 0
dnes 11:30 | Komunita

Bylo oznámeno, že bude proveden bezpečnostní audit zdrojových kódů open source softwaru pro implementaci virtuálních privátních sítí OpenVPN. Audit provede Matthew D. Green (blog), uznávaný kryptolog a profesor na Univerzitě Johnse Hopkinse. Auditována bude verze 2.4 (aktuálně RC 1, stabilní verze je 2.3.14). Audit bude financován společností Private Internet Access [reddit].

Ladislav Hagara | Komentářů: 2
dnes 06:00 | Komunita

Na YouTube byl publikován Blender Institute Reel 2016, ani ne dvouminutový sestřih z filmů, které vznikly za posledních 10 let díky Blender Institutu. V institutu aktuálně pracují na novém filmu Agent 327. Dění kolem filmu lze sledovat na Blender Cloudu. Videoukázka Agenta 327 z června letošního roku na YouTube.

Ladislav Hagara | Komentářů: 0
dnes 01:02 | Zajímavý článek

Minulý týden byly vydány verze 1.2.3 a 1.1.7 webového poštovního klienta Roundcube. V oznámení o vydání bylo zmíněno řešení bezpečnostního problému nalezeného společností RIPS a souvisejícího s voláním funkce mail() v PHP. Tento týden byly zveřejněny podrobnosti. Útočník mohl pomocí speciálně připraveného emailu spustit na serveru libovolný příkaz. Stejně, jak je popsáno v článku Exploit PHP’s mail() to get remote code execution z roku 2014.

Ladislav Hagara | Komentářů: 1
včera 16:00 | Nová verze

Byla vydána verze 0.98 svobodného nelineárního video editoru Pitivi. Z novinek lze zmínit například přizpůsobitelné klávesové zkratky. Videoukázka práce s nejnovější verzí Pitivi na YouTube.

Ladislav Hagara | Komentářů: 1
včera 15:00 | Zajímavý software

Stop motion je technika animace, při níž je reálný objekt mezi jednotlivými snímky ručně upravován a posouván o malé úseky, tak aby po spojení vyvolala animace dojem spojitosti. Jaký software lze pro stop motion použít na Linuxu? Článek na OMG! Ubuntu! představuje Heron Animation. Ten bohužel podporuje pouze webové kamery. Podpora digitálních zrcadlovek je začleněna například v programu qStopMotion.

Ladislav Hagara | Komentářů: 5
7.12. 21:21 | Nová verze Ladislav Hagara | Komentářů: 0
7.12. 11:44 | Zajímavý projekt

Na Indiegogo byla spuštěna kampaň na podporu herní mini konzole a multimediálního centra RetroEngine Sigma od Doyodo. Předobjednat ji lze již od 49 dolarů. Požadovaná částka 20 000 dolarů byla překonána již 6 krát. Majitelé mini konzole si budou moci zahrát hry pro Atari VCS 2600, Sega Genesis nebo NES. Předinstalováno bude multimediální centrum Kodi.

Ladislav Hagara | Komentářů: 2
7.12. 00:10 | Nová verze

Byla vydána verze 4.7 redakčního systému WordPress. Kódové označením Vaughan bylo vybráno na počest americké jazzové zpěvačky Sarah "Sassy" Vaughan. Z novinek lze zmínit například novou výchozí šablonu Twenty Seventeen, náhledy pdf souborů nebo WordPress REST API.

Ladislav Hagara | Komentářů: 10
6.12. 12:00 | Zajímavý projekt

Projekt Termbox umožňuje vyzkoušet si linuxové distribuce Ubuntu, Debian, Fedora, CentOS a Arch Linux ve webovém prohlížeči. Řešení je postaveno na projektu HyperContainer. Podrobnosti v často kladených dotazech (FAQ). Zdrojové kódy jsou k dispozici na GitHubu [reddit].

Ladislav Hagara | Komentářů: 27
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 805 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.

31.3.2014 20:04 gld17 | skóre: 4 | blog: GLDiuv_blog
C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Přečteno: 677×
Zdravim,

chtel bych se zeptat, zda-li nevite o nejake knihovne, ktera by pocitala sqrt treba s presnosti jen na tri desetinna mista (slo by to napsat ale chci optimalizovanou), potreboval bych udelat takovou jednoduchou analyzu obrazu ktera se bude delat na Raspberry Pi (bude slouzit pro pristani koptery do doku) a premyslim jak to udelat co nejmin narocne aby to vubec stacilo.

Je to moje diplomka a pouzit jen priblizne hodnoty sqrt mi prijde jako dost dobry napad ktery by usetril dost casu, protoze stejne bych vetsi presnost nevyuzil (math.h vraci normalne double).

Jinak bych si asi zkusil napsat sam nejaky assemblerovsky kod na to, cimz bych urcite zapusobil na porotu :D

Řešení dotazu:


Odpovědi

Josef Kufner avatar 31.3.2014 21:10 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Podíval jsi se profilerem, že to drhne opravdu tam, kde si myslíš, že to drhne?
Hello world ! Segmentation fault (core dumped)
31.3.2014 21:34 gld17 | skóre: 4 | blog: GLDiuv_blog
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Diky za tip, zkusim to udelat, ale zatim tuhle cast jeste nedelam, nejsem tak daleko. Ptam se preventivne a informativne.
1.4.2014 12:43 jake
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
v tom pripade bych to videl na predcasnou optimalizaci
1.4.2014 12:57 gld17 | skóre: 4 | blog: GLDiuv_blog
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
nevim jak ty, ale ja, narozdil od tebe, vim diky svemu zalozenemu tematu o tomto vypoctu odmocniny: https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code

Takze ses jen dalsi neprihlaseny brblal.
rADOn avatar 1.4.2014 17:06 rADOn | skóre: 44 | blog: bloK | Praha
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Tim "narozdil" bych si nebyl byt tebou tak jistej, to to co jsi objevil je legendarni a dobre znamej hack. Kdyz budes patrat dal tak se da najit i rozhovor s Carmackem kde (krome popreni otcovstvi) celkem jasne rekl ze dnes uz je blbost takovy vylomeniny delat.

BTW Jestli te zacaly bavit prekomplikovany optimalizace tak pogoogli termin "duff's device", to se ti bude libit. Zadnej z (nezasvecenych) ceckaru v praci nebyl schopnej rict jestli je to legalni C kod :-)
"2^24 comments ought to be enough for anyone" -- CmdrTaco
stativ avatar 1.4.2014 18:58 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Nejenom, že je to dobře známé, ale výkonově už je to k ničemu. Tedy většinou. Je to asi tak dva roky zpátky, kdy jsem potřeboval normalizovat hodně vektorů, tak jsem zkoušel různé přístupy a fast inverse square root byla v C několikanásobně pomalejší než knihovní funkce. A o řád pomalejší než SSE intrinsics. Co bylo zajímavé, tak v C# byl, pokud se dobře pamatuji, fast inverse srovnatelný s knihovní funkcí. SSE pak bylo kvůli přepínání do unmanaged módu očekávaně nejpomalejší.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
2.4.2014 23:03 jake
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
brblal? mas nejakej komplex? ... resit rychlost vypoctu odmocniny v tehle fazi vyvoje, ve ktere jsi, je proste nesmysl - az ti to pobezi a vykonove to nebude dostatecny, tak pak teprve hledej, kde tomu pomuzes, do ty dobe je tohle ztrata casu ... ale tak je to tvuj cas, ze jo ... JFYI tenhle "Cormackuv" trik zna fakt asi kazdej, tedy i ja - ale jo, ses borec, ze to znas taky ;-)
31.3.2014 23:10 axel
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Zdravim, Jinak bych si asi zkusil napsat sam nejaky assemblerovsky kod na to, cimz bych urcite zapusobil na porotu :D
Nepochybuju o tom, ze tvuj kod v assembleru bude radove vykonnejsi, nez knihovni funkce. Zabyvat se podobnou - podle mne nesmyslnou - uvahou o optimalizci vypoctu odmocniny v kontextu programu na rizeni koptery je ucebnicovy priklad uviznuti v detailu, ktery na porotu jiste zapusobi, mozna ale ne tim zpusobem, ktery ocekavas. Naprogramuj to s knihovni funkci, profiluj, a pak pripadne optimalizuj.
31.3.2014 23:17 gld17 | skóre: 4 | blog: GLDiuv_blog
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Beru to s rezervou. O vasi schopnosi pochopit moznosti takove knihovny a to nejen v kontextu s moji kopterou, nepochybuji.

Ocividne jste analyzu obrazu nikdy nedelal a nevite, jak dlouho to trva a na cem to vazne.
stativ avatar 1.4.2014 13:10 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Ocividne jste analyzu obrazu nikdy nedelal a nevite, jak dlouho to trva a na cem to vazne.
Mě přijde, že vy na tom nejste o moc lépe. Nevím, co konkrétně tam řešíte, ale pokud jde o rychlost výpočtu, tak se spousta věcí dá řešit pomocí lookup tabulek, pro float vstup se pak dá použít lineární interpolace hodnot z tabulky. Ale na samotné sqrt, sin aj. se to skoro určitě nevyplatí, protože HW implementace často nějakou formu LUT používá. Pokud ale výpočet jde sloučit do nějakého black boxu „hodím dovnitř číslo/čísla, vyhodí to výsledek“ a vstup je nějak rozumně omezen, tak je LUT většinou dobrá volba. Tabulka může být i vícerozměrná, ale její velikost je pak mnohem větší a chce si to opravdu dávat pozor na to, jestli její použití kvůli případným cache misses nebude pomalejší než to počítat normálně.

Další věc je, že jít do assembleru se většinou vyplatí jen v případě, kdy se problém dá dobře řešit pomocí SIMD instrukcí, což je k ničemu, protože RPi nemá NEON. Mnohem víc se získá upravením algoritmu (něco různě ošidit a podobně). Třeba u analýzy obrazu se často dá dobře využít časové koherence a počítat jen změny.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
Josef Kufner avatar 31.3.2014 23:51 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Nepochybuju o tom, ze tvuj kod v assembleru bude radove vykonnejsi, nez knihovni funkce.
Jsem si celkem jist, že tomu bude naopak. Leda by využil specifických podmínek daných konkrétním problémem. Ale to je problém spíš matematický, než programovací. Tady je lepší se zamyslet nad nahrazením pomalých operací něčím jiným – předpočítané tabulky, aproximace polynomem, kešování mezivýsledků, …

Taková předpočítaná tabulka hodnot často používaných vzorečků by mohla hodně pomoct. Pokud má málo významných číslic, je použité množství paměti celkem malé. Například tabulka 11bit int na 16bit int zabere 4KB, což se při troše štěstí vejde do L1 cache.

Další a mnohem zajímavější možností je použít grafický čip k výpočtům. Nevím jak moc Malina podporuje OpenCL, ale možná by jsi mohl aspoň něco implementovat pomocí shaderů.
Hello world ! Segmentation fault (core dumped)
Jendа avatar 1.4.2014 00:41 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Nevím jak moc Malina podporuje OpenCL
Myslím, že vůbec. A i kdyby, tak než se dočká výsledku z OpenCL, tak mu to spadne :) (musí počítat víc věcí paralelně a je tam laaaaaag)

Já myslím, že pokud má problém řídit quadcopteru s takto výkonným procesorem, chyba bude jinde než v pomalém počítání odmocnin a trigonometrie. Jsou i elektroniky s 8bit AVR na 24 MHz a funguje to.
Jendа avatar 1.4.2014 00:43 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Aha, už vidím, jde o analýzu obrazu. Zkusil bych to naprogramovat co nejvíc celočíselně.
Řešení 1× (stativ)
Jendа avatar 1.4.2014 00:33 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
RPi má hardwarovou FPU. Pokud nebudeš dělat ve svém algoritmu nějaké šílenosti typu bitslicing (to si u floating-point operací nedokážu představit), myslím, že HW FPU nemáš šanci předehnat.

Nevím, jak dlouho trvá na FPU v ARMu běžná operace, ale když to porovnáš s takovýmito šílenostmi, ten shift, odečtení a několik násobení asi vyjde hůř.
1.4.2014 13:01 potato
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Rozdíl mezi elementární operací a speciální funkcí na FPU je pořád asi tak řád, takže šílenosti jsou rychlejší, byť zrovna sqrt patří spíš mezi rychlé speciální funkce. Ostatně, vyzkoušej...
4.4.2014 12:46 Logik
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Řád? Takže máš na spočítání odmocniny, aby se vůbec vyplatilo ji aproximovat, cca 5 instrukcí....

Jendа avatar 4.4.2014 13:58 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Tak floatová odmocnina je u mě 10x pomalejší než ten bitshiftový odhad odkazovaný níže. A inverse square root je 2x pomalejší než ten z Quake (nemám pro to instrukci, dělám vsqrt a vdiv).
2.4.2014 22:00 Ivan
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Kdysi davno jsem prochazel knizku (anebo knihovnu) ktera se jmenova nejak jako "Numerical recipies in C++". Tak se daly najit naprosty silenosti, ktery normalni clovek nevymysli. Neco z toho se urcite pouziva jeste dneska.
2.4.2014 22:32 lertimir | skóre: 58 | blog: Par_slov
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Tak to je naprosto jasné. Algoritmizace, numerická matematika a aproximace, má za sebou desítky let vědeckého vývoje. V současnosti je už pokrok na mnoha místech malý, protože u mnoha algoritmů je dokázáno, že lepší konvergence/optimalizace už být nemůže. Mnoho knihoven zůstalo komerčních jako např. FORTRANská knihovna IMSL, kterou jsem používal někdy koncem 80 let. Právě FORTRAN je příklad jazyka, který skoro nic nekontroluje a provádí jen nezbytné operace. Triviální příklad pro algoritmizaci je aproximace funkce. Matematicky zřejmé je to Taylorovým rozvojem. Hodně nezřejmé, ale místo Taylora z nějakého jednoduchého počátku je aproximace po částech s různými počátky a okolími konvergentní mnohem rychleji. Vymyslet se to samozřejmě dá, ale člověk musí mít silný matematický background.
3.4.2014 09:56 DaBler | skóre: 12 | blog: dabler | Brno
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Pokud potřebuješ odmocninu √x a ne 1/√x, tak doporučuji tento trik:

http://bits.stephan-brumme.com/squareRoot.html

Nezkoušel jsem to na Raspberry Pi, ale na mém Intel Core2 je rychlejší než knihovní funkce sqrtf.
4.4.2014 12:39 TrSek
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Hrozne nepresne. Pisou ze +/- 5% ale co jsem testoval ja tak klidne i 12%.
Jendа avatar 4.4.2014 14:14 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Přílohy:
Pro malá čísla se to nehodí, pak to ale začne být docela hezké.
Jendа avatar 4.4.2014 14:29 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Přílohy:
Napadlo mě, že by nebyl špatný nápad normalizovat to přes velikost výsledku, ne přes to původní číslo :-). To už vypadá hůř (a realističtěji).
4.4.2014 17:36 DaBler | skóre: 12 | blog: dabler | Brno
Rozbalit Rozbalit vše Re: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.
Pokud jde o přesnost více než o rychlost, můžete k výpočtu odmocniny použít inverzní odmocninu zmíněnou výše:

1.f/Q_rsqrt(x)

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.