Hlavní navigace

Základní aritmetické operace prováděné ve formátu FX

11. 7. 2006
Doba čtení: 11 minut

Sdílet

V sedmé části seriálu budou uvedeny postupy používané při aritmetických operacích prováděných s číselnými hodnotami reprezentovanými v systému pevné řádové binární čárky. Popíšeme si zejména základní aritmetické operace a také si ukážeme nejjednodušší způsob převodu hodnot z formátu FP do formátu FX a zpět.

Obsah

1. Kvantitativní popis zvolené reprezentace numerických hodnot ve formátu FX
      1.1 Přesnost
      1.2 Rozlišení
      1.3 Rozsah
      1.4 Dynamický rozsah
      1.5 Zhodnocení
2. Základní aritmetické operace prováděné ve formátu FX
3. Součet
4. Rozdíl
5. Součin
6. Podíl
7. Převod z FP formátu do FX formátu
8. Převod z FX formátu do FP formátu
9. Obsah dalšího pokračování tohoto seriálu

1. Kvantitativní popis zvolené reprezentace numerických hodnot ve formátu FX

Back in the olden days of dragons and sorcerers, before floating point coprocessors, computers could only directly manipulate whole numbers (integers). Things like decimal points were new fangled technologies only used by crazy mathematicians with slide rules and pen and paper. To overcome this deficiency crufty old-school programmers, many of whom today are over 30 years old, had to resort to various hacks and tricks in order to represent wacky numerical concepts like „0.5“ The most common technique was fixed point math.

Při bližším pohledu na číselné hodnoty uložené v některém ze systémů pevné řádové binární čárky (FX formátu) se mnohdy nevyhneme nutnosti kvantitativního popisu číselných hodnot, jež je možné v zadaném formátu ukládat. Vlastnosti množin všech možných hodnot, jichž mohou čísla ve vybraném formátu nabývat, je možné popsat pomocí veličin popsaných v následujících podkapitolách.

1.1 Přesnost

Přesnost (precision) Xprec značí maximální počet reprezentovatelných bitů, jež je možné nezávisle na ostatních bitech měnit, tj. nejsou stále nastaveny na konstantní nulovou či naopak jednotkovou hodnotu ani nejsou kopií předchozích či naopak následujících bitů. U formátů numerických hodnot uložených v pevné řádové binární čárce je přesnost rovna přímo délce bitového vektoru, tj. počtu bitů ve slově, kterými je číselná hodnota jednoznačně popsána. To ovšem platí pro čísla kladná nebo čísla uložená ve dvojkovém doplňku; v případě jedničkového doplňku nikoli.

1.2 Rozlišení

Rozlišení (resolution) Xres je možné vyjádřit absolutní hodnotou nejmenšího reprezentovatelného nenulového čísla. Příkladem může být formát A(13,2), u něhož je rozlišení rovno 1/22=0,25(10), nebo formát A(15,0), kde je rozlišení rovno 1/20=1,00(10). To znamená, že v daném formátu A(13,2) od sebe nelze jednoznačně rozlišit dvě navzájem rozdílné číselné hodnoty, které se od sebe liší o hodnotu menší než 0,25 a formát A(15,0) uchovává pouze celočíselnou část numerické hodnoty, tj. nerozliší například hodnoty 123,4(10) a 123,5(10).

1.3 Rozsah

Rozsah (range) Xran lze vyjádřit pomocí rozdílu mezi nejvyšší a nejnižší reprezentovatelnou hodnotou, s uvažováním znaménka reprezentovatelných hodnot, tj.

Uran=Umax+-Umax-
Aran=Amax+-Amax-

Příkladem budiž opět formát A(13,2), jehož rozsah lze vypočítat následovně:

Aran=Amax+-Amax-=8191,75-(-8192,00)=1638­3,75(10)

1.4 Dynamický rozsah

Dynamický rozsah (dynamic range) Xdr je dán poměrem mezi maximální absolutní hodnotou a minimální kladnou nenulovou reprezentovanou hodnotou. Pro formát typu A(a,b) se dynamický rozsah vyjádří následujícím vztahem:

Adr(a,b)=2×2/2-b=2a+b+1=2N

Obdobný vztah platí i pro formát U(a,b):

Udr(a,b)=(2a-2-b)/2-b=2a+b-1=2N-1

Všimněte si zajímavého výsledku předchozích vztahů: dynamický rozsah není závislý na poloze binární čárky, pouze na počtu bitů. To je ovšem logické, protože při přímém dělení dvou čísel uložených v FX formátu (tj. dělení bez ohledu na binární tečku) vlastně dochází k dělení celočíselnému.

1.5 Zhodnocení

Při provádění výpočtů s hodnotami uloženými v systému pevné řádové binární čárky je nutné pro každou zpracovávanou veličinu či bezrozměrnou hodnotu správně nastavit všechny zmíněné vlastnosti, tj. přesnost Xpre, rozlišení Xres, rozsah Xran a dynamický rozsah Xdr. Již z výše uvedeného popisu těchto vlastností je zřejmé, že se všechny vlastnosti vzájemně ovlivňují, tj. například nastavení přesnosti a rozlišení určuje další dvě vlastnosti apod.

V praxi se pro každou veličinu určí zejména rozsah a požadované rozlišení a následně se provede zjištění, zda je možné hodnoty dané veličiny ve vybraném formátu reprezentovat, či zda se musí provést redukce některé z vlastností, například snížení přesnosti či rozsahu hodnot.

Vzhledem k tomu, že se všechny výpočty budou povětšinou provádět na flexibilních čipech (CPU, DSP či FPGA), není nutné se omezit na pevně daný formát pro všechny veličiny s nimiž se výpočty mají provádět, protože každou část výpočtu lze provádět s hodnotami uloženými v jiném formátu s velmi jednoduchým převodem mezi jednotlivými formáty.

To je největší předností, ale současně i největší slabinou FX formátu. Předností je tato flexibilita pro toho, kdo zpracovávaný problém dokáže dobře analyzovat a následně pro jeho řešení navrhnout vhodné algoritmy (se znalostí hardwaru, na kterém výpočty poběží); výrazná slabina pro týmy preferující rychlý („quick and dirty“) vývoj – prototypování se většinou provádí ve vyšších programovacích jazycích, často s dynamickým typováním (Python, LISP), nebo netypových (Tcl, PHP) s podporou „velkých“ celočíselných a neceločíselných údajů. Při přenosu programu do jazyků s datovými typy odpovídajícími použitému hardwaru (většinou se jedná o typy byte/short int/int/long long int, float/single a double) potom mohou vznikat těžko odhalitelné chyby.

2. Základní aritmetické operace prováděné ve formátu FX

V dalších kapitolách si ukážeme způsob implementace základních aritmetických operací s numerickými hodnotami uloženými v FX formátu. Při praktických ukázkách budeme většinou používat formáty U(16,16) resp. A(15,16), a to zejména z toho důvodu, že pro zápis jednotlivých bitů je možné v těchto formátech s výhodou využít hexadecimálního zápisu. Ten bude odpovídat C-čkovské syntaxi, tj. každá šestnáctková hodnota bude začínat znaky . Tyto formáty jsou také využitelné na prakticky všech dnes používaných platformách, zejména na třicetidvoubitových procesorech, ale i na mnoha digitálních signálových procesorech či mikrořadičích. U obou zmiňovaných formátů je možné jednotlivé bity zapsat následovně:

0×WWWWFFFF

kde horních šestnáct bitů představuje celou část čísla (whole part) a dolních šestnáct bitů část zlomkovou (fractional part). V případě formátu A(15,16) je použit dvojkový doplněk, tj. čísla kladná mají nejvyšší bit nulový, zatímco čísla záporná jsou tvořena inverzí své absolutní hodnoty a přičtením jedničky – tím pádem je u záporných čísel nejvyšší bit vždy nastaven na jedničku.

Na tomto místě je opět vhodné poznamenat, že volba konkrétního formátu úzce souvisí se zpracovávaným problémem. Pokud bychom například potřebovali ukládat hodnoty goniometrické funkce sinus, bylo by vhodnější zvolit místo formátu A(15,16) spíše formát A(2,29), čímž se zvýší jak rozlišení, tak i využití všech bitů ve třicetidvoubitovém slově, protože hodnota funkce sinus leží v intervalu –1,0(10)..+1,0(10), pro celočíselnou část tedy není zapotřebí rezervovat celých šestnáct bitů.

3. Součet

Základní aritmetickou operací je nepochybně součet dvou číselných hodnot. Ten je možné provádět pouze v případě, že obě hodnoty mají stejný formát, tj. shodný počet bitů před a za binární řádovou čárkou. Pokud je tato podmínka splněna, je možné součet dvou numerických hodnot A a B zapsat následovně:

A×2b+B×2b=(A+­B)×2b

Vidíme, že není žádný rozdíl mezi součtem dvou celočíselných hodnot (integer) a hodnot uložených v FX formátu. To je jistě výhodné, protože při praktické implementaci je možné využít přímo instrukce nabízené použitým mikroprocesorem, resp. jeho aritmeticko-logickou jednotkou. V předchozí části tohoto seriálu jsme si řekli, že bitovou délku výsledků po aritmetické operaci dvou číselných hodnot uložených v FX formátech U(a,b) a A(a,b) je možné vyjádřit pomocí vztahů:

U(a,b)+U(a,b)­=U(a+1,b)
A(a,b)+A(a,b)­=A(a+1,b)

tj. pro uložení výsledku je obecně zapotřebí vyhradit slovo širší právě o jeden bit. Vzhledem k tomu, že se ve většině aplikací přesnost nezvyšuje, může při součtu nastat přetečení (overflow), což je stav, kdy se výsledná hodnota již nevejde do nastaveného počtu bitů. Přetečení je při provádění aritmetické operace součtu v aritmeticko-logické jednotce (ALU) většinou signalizováno nastavením příznaků CF (carry flag, příznak přenosu) a OF (overflow flag, příznak přetečení do znaménkového bitu). Příznak přenosu ve své podstatě nahrazuje chybějící N+1 bit výsledku a mnohdy se také k tomuto účelu používá, například při víceslovním sčítání. Příznak přetečení signalizuje přetečení výsledku do znaménkového (nejvyššího) bitu, což výsledek samozřejmě znehodnotí (z kladného čísla se stane záporné a naopak). Při práci s formátem U(a,b) postačí testovat pouze příznak přenosu, naopak formát A(a,b) vyžaduje oba příznaky, protože zde je situace složitější díky práci s dvojkovým doplňkem.

4. Rozdíl

Aritmetická operace rozdílu se provádí naprosto stejným způsobem jako aritmetická operace součtu. Pokud mají obě hodnoty vstupující do operace stejný počet bitů před a za binární řádovou čárkou, je splněna podmínka pro provedení operace rozdílu, kterou je možné zapsat následovně:

A×2b-B×2b=(A-B)×2b

Pokud se počty bitů před a za binární řádovou tečkou liší, je nutné provést přepočet jedné nebo obou hodnot na stejný formát. Přepočet spočívá v pouhém bitovém posunu doleva či doprava. Stejně jako v případě součtu, i u rozdílu dvou hodnot je nutné počítat s tím, že výsledek vyžaduje větší bitovou šířku (opět minimálně o jeden bit).

5. Součin

Operace součinu je již poněkud složitější než výše uvedené operace součtu a rozdílu. Je to z toho důvodu, že se počet bitů výsledku rapidně zvyšuje, což může na některých architekturách způsobovat problémy s malou bitovou šířkou násobičky vestavěné v aritmeticko-logické jednotce. Formát výsledku je možné vyjádřit následovně:

U(a1, b1) × U(a2, b2)=U(a1+a2, b1+b2)
A(a1,b1) × A(a2, b2)=A(a1+a2+1, b1+b2)

Přitom je možné násobit dvě hodnoty, jejichž formáty jsou rozdílné, tj. počet bitů před a za binární řádovou čárkou může být rozdílný. Dokonce je možné provést vynásobení celočíselné hodnoty hodnotou uloženou ve formátu FX – to u operací součtu a rozdílu možné nebylo. Konkrétně, tj. pro vybrané formáty U(16,16) a A(15,16) nabývá výsledek součinu tvaru:

U(16,16) × U(16,16)=U(32,32)
A(15,16) × A(15,16)=A(31,32)

Z původně třicetidvoubitových slov se tedy stala slova šedesátičtyřbitová. Na architektuře x86 to nezpůsobuje větší problémy, protože operace násobení svůj výsledek ukládá do dvojice registrů, na některých DSP je však bitová šířka výsledku menší. Z toho důvodu se může před operací násobení uměle zmenšit přesnost hodnot vstupujících do této operace, například tak, že se hodnota posune o n bitů doprava. To má samozřejmě za následek nárůst chyby výpočtu. V případě, že je požadován stejný formát výsledku jako je formát obou operandů, musí dojít k bitovému posunu výsledku o b bitů doprava a k odseknutí horních a bitů.

Pokud bychom například měli k dispozici pouze třicetidvoubitovou násobičku, mohou se vstupující hodnoty upravit z formátu U(16,16) na formát U(24,8) prostým posunem o 8 bitů doprava. Horních osm bitů je přitom nastaveno na nulovou hodnotu, fyzicky se tedy jedná o formát U(24,8), logicky však o formát U(16,8). Výsledek násobení dvou hodnot bude nabývat tvaru U(16+16,8+8)=­U(32,16), ale vzhledem k tomu, že násobička je pouze třicetidvoubitová, je výsledek ořezán do formátu U(16,16), tj. pro mnoho vstupujících hodnot je pravděpodobné, že při násobení dojde k přetečení a tím pádem i k znehodnocení výsledku.

Na to je zapotřebí při implementaci FX formátu neustále myslet, zejména u operací, při kterých je sice výsledek poměrně malý (odpovídající vstupním hodnotám), ale v průběhu výpočtu se pracuje s hodnotami mnohem většími. Typickým příkladem je výpočet délky vektoru v ploše či prostoru, při kterém se provádí umocňování jednotlivých složek (zde může dojít k přetečení) a po součtu druhých mocnin dojde k odmocnění, takže výsledek je sice řádově srovnatelný se vstupními údaji, ale uvnitř výpočtu se pracuje s mnohem většími hodnotami.

6. Podíl

Při podílu dvou hodnot se opět mohou pro dělence a dělitele použít rozdílné FX formáty, včetně čísel celočíselných. Formát výsledku se určí podle vztahů:

U(a1, b1)/U(a2,b2)=­U(a1+b2, | log2(2a2+b1-2b1-b2)|)
A(a1, b1)/A(a2, b2)=A(a1+b2+1­, a2+b1)

Což pro námi zvolené formáty U(16,16) a A(15,16) znamená:

U(16,16)/U(16­,16)=U(16+16, |log2216+16-216–16|)=U(32,31)
A(15,16)/A(15­,16)=A(32, 31)

O podílu platí téměř stejné údaje jako u operace násobku, tj. na některých architekturách mohou nastat problémy z důvodu malé bitové šířky děličky. V těchto případech se (opět) může provést úprava dělence a dělitele před vstupem do operace podílu. Buď se zabrání přetečení výsledku (dělení dělencem bitově posunutým doleva), nebo se naopak zvýší přesnost výsledku s tím rizikem, že může dojít k přetečení. Na architektuře x86 je však dělení podporováno i pro dvojnásobně široké operandy (dvojice registrů).

7. Převod z FP formátu do FX formátu

Nejjednodušší (ale v některých případech i zdlouhavý) převod numerických hodnot z formátu plovoucí řádové čárky do formátu pevné řádové čárky je možné provést pomocí jednoduché operace:

XFX=XFP×2b

Alternativně je možné provést programovou rotaci mantisy FP hodnoty tak, aby hodnota exponentu odpovídala požadovanému počtu bitů b. Na tomto místě je vhodné podotknout, že některé matematické koprocesory (FPU) přímo obsahují instrukci násobení a dělení celočíselnou mocninou dvou, která je rychlejší, než obecné násobení, takže programová rotace mantisy může být pomalejší než výše uvedené násobení.

Pro převod celočíselné hodnoty (integer) do formátu pevné řádové tečky se provede pouze bitový posun původní hodnoty o b bitů doleva, což je opět podporovaná operace (tentokrát prováděná na CPU a nikoli na FPU):

XFX=XINT<<b

8. Převod z FX formátu do FP formátu

Zpětný převod numerické hodnoty z formátu pevné řádové čárky do formátu řádové čárky plovoucí se v nejjednodušším případě provádí převrácením postupu uvedeného v předchozí kapitole, tj:

XFP=XFX/2b

Za povšimnutí však stojí fakt, že například FX formát A(15,16) či U(16,16) není možné převést beze ztráty přesnosti na FP formát float/single, i když mají oba formáty pro číselnou hodnotu vyhrazen stejný počet bitů. Je tomu tak proto, že v FP formátu je část bitů určena pro uložení exponentu, což samozřejmě u FX formátů s implicitně umístěnou binární řádovou čárkou není nutné (binární tečka je určena programově a není ji tedy zapotřebí ukládat spolu se zpracovávanou hodnotou). Z tohoto důvodu se při převodu mezi FX formáty a FP formáty se stejným počtem bitů počítá se ztrátou přesnosti a také je vhodné nastavit vhodný způsob zaokrouhlení. Většinou jsou podporovány čtyři režimy zaokrouhlení, jejich volba závisí na povaze řešeného (počítaného) problému:

UX DAy - tip 2

  1. round to zero: zaokrouhlení směrem k nule, tj. kladná čísla k pravému konci osy a záporná čísla k levému konci
  2. round to +inf: zaokrouhlení směrem k +∞, tj. k levému konci osy
  3. round to -inf: zaokrouhlení směrem k -∞, tj. k pravému konci osy
  4. round to nearest: zaokrouhlení k nejbližší reprezentovatelné hodnotě

9. Obsah dalšího pokračování tohoto seriálu

Příště si již ukážeme algoritmy (realizované v programovacím jazyce C), ve kterých budou implementovány základní aritmetické operace s FX formátem, samozřejmě včetně převodu z FP formátu do FX formátu a naopak.

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.