Matematika v robotice 21. Reálná čísla 1. Rychlost

10. prosince 2015 v 6:00 | Petr |  Roboti a Matematika
Bylo nebylo - býval jsem kdysi velmi zadobře s jistým významným pražským biochemickým profesorem - nejednu přednášku jsme spolu udělali, ale pak se on vydal k "temné straně síly" a mně nezbylo než prohlásit notoricky známé - "aktivní blb je horší než třídní nepřítel" a dokonce "pekelná brána se mu už zjevuje" - což jsem dokonce napsal na tomto blogu. Jaké pak bylo překvapení, když jsem se v jeho poslední knize - dočetl : Zaostalci mohou být nebezpeční nejen pacientům, ale mohou ohrožovat i seriozní "názorové vůdce", rozvojem pocitu zmaru a beznaděje, při nepřetržitém přesvědčování o kvalitě důkazů, moderních podložených postupů a guidelines ....

A víte o čem ta kniha byla ? O matematice v medicíně, protože oba se považujeme za matematicky orientované - jenom on je vědec a píše články ve stylu "Implikace Bayesova teorému v interpretaci laboratorních vyšetření" - zatímco já píšu "Vzácné choroby nelze potvrdit, pouze vyloučit" - asi si myslíte, že jsem vidlák z Frydku a tak mi to patří, ale pozoruhodné je, že obě ty věty - znamenají to samé, co už jsem taky na svém blogu jednou popsal a to ZDE. Schválně teď udělejte 5 minut pauzu a přečtete si to jestli tomu rozumíte, nebo ne - rozumíte že - takže už víte proč jsem ošoupaný borec s posledními botami.

Proč jsem tu kolegovu "podivnou" knihu četl - prototože jsem hledal inspraci, kterou jsem nakonec nenašel - na přednášku, která by kolegům doktorům vysvětlila něco matematiky, ale aby tam slovo "matematika" nebo "statistika" nebo "implikace" nebo nedej bože "teorém" ani jednou nepadlo, což se mi nakonec povedlo, jenomže když jsem potom byl plný písmen "sigma" a "chí" - tak jsem si uvědomil, že jsem se velice podrobně zabýval celočíselnou matematikou programovanou v assembleru, ale zcela jsem ignoroval "reálná čísla" alias "floating point numbers" a jejich "implikace" pro programování robotů.
Tedy dosti již planého kecání - Použití nebo nepoužití reálných čísel v robotech má minimálně 3 aspekty, které postupně probereme a to :
  1. Rychlost výpočtu
  2. Přesnost výpočtu
  3. Kdy ano a kdy ne - neboli "Zákeřnost"
Dnes tedy máme na programu probrat ještě rychlost. Když si všimnete, tak výkony "superpočítačů" se měří ve FLOPS alias Floating Point Operation Per Second - neboli kolik operací s reálnými čísly daný počítač udělá - vůbec se neberou MIPS - tedy Milióny Instrukcí Per/za Sekudnu. To má své hlubší příčiny.

Příklad - průměr dvou čísel v celočíselné matematice spočtete jako
C = ( A + B ) >> 1
To jsou dvě operace - součet a bitový posun - pak tu ale máme ten problém, že takhle může dojít ke ztrátě přesnosti a musíme průměr zaokrouhlit Tedy :
C = ( A + B + 1 ) >> 1
to už jsou tři operace - tedy o jednu více než když to počítáte "klasicky" s reálnými čísly neboli
C = ( A + B ) / 2
OK - pořád můžete namítat, že Integerových - alias "celočíselných" jednotek je v moderních procesorech více než "floating point" a že celočíselný výpočet půjde rychleji, ale pak si představte "zaokrouhlený" průměr z 5 čísel, který by se ve "float" matematice zapsal takto :
F = ( A + B + C + D + E ) / 5
Jak taky jinak, ale v "integerové" matematice bychom museli napsat :
F = ( A + B + C + D + E + 2.5 ) DIV 5
Zapsat celočíselně 2.5 je problém - takže můžeme rezignovat na přesnost zaokrouhlení a dát tam 2 nebo 3 , nebo napsat něco jako:
F = [ ( A + B + C + D + E ) << 1 + 5 ] DIV 10

To je první problém - druhý problém je jasný - každá "floating point" architektura má instrukci "fdiv" pro dělení, ale "celočíselné dělení "DIV" mají jenom některé procesory a dělit postupně odčítáním a bitovými posuny je hrůza.

Je tedy jasné, že pokud nebereme, pár speciálních výpočtů kde celočiselná matematika v assembleru je rychlejší - pokud má daný procesor matematický koprocesor - neboli Hardwarovou jednotku pro reálná čísla - je výhodnější používat reálná číla - na co to jenom jde ( a na co to nejde probereme v posledním díle ).

Navíc - celéočíselné operace se považují za "vyřešenou věc" a patrně memůžeme ani u nových procesorů čekat nic převratného, zatímco "floating point" operace - díky počítačovým hrám a vůbec 3D grafice zažívají obrovský boom - jednak tady existují uvnitř našich počítačů opravdové superpočítače - akorát se jim nějakým omylem říká "grafické karty" a navíc ani samotné procesory nechtějí zůstat pozadu takže kažého půl roku Intel a ti další oznamují "nové instrukční sady" - pro reálná čísla - většinou typu SIMD tedy "single instruction multiple data" - jen pro představu o čem se mluví tak se tomu říká MMX, SSE1, SSE2, SSE3, SSE4 a tak dále a tak podobně - takže pro reálná čísla zkompilovaný program - rekompilovaný novým kompilátorem, pro nový procesor může velice překvapit, aniž byste v kódu přepisovali jedinou řádku.

Patrně budete namítat, že CORE i7 se vám do SUMO-Robota nevejde, ale o tom se dneska nebavíme - dnes probíráme "velké roboty" ve stylu Darpa Robot challenge - a tam se už nějaký "ATOM", které všechny, bez výjimky jsou těmito "floating point blbostmi" vybaveny - v pohodě vejde.

OK těšte se na příští týden - kde budeme probírat přesnost / nepřesnost reálných čísel.
 

Buď první, kdo ohodnotí tento článek.

Komentáře

1 Mroks Mroks | 10. prosince 2015 v 11:00

No konečne seriál presne podľa môjho gusta. Už sa teším aj na druhý týždeň.

2 Perpeťák Perpeťák | 11. prosince 2015 v 10:47

Psát jako robotik články o robotech mi připadá jak chtít být děvkař, a psát články o šukání. Pavlu Šrajtovi z časopisu ABC mladých přírodovědců to kdysi již před čtyřiceti lety opravdu reálně jezdilo, materiál byl Merkur a plíšky ustříhané z pocínovaných plechovek, a jeho špičkovou součástkou byl přitom tehdy tak maximálně fotoodpor 1PP70.

3 c c | 11. prosince 2015 v 12:11

Psát o robotech, to je jako psát o býčích zápasech. Čtenáři jsou většinou jen diváci, kteří by  chtěli být také strašně stateční, ale nejsou...

4 dotaz dotaz | 13. prosince 2015 v 23:11

[2]:[3]: A pointa? V DARPA jsou podle vás idioti co vyhazují miliony $ zbytečně, protože by stačil kus plechovky a fotoodpor, říkám to správně?

5 Perpeťák Perpeťák | 14. prosince 2015 v 10:12

Výšeuvedené tvrzení je mistrovský odskok o 180 stupňů od skutečného problému:
1- V DARPA jsou idioti co vyhazují miliony $ zbytečně... -ANO
2- ..by stačil kus plechovky a fotoodpor...-NE

Připadá mi to podobné, jako když dovedeme zapálit oheň sirkou, a někdo nám stále vnucuje zlatý zapalovač s nedostižným designem a mikroprocesorovým řízením zapalovacího napětí s těploměrem a výškoměrem ta tisíc dolarů, kterým když škrtneme, tak se nezapálí, a ohlásí nám softvérovou chybu na adrese 1CAF F5D0.

6 dotaz dotaz | 14. prosince 2015 v 11:40

[5]: nebýt DARPA, tak si ty své výlevy můžete dnes psát tak akorát na papír. Jelikož je tím řečeno vše podstatné, diskuse právě skončila.

7 Perpeťák Perpeťák | 14. prosince 2015 v 16:21

V jednom Čapkově románu dal Bůh člověku Hlínu stovoření, a ten s ní jako svůj první pokus udělal blechu. Takto přesně mi připadá vývoj počítačů a techniky okolo od jejich vynálezu. Ideu praktického zkasírování nákladů vývoje počítačů jejich násilným vnucením solventním Blbcům krásně vystihuje někdejší rozhovor mladého dlouhlovlasého Steva Jobse s jeho přítelem Vozniakem, popisovaný v jeho životopisu, kde Vozniak se ptá:

Co s těma počítačema ty blbci budou dělat, vždyť to od nás nikdo nekoupí..

A Steve mu odpovídá:

Co blbneš, vnutíme to všem, třeba i babám do kuchyně.

A Vozniak se fascinovaně ptal:

A co s tím ty baby budou v tý kuchyni dělat?

A Steve odpověděl:

Budou si do těch počítačů psát své dny, a kuchařské recepty, a hlavně, budou moct dělat před těma, co to ještě nemají, chytrý !!!

8 Perpeťák Perpeťák | 14. prosince 2015 v 17:26

Už jen video, a končím...

https://www.youtube.com/watch?v=ExbYMgwRDlw

9 m.marianek m.marianek | 14. prosince 2015 v 19:23

[8]: Mno, něco na tom bude, když jsem poprvé viděl Minecraft, tak mi naprosto vyrazilo dech, že hra, která pro svůj rozumný běh potřebuje minimálně dvoujádrový procesor na 2GHz a 2GB RAM, vypadá hůř jak DOOM. Musí být umění napsat něco takového. Mimochodem víte co je totální rozpolcení osobnosti operačního systému? Nabootovat multibootem z Grubu Windows, spustit na nich portable Ubuntu, v něm Wine, ve Wine spustit Internet Explorer a připojit se na www.Linux.com :-D. Takhle nějak si představuju, že funguje Minecraft (resp. ještě o poznání hůř).

10 Petr G. Petr G. | 19. prosince 2015 v 15:54

[9]:  :-D hezky napsáno.

DARPA má aspoň neomezený rozpočet.
Ostatní idioti s omezeným rozpočtem mají neomezené sebevědomí.

11 Dalík Dalík | 31. prosince 2015 v 20:25

GEEK: jsem jen obyčejný český jouda, ale takto geniální způsob zaokrouhlování jsem ještě neviděl... kolik jste toho při psaní vypil?

12 Mroks Mroks | 2. ledna 2016 v 18:26

[11]: však Kubáčove zaokrúhľovanie už máš preštudované http://petr-kubac.blog.cz/1306/matematika-v-robotice-7-svet-celych-cisel-4
...už vtedy si tam pridával komentár :-)

13 Dalík Dalík | 3. ledna 2016 v 23:44

12: máte pravdu, děkuji, zjevně jsem v minulém článku tento způsob zaokrouhlování zcela přijal za svůj :)

nicméně:

A   B   (A+B)>>1  err1  (A+B+1)>>1  err2
10  10   10        0      10         0
10  11   10        -0,5   11         0,5
11  11   11        0      11         0
11  12   11        -0,5   12         0,5
12  12   12        0      12         0

průměrná chyba je konkrétně při dělení dvěma furt stejná, takže ono přičítání jedničky je zbytečná operace. Při dělení vyššími čísly už zaokrouhlování průměrnou chybu snižuje a má smysl.

14 petr-kubac petr-kubac | 5. ledna 2016 v 10:39

Představte si následující situaci - počítáte exponenciální klouzavý průměr z hodnot
1 1 1 1 1 1 1 1 1 1 až do nekonečna - bez zaokrouhlení - takže startujete s hodnotou průměru 0
(0+1) >> 1 = 0
(0+1) >> 1 = 0
atd...
takže klouzavý průměr nikdy nedosáhne nominální hodnoty, které má dosáhnout.

Existují i opačné situace - tedy vstupní data jsou

0 0 0 0 0 0 0 a minulý průměr je 1
v takovém případě klouzavý průměr nidky nedosáhne hodnoty 0 - tudíž se zdá, že je to opravdu jedno zdali chyba je + nebo - 0,5 bitu.

Praxe z programování číselných algoritmů ale ukazuje, že hodnota 1, která vytrvale ( a špatně ) zůstává v nějaké proměnné je daleko "bezpečnější" než hodnota 0 s ohledem třeba na dělení a další zákeřnosti - doporučuju vyčkat na příští díl, kde je takový hezký příkládek tohoto principu.

15 Dalík Dalík | 5. ledna 2016 v 22:14

Díky za reakci, na další díl počkám.

Nicméně ten druhý příklad bude také hned 0, ne?
(1+0)>>1 = 0

16 petr-kubac petr-kubac | 7. ledna 2016 v 10:57

[15]: Ajaj - nedorozumění - druhý případ jsem myslel se zaokrouhlováním - jakože ( 0 + 1 + 1 ) >> 1 = 1 atd....

Komentáře jsou uzavřeny.


Aktuální články

Reklama