close
Vážení uživatelé,
16. 8. 2020 budou služby Blog.cz a Galerie.cz ukončeny.
Děkujeme vám za společně strávené roky!
Zjistit více

Vážení uživatelé,
16. 8. 2020 budou služby Blog.cz a Galerie.cz ukončeny.
Děkujeme vám za společně strávené roky!

Matematika v robotice 22. Reálná čísla 2. Přesnost.

24. prosince 2015 v 5:21 | Petr |  Roboti a Matematika
Na začátku článku musím probrat otázky "nad dopisy diváků" . Především tedy omluva, za to, že minulý týden jsem místo "robotické matematiky" nabádal ke koupi hvězdářského dalekohledu, ale koukání na hvězdičky s děckama a rodinou je tak příjemné, že jsem to musel napsat ještě před Vánocemi. Druhá otázka je - proč používám pojem "reálné číslo" když v angličtině se to řekne "floating point number". Princip je v tom, že otrockým překladem "real number" vznikne "reálné číslo". Naopak "floating point number" jsem v jednom textu viděl přeložené jako "počet plovoucích teček" a od té doby se tohoto výrazu bojím....

OK dostáváme se k meritu věci - představte si program, který edituje obrázky - vstupem jsou pixely nějakého JPEGu nabývající celočíselných hodnot 0-255 výstupem jsou pixely jiného JPEGu nabývající celočíselných hodnot 0-255 - a způsob jak se s nimi pracuje ? Obrovské pole reálných číslel. Tedy skutečně je to tak - i softwary, které se zdají pracovat s výlučně celočíselnými daty většinou vnitřně pracují s reálnými čísly: první důvod jsme probrali minule - dneska jsou počítače přecpané hardwarovou podporou pro "floating point numbers". Druhý důvod souvisí s tím, že pokud jedno celé číslo přepočítáváte celočíselnou tedy "fixed point" matematikou na jiné číslo - musíte velice pečlivě dbát na to kolik bitů vám kde může přetéct, jak zaokrouhovat, abyste neztráceli přesnost a další zákeřnosti, které jsem zde na blogu ani nezmínil, ale jako programátor v celočíselném assembleru jsem si jich mnoho užil.

Tedy stručně - pokud máme 32 bitovbé celé číslo - buď jej procesor bere jako UNSIGNED - bez znaménka a v tom případě se jedná o celčíselný rozsah 0 - 4294967296. Pokud procesor bere takové číslo jako SIGNED ( se znaménkem ) pak je celočíselný rozsah od -2147483648 do +2147483647. V principu bych se měl stydět, protože procesoru je až na výjimky jedno jestli číslo je SIGNED nebo UNSIGNED - tohle je záležitzost interpretace 32 bitů softwarem. OK - "rozlišovací schopnost" 32 bitového celého čísla je 1 bit - tedy prosté číslo 1 a tato rozlišovací schopnost se hrubě mění podle velikosti čísla - tedy u hodnot 0-1-2- atd činí "Chyba o jedničku" - obrovskou sumu v desítkách procent. Už u 16 bitů není "chyba o jedničku nijak hrozná" rozdíl mezi 65535 a 65536 jsou tři tisíciny procenta - chyba celočíselného výpočtu je tedy "absolutní" a s velikostí čísel postupně klesá.

Jak je to s 32 bity "reálného čísla". V C se 32 bitovému reálnému číslu myslím říká "single" zatímco 64 bitové reálné číslo je "double" podle "single / double precision floating number". Abychom se v reálnch číslech vyznali - je třeba probrat "jak je to uděláno". Tedy "reálná čísla" v počítači jsou de facto stejná jako "dekadická čísla" běžného typu ve "vědecké notaci".

Příklad : Náboj elektronu je -1.6021766208×10−19 Coulombů tedy zápis je Z * M * 10E. kde Z je "znaménko" tedy + nebo - - v binárním tvaru je to 1 bit pak je M - Mantisa která je u "single" čísla 23 bitů - zásadou je že mantisa je vždy "vykrácena", tak aby její hodnota byla 0-1. V binárním tvaru je mantisa vykrácena tak aby nejvyšší bit byl vždy 1 a ten se "zahazuje" a tudíž 23 bitů mantisy umožní uložit 24 bitů. Jedinou výjimkou z tohoto pravidla je číslo 0 slovy "nula" - ta se ukládá tak, že všechny bity mantisy jsou nulové.

Poslední je E - exponent tedy na kolikátou musíme umocnit 10, abychom dostali správný řád čísla. I tohle je u binárních čísel odlišné - tam je exponent na kolikátou musíme umocnit "základ 2" abychom dostali správný řád a u typu "single" je tomu věnováno 8 bitů, které počítače považují za "signed" číslo tedy i Exponent má de-facto znaménkový bit, aby bylo jasné zda číslo je nepatrný zlomek, nebo veliká hodnota.

Pozoruhodné jsou další detaily "jak je to uděláno". Amatér by totiž jednotlivé bity uspořádal "naivně" to jest Zbit pak M bity mantisy pak E bity exponentu. ve skutečnosti je to v počítači úplně jinak první je Z bit, pak jsou E bity exponentu a pak teprve jsou M bity mantisy - tuší někdo ze čtenářstva proč ?
Ano je to tak - instrukce CMP pro porovnání dvou čísel je de-facto jejich rozdíl a procesor čísla odečte výsledek zahodí a pamatuje si akorát "znaménkové bity" tedy kladný, záporný, nebo nula což stačí k rozhodnuté větší, menší nebo stejný. Reálná čísla jsou udělána tak aby ač "reálná" dala se porovnávat stejnou "celočíselnou" instrukcí CMP. Posuďte sami : první je znaménko, protože pochopitelně jakékoliv kladné číslo je větší než jakékoliv záporné. Pak jsou bity exponentu. Tedy pokud znaménkový bit je stejný - a víme že mantisa je 0-1 pak je jasné, že 10 < 11 a tudíž bude 210 < 211. Poslední je pochopitelně mantisa, která se v tomto případě chová jako "svého druhu celé číslo" - takže pokud od sebe odečtete dvě "reálná čísla" celočíselnou instrukcí - vznikne nesmysl, ale znaménko tohoto nesmyslu - kladné, záporné, nulové - je správné.

OK - je tedy na čase zabývat se přesností "single" reálného čísla - základ je v mantise, která má 24 bitů a jak víme tak je vždy ( až na číslo 0 ) zaokrouhlená tak aby první bit ( který se zahazuje ) byl číslo 1 takže "nejmenší rozlišovací schopnost" mantisy je poměr mezi ( binárními ) čísly :
0b10000000 00000000 00000000 a 0b10000000 00000000 00000001 - což je poměr mezi čísly 16 777 216 / 16 777 217 - tedy díky neustálému zaokrouhlování mantisy na "první platný jedničkový bit" a s tím souvisejícím upravováním velikosti exponentu je "chyba" neboli "rozlišovací schopnost" reálných čísel typu "Single" asi 6*10-8. Pokud nechceme rozlišovaci schopnost počítat takto vidlácky a složitě - v teorii počítání s reálnými čísly existuje pojem "machine epsilon" - což je totéž, co naše chyba a ta je pro přesnost "single" definována jako 2-24 což je 5.96*10-8 BINGO

To bychom ale nebyli mezi matematiky, aby to bylo takto vidlácky jednoduché - takže ne všichni jsou toho názoru, že "machine epsilon" neboli teoretická chyba zaokrouhlování se má počítat takto - mezi teoretickými matematiky a informatiky jsou optimisiti, kteří tvrdí že chyba není větší než 2-24 ale pak jsou mezi nimi i pesimisti, kteří tvrdí že chyba může být "o bit větší" a dosáhnout až 2-23 neboli 1.19*10-07.

Jen pro zajímavost typu "Double" - neboli 64 bitů má 1 bit znaménka, 53 bitů mantisy a 11 bitů exponentu - takže tam je "rozlišovací schopnost" neboli "machine epsilon" 2-53 alias 1.11*10-16 pro optimisty a 2-52 neboli 2.22*10-16.

Pro případ veliké diskuse musím na plnou hubu zmínit že "machine epsilon" není "absolutní chyba" - takže ne aby se někdo ptal jak můžeme hodnoty 10-30 počítat s chybou 10-6. Na rozdíl od celých čísel je to relativní chyba takže zaokrouhlovací chyba výpočtu na hladině 10-30 je 10-30 * 10-6 neboli 10-36 jasné ?

OK takže máme tu ty reálnými čísly počítané JPEGy - ale krom toho máme v počítačových hrách v poslední době "High Dynamic range rendering" a taky ve fotografii máme "High dynamic range imaging" - takže pozice celých čísel obrázcích se trochu otřásá v základech, ale aby to nebylo tak, že RGB pixel zabere 12 bajtů - rozmáhá se v poslední době formát "half" - tedy 16 bitová reálná čísla.

Vůbec počítačové reprezentaci reálných čísel která mají méně než 16 bitů se říká "minifloats" a musím konstatovat, že - jako obvykle - na Wikipedii je o nich článek, který stojí za přečtení neb dává jasnější představu jak vlastně "nepřesnost" tohoto číselného formátu vypadá.
 

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

Komentáře

1 dotaz dotaz | 25. prosince 2015 v 13:22

S tím C a datovými typy - těsně vedle, je to přesně to, jak se to jmenuje, tedy v podstatě násobky. Délka pak závisí od sběrnice daného systému, a jelikož kolem toho bylo již mnoho napsáno i nadiskutováno a stejně to nikam nevedlo, tak nakonec v jedné z nejnovějších implementací byly v C zavedeny nové jednoznačné datové typy {např (u)int8_t nebo (u)int32_t} - knihovna stdint.h

en.wikipedia.org/wiki/C_data_types#stdint.h

2 Pirx Pirx | 26. prosince 2015 v 19:10

OFFTOPIC, ale aktualni:
Svet se definitivne obratil v zadnici:
http://programino.com/index.html
Zejmena me na zalozce Buy vydesila veta
"Allowed to use PROGRAMINO IDE for Arduino in commercial projects."
Pristi raketa k marsu bude rizena Arduinem...

Komentáře jsou uzavřeny.


Aktuální články

Reklama