Matematika v robotice 23. Reálná čísla 3. Zákeřnost

7. ledna 2016 v 5:59 | Petr |  Roboti a Matematika
Pojem zákeřnost v počítačových algoritmech by si zasluhoval vlastní definici, nebo dokonce vlastní seriál. Osobně jsem udělal se "zákeřností" tolik zkušeností, že bydlet v Praze už je ze mě profesor "průserů" na některé "počítače řešící" fakultě.

Místo složitých definic posloužím příkladem. V dřevních dobách nebyly "hardwarově akcelerované" 2D i 3D grafické knihovny - pokud jste chtěli mít lepší úsečku než kreslil driver SVGA.DRV z Turbo Pascalu - museli jste si ji naprogamovat sami.

Jedna z mých assemblerových - ďábělsky rychlých - avšak neúspěšných - procedur pro kreslení úsečky využívala algoritmu zvaného "midpoint subdivision".

procedure LINE ( X1, Y1, X2, Y2 );
begin
IF (X1=X2) AND (Y1=Y2) THEN EXIT;
X_CENTER = ( X1 + X2 ) DIV 2;
Y_CENTER = ( Y1 + YZ ) DIV 2;
PutPixel ( X_CENTER, Y_CENTER);
LINE ( X1, Y1, X_CENTER, Y_CENTER );
LINE ( X_CENTER, Y_CENTER, X2, Y2 );
end;

Takže pro Pascalem nevládoucí - je to takto : Máte úsečku odcamcaď pocamcaď - spočtete její střed a tam uděláte tečku a pak voláte stejný algoritmus pro levý a pravý úsek, které udělají další a další tečky až "postupným půlením" úsečky namalujete všechny body.
OK to vypadá docela ideálně až na dvě drobné vady - buď počítáte "střed" bez zaokroulení - tedy X_CENTER = ( X1 + X2 ) DIV 2; a potom se pro určité kombinace souřadnic algoritmus "kousne" protože nikdy nenastane stav (X1=X2) AND (Y1=Y2) nebo můžete počítat se zaokrouhlením - ve stylu : X_CENTER = ( X1 + X2 + 1 ) DIV 2; ale potom dostanete - "hnus fialový namalovaný" ve stylu úsečky, kterou vidíte nahoře - vidíte tam ty nepravidelnosti ?

Jediná šance je použít "subpixelovou přesnost" - tedy pracovat třeba s 8 násbokem hodnot souřadnic a před procedurou PutPixel - je obě vydělit, ale tím je veškeré "kouzlo" tohoto algoritmu, který je v assembleru opravdu ďábelsky rychlý - ztraceno.

Tedy jasné co to je "zákeřnost" ? Tohle ovšem byla zákeřnost celočíselného algoritmu - u reálných čísel to však není o nic lepší. Říká se například, že účetnictví se nedá dělat v reálných číslech, protože se dostáváme do problémů, že potřebujeme od 3,57835928 miliard odečíst pět korun - kolik nám zbyde ? Díky implicitnímu zaokrouhlování mantisy zase 3,57835928 miliard - je to "oslíčku otřes se" nebo je to chyba výpočtu a tím pádem průser ?

Proto se pro účetnictví používají celá čísla a počítá se na jden halíř - ovšem "jak kdy" například banky počítají úroky z vkladů ( které musí vyplatit ) s oblibou po měsících a zaokrouhlují je dolů. Zatímco úroky z hypoték ( které si berou ) počítají po dnech ( kdyby to bylo možné počítali by to po pikosekundách ) a zaokrouhlují nahoru - protože "tím se více vydělá". Vůbec bych se nedivil kdyby ve velkých bankách bylo celé oddělení "výpočetní ne-přesnosti" které by se zabývalo otázkou jak dělat "nežalovatelné numerické chyby ve prospěch firmy".

OK mají roboti něco společného s bankou ? Okamžitě mě napadá jedna věc - váš robot ujel po celdenním "drandění" enkodérů 3,57835928 miliónů milimetrů a dostane příkaz - jeď ještě pět milimetrů a kolik bude "konečná vzdálenost" opět 3,57835928 miliónů milimetrů ? Je to "Zenonův paradox" nebo průser ve výpočtu ?

Takže je jasné, že na počítání čehokoliv "na kusy" potřebujeme celá čísla - což je zdánlívě přirozené, ale když vezmeme ty reálnými čísly počítané JPEGy - není to úplně intuitivní. Až budete přemýšlet jaký numerický formát použít - je třeba udělat tu složitou úvahu zdali je nutná "absolutní chyba" o jedničku - což znamená, že musíte používat celá čísla. To jsou úlohy typu přidej halíř k miliardě, nebo jestli je lepší použít relativní chybu typu "machine epsilon" - což vede k použití reálných čísel.

Pak je potřeba probrat ještě jednu věc - u reálných čísel a zejména u robotů ABSOLUTNĚ ZAKAZUJU používat konstrukce IF A=B THEN.... To je poukázka na zbláznění robota a přejetí maminy s kočárkem, nebo projetí zdí, nebo jiný průser. Tušítě proč ?

Kouzlo je totiž v tom, že pokud A i B vzniká každé jiným výpočtem je vysoce pravděpodobné, že se "nikdy nesejdou" a vždy se o "machine epsilon" budou lišit. Pokud tedy jste vůl a píšete A=B kompilátor porovnává tato čísla celočíselnou instrukcí CMP, která je považuje za stejná jedině pokud jsou všechny bity stejné. Správně a bezpečně je tedy IF abs ( A - B ) < Small_number THEN.

Otázka pak je co to má být Small_number - rozhodně to NESMÍ BÝT machine epsilon. Machine epsilon je relativní chyba - nikoliv abslutní hodnota !! Small_number tedy musí být nějaká hodnota, která je "pod rozličovací schopností daného algoritmu". Z toho pak vyplývá, že v extrémně nepříznivém případě musíme mít extra hodnotu typu Small_number pro každé porovnání.

Z tohoto pohledu vypadá porovnání A > B zdánlivě v pohodě, ale opět - za určitých okokností není - představte si, že hodnota A plynule klesá a hodnota B plynule roste - v tom případě, výraz bude dlouho Pravda a pak najednou přeskočí na Nepravda jo ? Může to tak být, ale taky to může být tak, že kolem hodnoty kdy A ( skoro ) = B, díky zaokroulování vyhodnocení podmínky "zakolísá" a bude dávat hodnoty pravda, nepravda, pravda nepravda a pak třeba už bude pokračovat dále jako nepravda.

Že to je "ezoterický problém", který v praxi nenastává ? Váš robot ale určuje svou trasu pomocí vyhodnocování, jestli je moc vpravo, nebo moc vlevo a cíl pozná podle POLOHA=CÍL ne ? Počítá s těmito zákeřnostmi váš algoritmus ? Když směr dalšího pohybu určují výrazy A > B nebo A < B - popisuje účinek "nestabilit" numerických algoritmů starý programátorský vtip : "Vstupujete li do počítačem řízeného výtahu - zapněte si bezpečnostní pás".....
Nakonec se dostáváme k "politicko-matematické" vložce. Západní společnosti se stále zlepšují - takže na obrázku máte "bilión" neboli 1012 dolarů ve stodolarovkách, což je 1/10 ceny za Americká "válečná dobrodružství" na blízkém východě po 11. září 2001. Pro srovnání - šipka ukazuje lidskou postavu namalovanou vedle "letiště plného palet se stodolarovkami" - pro srovnání velikosti. Počítání s takovými sumami je nepraktické i pro doporučená "celá čísla", proto si Američani pro spočtení svých dluhů vymysleli vlastní systém "plovoucích čísel" zvaných DECIMAL32 což je analogie "single" a DECIMAL64 což je analogie "double"

Kouzlo je v tom, že to je otrocký převod "vědecké notace" z displeje kalkulačky do PC tedy DECIMAL 32 má 1 bit znaménka 7 čísel mantisy od 0000000 do 9999999 a exponent. DECIMAL 64 je téměř stejný - jen má 16 cifer mantisy, - výhoda je, že miliardy a bilióny v této číselné soustavě se zaokroulují stejně jakoby je "intuitivně" zaokroulil člověk a navíc patrně tyto megasumy nevypadají tak děsivě.

TAkže tolik k reálným číslům - máte li "matematický koprocesor" nebo CUDA grafickou kartu ve vašem robotu - hrr na ně, ale nezapomeňte - opatrnost je na místě.

Mimochodem když vidím ty astronomické peníze a astronomické dluhy - napadá mě jediné čísla ještě "plavou", ale státy se už "potápějí" ?!

Poznámka při druhém čtení - jako obvykle mě ráno na míse napadlo ještě jedno řešení, jak "vydrbat ze systémem". Výraz IF A=B THEN by se možná dal přepsat jako IF A/B = 1 THEN - není vyloučeno, že tam by problémy s "machine epsilon" byly menší, ale zase by tam mohly být problémy se situací kdy A a zejména B by byly zanedbatelně malé až nulové. Jelikož jsem o takové variantě ani nic nečetl - nechávám prošlapávání "Cimrmanovských slepých uliček" tentokrát na čtenářích.
 

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

Komentáře

1 dotaz dotaz | 7. ledna 2016 v 10:24

K tomu kolísání - vadí to něčemu? První line followery (dva fotoodpory, dva tranzistory, dva motory) tak fungovaly a tu čáru někdy i opravdu udržely :-D MCU tomu dává víc možností, např. průměrování hodnot - ale jenom teoretizuju, žádného robotka jsem nikdy nestavěl, proto se tak blbě ptám… ?

2 petr-kubac petr-kubac | 7. ledna 2016 v 10:30

Line follower je ta jednodušší situace - regulace ve smyčce, kde i hrubá chyba se nakonec nějak vykompenzuje
zde je krásný příklad z mé dílny
http://petr-kubac.blog.cz/1305/matematika-v-robotice-3-co-je-to-presnost
Nejistota rozhodování u A > B ale může dělat problémy v některých případech typu "trvalého rozhodnutí" - jako je "teď odbočím vpravo a už se nebudu vracet"

3 dotaz dotaz | 7. ledna 2016 v 11:51

[2]: …nebo v případech vícenásobného „trvalého rozhodnutí”, kdy se nám ty chyby prostě budou kumulovat, až někde o dvacet křižovatek dál „zahnu blbě” prostě proto, že jsem nedokázal přijet v ose křižovatky. Už tomu asi rozumím, děkuji.

4 dotaz dotaz | 8. ledna 2016 v 5:53

Stejně mi to vrtá hlavou...ať už "machine epsilon tam a zpátky" nebo "100x machine epsilon", není aspoň částečným řešením mít "chytrá čidla a blbý procesor", a snažit se výpočtům v řádech statistické chyby úplně vyhnout (když to ještě navíc žere čas MCU)?

5 Honza V Honza V | 8. ledna 2016 v 11:49

Z jiných aplikací, kde bychom neradi ezoterické problémy, je dobré se tvrdých podmínek A > B raději vyvarovat a udělat to trochu spojitě (nějakou sigmoidou). Zaokrouhlovací chyby pak nemají "takovou moc".

K "politicko-matematické" vložce bych jenom dodal, že v dnešní době virtuálních pěněz jakožto pár bitů nekde na serverech není potřeba se držet při zdi. Ekonomický růst může trval klidně (skoro) do nekonečna, přihodíme pár bitů nebo to můžeme psát už rovnou v logaritmech. Státní dluh ve vlastní měně taky lze spatit asi tak za jednu milisekundu, když na to přijde.
Zkrátka, (velké) peníze už dávno opustily funkci uchovatele hodnoty, viz různé "poskitování likvidity". Tu funkci už mají jen malé peníze, které máme/nemáme na účtě a v peněženkách :-)

6 petr-kubac petr-kubac | Web | 8. ledna 2016 v 13:35

[5]: S oběma poznámkami souhlasím.
Pak tady je ještě možnost místo A > B použít ( A - B ) > Dostatečně_velká_hodnota - což by měl být mnohonásobek zaokrouhlovacích chyb možných při dané velikosti A a B

7 Pavel Pavel | 8. ledna 2016 v 19:04

ad astronomické peníze ....

toho si všiml už "Richard Feynman" ve svém slavném citátu :

"V galaxii je 10^11 hvězd. Kdysi to bývalo opravdu velké číslo. Ale je to jenom 100 miliard, to je míň než schodek státního rozpočtu. Takovým číslům jsme říkali astronomická, teď bychom jim měli říkat čísla ekonomická."

:o)

8 Vladan Vladan | E-mail | 17. ledna 2016 v 18:59

[2]: Pane doktore. Mám takovou otázku, která se netýká přímo tohoto tématu, ale je také elektrická. Nedávno jsem zakoupil  Vojenský přijímač R4. Natáhl jsen 20ti metrovou anténu a doporučený koax 70 Ohm jsem nesehnal, použil jsem 70 Ohm. Týden po poslouchání  na frekvenci 3,4MHz přišli sousedé i se staostou, že prý mohu neco rušit a tak podobné kraviny. Anténu jsem hezky stočil do bedýnky a mám po Ptákách.
Slyšel jsem že existuje širokopásmová anténa pro 1,4 - 12,5 Mhz . Jde o nějaký drát navinutý Cu na novodurovou trubku a . V elektrice jsem skončil na MFF UK vyhozením od první zkoušky, tak
sám nic nevymyslím, ani nenavrhnu. Vy jako Radioamatér a konstruktér robotů by jste mi mohl poradit jak na anténu do ??pokoje?? . budu Vám vděčný za povzbuzení a radu. Vladan
https://www.youtube.com/watch?v=fG_F8jzgHcg

9 petr-kubac petr-kubac | 18. ledna 2016 v 8:30

[8]: To jsou opravdu kraviny R4 je superhet, který do antény nic nevyzařuje ( některá rádia parazitně vysílají )

Nicméně jsem to taky zažíl, známý vyzyčil anténu na paneláku viditelnou z okna jisté dámy v soudedním paneláku a začaly problémy - zdechly rybičky, záda rozbolela a dokonce se pokazila žehlička !!!

Jestli do toho chcete jít tvrdě - ať si objednají měření na ČTU a dokážou vám, že rušíte.

Komentáře jsou uzavřeny.


Aktuální články

Reklama