Hlavní navigace

Fixed point arithmetic

24. 5. 2006
Doba čtení: 13 minut

Sdílet

Dnešním dnem začíná na Rootu krátký seriál, který si klade za cíl přiblížit čtenářům problematiku reprezentace (způsobu uložení) numerických hodnot v operační paměti počítače s možností jejich následného zpracování pomocí mikroprocesoru (CPU), popř. i matematického koprocesoru (FPU).

Obsah

1. Reprezentace numerických hodnot ve formátu pevné a plovoucí řádové (binární) tečky
2. Jakými způsoby je možné reprezentovat číselné hodnoty v operační paměti počítače?
3. Uložení čísel ve formátu pevné řádové binární tečky
4. Přednosti a zápory formátu pevné řádové tečky
5. Uložení čísel ve formátu plovoucí řádové (binární) tečky
6. Formát plovoucí řádové binární tečky a norma IEEE 754
7. Přednosti a zápory formátu plovoucí řádové tečky
8. Literatura a odkazy na Internetu
9. Obsah dalšího pokračování tohoto seriálu

1. Reprezentace numerických hodnot ve formátu pevné a plovoucí řádové (binární) tečky

V tomto článku, na který bude navazovat i několik pokračování, si popíšeme některé ze způsobů reprezentace (resp. způsobu uložení) podmnožiny racionálních numerických hodnot (zkráceně čísel) v operační paměti počítače a/nebo v registrech jeho mikroprocesoru (CPU) či matematického koprocesoru (FPU). Jedná se o takzvané uložení vybrané množiny numerických hodnot v systému pevné řádové (binární) tečky. V tomto textu se budeme záměrně dopouštět drobného prohřešku oproti stávající normě českého jazyka, protože budeme neustále psát o řádové, desetinné a binární tečce a nikoli čárce – z hlediska anglické terminologie to bude více konzistentní, i když z češtinářského hlediska by bylo zcela jistě korektnější psát o řádové čárce, protože se v češtině celá část čísla od části desetinné odděluje právě čárkou a nikoli tečkou, jak je tomu zvykem v anglosaských zemích (programátoři, kterým je tento článek určen především, však tuto skutečnost zcela jistě znají).

V anglické literatuře se zmíněná forma reprezentace číselných hodnot označuje zkratkou FX nebo FXP (fixed point), zatímco dnes častěji používaná reprezentace v systému plovoucí řádové tečky se všeobecně označuje zkratkou FP (floating point). V jednom článku jsem dokonce místo zkratky FX viděl i zkratku XP (fixed point), ale to bylo před mnoha lety, v době Windows 95 :-). Nejprve si vysvětlíme princip obou metod použitých pro ukládání podmnožiny racionálních čísel a posléze si také řekneme, jaké výhody a nevýhody jednotlivé principy přináší v každodenní programátorské praxi a ve kterých situacích je vhodnější použít pevnou řádovou čárku. V dalším textu budeme formát pevné binární řádové tečky zkracovat na FX formát a formát používající plovoucí řádovou tečku budeme zapisovat jako FP formát.

2. Jakými způsoby je možné reprezentovat číselné hodnoty v operační paměti počítače?

Při ukládání číselných hodnot do operační paměti počítače záhy narazíme na některé problémy, z nichž některé souvisí s konečným počtem bitů, které pro uložení dané hodnoty „obětujeme“, a další vycházejí ze způsobu zpracování hodnot mikroprocesorem či matematickým koprocesorem. V konečném počtu bitů je totiž možné uložit pouze konečné množství různých hodnot a je plně v rukou programátora, jak efektivně daný počet bitů využije či naopak promrhá ukládáním nepodstatných informací. Poměrně často se totiž stává, že i program využívající dvojitou či dokonce rozšířenou přesnost čísel při FP operacích (tj. datové typy double a extended/tempo­rary) dává nesprávné výsledky dané nepochopením principu práce FP aritmetiky a přitom je možné se přesnějších výsledků dobrat i při použití pouhých 32 bitů, ale s pečlivě vyváženými aritmetickými a bitovými operacemi.

Na druhou stranu nejsou dnes používané mikroprocesory tak univerzálními zařízeními, jak by se na první pohled mohlo zdát. Mikroprocesory jsou totiž (většinou) navrženy tak, aby účinně, například v rámci jedné operace či instrukce, zpracovávaly pouze konstantní počet bitů. Příkladem mohou být dnes velmi rozšířené procesory řady x86, které jsou velmi dobré při práci s 32 bitovými hodnotami, ale při požadavku na aritmetické výpočty probíhající na (řekněme) 21 bitech se veškerá jejich efektivita ztrácí a procesor se širokými vnitřními sběrnicemi, matematickým koprocesorem atd. se potýká s prohazováním jednotlivých bitů. Mnohem lepší situace nastane v případě, že se nějaká operace implementuje na programovatelném poli FPGA – zde je možné vytvořit obvody provádějící matematické a logické operace s libovolným počtem bitů, čímž se oproti univerzálním řešením (např. konstantní bitová šířka sběrnice a/nebo registrů) ušetří mnoho plochy těchto velmi zajímavých obvodů (FPGA mohou mimochodem znamenat i velkou šanci pro hnutí open source – pomocí nich by mohlo vznikat, a někde už vzniká open hardware, které by mohlo odstranit závislost na „uzavřených“ síťových a grafických kartách apod.).

Vraťme se však ke způsobům reprezentace číselných hodnot v operační paměti. Nejprve předpokládejme, že pro reprezentaci vlastností určitého objektu či stavu z reálného světa použijeme N binárních číslic (bitů), tj. základních jednotek informace, která může nabývat pouze jedné ze dvou povolených hodnot (ty se značí například symboly yes/no nebo true/false, ale my se budeme spíše držet označení 0 a 1). Pomocí této uspořádané N-tice je možné popsat celkem:

20×21×22 … 2N-1=2N

jednoznačných, tj. navzájem odlišných, stavů. Množina těchto stavů může reprezentovat prakticky jakýkoliv abstraktní či reálný objekt. Přitom si musíme uvědomit, že u této množiny není implicitně řečeno ani myšleno, že se jedná například o celá kladná čísla, to je pouze jedna z mnoha možných interpretací zvolené N-tice (my programátoři máme tendenci považovat celá kladná čísla za přirozenou interpretaci bitové N-tice, to však vychází pouze z našeho pohledu na svět a z našich zkušeností). Reprezentaci momentálního stavu abstraktního či reálného objektu si můžeme představit jako zobrazení z množiny binárních stavů na elementy vzorové (a obecně neuspořádané) množiny. Nejčastěji používanými zobrazeními jsou zobrazení množiny binárních stavů na interval celých kladných čísel (Unsigned Integers), popřípadě na interval celých čísel (Signed Integers).

3. Uložení čísel ve formátu pevné řádové binární tečky

Numerické hodnoty zapsané ve formátu pevné řádové binární tečky se chápou jako podmnožina racionálních čísel, což jsou taková čísla, jejichž hodnoty lze vyjádřit vztahem:

xFX=a/b    a,b leží v Z, b ≠ 0

Číselné hodnoty z uvažované podmnožiny jsou navíc omezeny podmínkou:

b=2k    b leží v Z, k leží v Z+

Protože b je celočíselnou mocninou dvojky (a ne desítky či jiného základu), určuje jeho hodnota n polohu binární tečky v uloženém čísle. Další podmínkou, která má však spíše implementační charakter, je zachování stejného počtu binárních cifer v každém reprezentovaném čísle, což mimo jiné znamená, že všechna čísla mají řádovou binární tečku umístěnou na stejném místě – z této podmínky ostatně plyne i název popisovaného způsobu reprezentace vybrané podmnožiny racionálních čísel. Tak jako i v jiných reprezentacích čísel jsou nulové číslice před první nenulovou cifrou a za poslední nenulovou cifrou nevýznamné, proto je není zapotřebí uvádět.

Prakticky může být číselná hodnota v systému pevné řádové tečky uložena na osmi bitech například následujícím způsobem (uvažujeme pouze kladné hodnoty):

Číselná hodnota uložena na osmi bitech
Pozice bitu 8 7 6 5 4 3 2 1
Váha bitu 24 23 22 21 20 2-1 2-2 2-3
Desítková váha bitu 16 8 4 2 1 0,5 0,25 0,125

4. Přednosti a zápory formátu pevné řádové tečky

Ve výše uvedeném příkladu je binární řádová tečka umístěna vždy mezi třetím a čtvrtým bitem. Vzhledem k tomu, že je tato skutečnost dopředu známá algoritmu, který provádí zpracování čísel, není zapotřebí spolu s číslem uchovávat i pozici binární tečky, což výrazně snižuje počet bitů, které je zapotřebí rezervovat pro čísla ze zadaného rozsahu. To je tedy první přednost systému pevné řádové tečky – pokud programátor dopředu zná rozsah všech zpracovávaných hodnot a požadovanou přesnost, může být výhodné tento systém použít. Programátor také díky explicitním určení polohy řádové tečky může určit, ve kterém místě programu se musí přesnost či rozsah zvýšit a kdy naopak snížit. Lépe se tak využije počet bitů, které můžeme pro uložení jednoho čísla obětovat (typicky je tento počet bitů roven délce slova mikroprocesoru, popř. jeho celočíselnému násobku či naopak podílu).

Jak se dozvíme v následujícím pokračování tohoto seriálu, je možné základní matematické operace (sčítání, odčítání, násobení a dělení) poměrně jednoduše implementovat i při použití formátu pevné řádové tečky. V případě, že není k dispozici specializovaný (a současně velmi komplikovaný) matematický koprocesor, je mnohdy mnohem jednodušší a rychlejší implementovat matematické operace v FX formátu. To je případ mnoha jednočipových mikroprocesorů (mikrořadičů), signálových procesorů, ale i specializovaných zařízení obsahujících programovatelné obvody CPLD či FPGA. Dnes sice mají komplikovanější (a dražší) FPGA implementovanou i jednotku FPU, ale mnohdy je výhodnější použít FPGA bez této jednotky a potřebné operace si do tohoto obvodu „vypálit“ po svém.

Třetí výhodou je fakt, že u FX formátu může programátor navrhnout a posléze také dodržet požadovanou přesnost všech prováděných výpočtů. To je velký rozdíl oproti FP formátu (resp. jeho podmnožinám, které se nejčastěji používají). Není vzácností narazit na programy, které používají datové typy float či double a přitom jsou výpočty prováděné v těchto programech zatíženy velkou chybou, protože si programátoři plně neuvědomují některé limity FP formátu. Kritické jsou například výpočty s peněžními hodnotami, ale i pouhé sčítání čísel, jež se od sebe o mnoho řádů liší, vede k velkým chybám, které dokonce mohou zapříčinit vznik nekonečných smyček, populární dělení nulou atd.

FX formát má však i některé nevýhody. První nevýhoda spočívá v tom, že tento formát není příliš podporován, a to ani po programové stránce (podpora v programovacích jazycích), ani výrobci mikroprocesorů pro počítače PC. Situace je však odlišná v oblasti jednočipových mikropočítačů, signálových procesorů (DSP), řídicích systémů, nebo například u IBM RS 6000, který kromě jednotky FPU obsahuje i FXU – jednotku pro provádění výpočtů v pevné řádové binární čárce. Na platformě x86 je možné pro FX formát použít instrukce MMX.

Dále může být použití FX formátu nevýhodné v případě, že se mají zpracovávat numerické hodnoty, které mají velkou dynamiku, tj. poměr mezi nejvyšší a nejnižší absolutní hodnotou. V takovém případě by se mohlo stát, že by se při použití FX formátu muselo pro každé číslo alokovat velké množství bitů, které by mohlo dokonce překročit počet bitů nutných pro FP formát. Také v případě, kdy dopředu nevíme, jaké hodnoty se budou zpracovávat, může být výhodnější použití FP formátu. Zde se však nabízí otázka, ve kterých případech nevíme, jaké hodnoty můžeme na vstupu získat: většinou je již z podstaty úlohy dopředu známé, s čím je možné počítat a které hodnoty jsou naprosto nesmyslné. Je však pravdou, že takovou analýzu málokdo dělá a když při výpočtech ve floatech dochází k chybám, tak se bez přemýšlení program přepíše na doubly a problém se tak buď odstraní, nebo alespoň odsune na pozdější dobu, například do chvíle, kdy jsou programu předložena reálná data a ne „pouze“ data testovací.

5. Uložení čísel ve formátu plovoucí řádové (binární) tečky

Uložení racionálních čísel ve formátu plovoucí řádové tečky (FP formát) se od FX formátu odlišuje především v tom, že si každá numerická hodnota sama v sobě nese polohu řádové tečky. Z tohoto důvodu je kromě bitů, které jsou rezervovány pro uložení významných číslic numerické hodnoty, nutné pro každou numerickou hodnotu rezervovat i další bity, pomocí nichž je určena mocnina o nějakém základu (typicky 2, 8, 10 či 16), kterou musí být významné číslice vynásobeny resp. vyděleny. První část čísla uloženého v FP formátu se nazývá mantisa, druhá část exponent. Obecný formát uložení a způsob získání původního čísla je následující:

xFP=be×m

kde:

  1. xFP značí reprezentovanou numerickou hodnotu z podmnožiny reálných čísel
  2. b je báze, někdy také nazývaná radix
  3. e je hodnota exponentu (může být i záporná)
  4. m je mantisa, která může být i záporná

Konkrétní formát numerických hodnot reprezentovaných v systému plovoucí řádové tečky závisí především na volbě báze (radixu) a také na počtu bitů rezervovaných pro uložení mantisy a exponentu. V minulosti existovalo mnoho různých formátů plovoucí řádové tečky (vzpomíná si někdo na Turbo Pascal s jeho šestibytovým datovým typem real?), dnes se však, ustálilo použití formátů specifikovaných v normě IEEE 754.

6. Formát plovoucí řádové binární tečky a norma IEEE 754

Norma IEEE 754 specifikuje nejenom vlastní formát uložení numerických hodnot v systému pevné řádové tečky, ale (a to je celkem neznámá skutečnost) i pravidla implementace operací s těmito hodnotami, včetně konverzí. Konkrétně je v této normě popsáno:

  1. Základní (basic) a rozšířený (extended) formát uložení numerických hodnot.
  2. Způsob provádění základních matematických operací: sčítání, odečítání, násobení, dělení, zbytek po dělení, druhá odmocnina a porovnání.
  3. Pravidla konverze mezi celočíselnými formáty (integer) a formáty s plovoucí řádovou tečkou.
  4. Způsob konverze mezi různými formáty s plovoucí řádovou tečkou.
  5. Způsob konverze základního formátu s plovoucí řádovou tečkou na řetězec číslic.
  6. Práce s hodnotami NaN (not a number) a výjimkami.

Touto normou se budeme podrobněji zabývat ve druhé části tohoto seriálu, zejména proto, že bude zapotřebí provádět převody mezi hodnotami v FP formátu a hodnotami v FX formátu.

7. Přednosti a zápory formátu plovoucí řádové tečky

Vzhledem k tomu, že je FP formát v současnosti velmi rozšířený a používaný, musí nutně přinášet některé výhody, jinak by jeho rozšíření nebylo zdaleka tak velké. První předností je podpora FP operací díky hardwarovým FPU jednotkám, které jsou dostupné jak ve formě samostatného matematického koprocesoru (Intel 8087, Intel i80287, Intel i80387, Intel i80487, Motorola M68881, Motorola M68882), tak i jako přímá součást moderních mikroprocesorů (řada x86 od „plnohodnotných“ mikroprocesorů i486, Motorola M68040, Power PC, některé typy mikrořadičů a signálových procesorů atd.). Další předností je existence normy IEEE 754, ve které je mimo jiné řečeno i to, že každá FPU jednotka by měla podporovat ideálně dva formáty, například basic single a basic double. To je velmi důležité, zejména pro přenos numerických údajů mezi různými zařízeními. Pro mnoho programátorů je také výhodné to, že jeden základní datový typ (například float) je možné použít pro reprezentaci mnoha objektů či vlastností (jak si však ukážeme v další části tohoto seriálu, ne vždy je tento předpoklad pravdivý). Všechny tyto skutečnosti vedly k tomu, že FP formát (či formáty) jsou v prakticky všech programovacích jazycích implementovány jako základní datové typy, což představuje velký náskok před FX formátem, který je podporován pouze několika málo jazyky a programovými knihovnami.

FP formát však má i některé zápory, které nás mohou v některých případech „donutit“ k použití formátu FX. První nevýhoda vychází z velké komplexnosti vlastního formátu, tj. způsobu rozdělení údajů na mantisu a exponent. I taková základní matematická operace, jako je součet, je díky FP formátu poměrně složitá a výsledek nemusí vždy odpovídat intuitivnímu cítění programátora, který má tendenci FP formát pokládat za ekvivalent reálných čísel („datový typ double je přesný…“). Mnoho programátorů se například chybně spoléhá na to, že i pouhý převod mezi typem int na single/float a zpět na int je bezeztrátový – pravý opak je pravdou a to vzhledem k tomu, že se ztratí hodnoty minimálně osmi nejnižších bitů, které musely být vyhrazeny pro uložení exponentu. FP formát, resp. formát specifikovaný normou IEEE 754, se nehodí pro práci s peněžními hodnotami; z tohoto důvodu se v některých vyšších programovacích jazycích zavádí speciální datový typ decimal resp. currency, určený specielně pro peněžní hodnoty.

Další nedostatek FP formátu souvisí s jeho značnou komplexností. Hardwarové jednotky FPU jsou velmi komplikované, což limituje použití FP operací v některých vestavných – embedded – zařízeních (těch je dnes řádově více než osobních počítačů), ale i v dnes oblíbených smartphonech atd. Tím neříkám, že některé mikroprocesory použité ve smartphonech FPU nemají, bylo by ale zajímavé zjistit, zda by ty statisíce logických hradel použitých na implementaci FPU nešly využít jiným způsobem. Dále se komplikuje a především zpomaluje převod mezi FP formáty a celočíselnými formáty dat (integer, long). Z tohoto důvodu jsou například mnohé signálové procesory zkonstruovány tak, aby podporovaly pouze FX aritmetiku, protože jak na vstupu signálového procesoru, tak i na jeho výstupu jsou prakticky vždy celočíselné hodnoty a pouze převody mezi vstupem, interní reprezentací a výstupem by byly mnohdy komplikovanější než implementace veškerých výpočtů v FX reprezentaci.

UX DAy - tip 2

8. Literatura a odkazy na Internetu

  1. Yates Randy: Fixed-Point Arithmetic: An Introduction,
    Digital Sound Labs, March 3, 2001
  2. Hook Brian: An Introduction to Fixed Point Math,
    Game Design and Review, 2003
  3. P. Mikulec, M. Vojtíšek: Procesor IBM RS 6000,
    http://petam.chy­trak.cz/skola/RS6000
  4. Wikipedia: Fixed-point arithmetic,
    http://en.wiki­pedia.org/wiki/Fi­xed-point_arithmetic
  5. Wikipedia: Floating point,
    http://en.wiki­pedia.org/wiki/Flo­ating_point
  6. Wikipedia: IEEE floating-point standard,
    http://en.wiki­pedia.org/wiki/I­EEE_Floating_Po­int_Standard

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

V následujícím pokračování tohoto seriálu si podrobně popíšeme formáty uložení specifikované pomocí normy IEEE 754, včetně způsobu provádění všech základních matematických operací.

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