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.
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… ?