Interní reprezentace numerických hodnot: od skutečného počítačového pravěku po IEEE 754–2008 (dokončení)

Obsah

1. Interní reprezentace numerických hodnot: od skutečného počítačového pravěku po IEEE 754–2008 (dokončení)

2. Norma IEEE 754 a IEEE 754–2008

3. Vliv existence IEEE 754 na další vývoj IT

4. Varianta single – hodnoty s jednoduchou přesností

5. Varianta double – hodnoty s dvojnásobnou přesností

6. Denormalizovaná čísla, hodnoty typu NaN a nekonečna

7. Rozšířený formát extended/temporary

8. Varianta quadruple – hodnoty se čtyřnásobnou přesností

9. Varianta octuple – 256 bitů pro jedno číslo

10. Varianta half – poloviční přesnost

11. Další „malé“ FP varianty

12. Použití BCD pro uložení čísel i pro výpočty

13. Podpora pro výpočty v BCD v instrukčních sadách mikroprocesorů

14. Od BCD ke kódování EBCDIC

15. Formáty s plovoucí řádovou čárkou s bází rovnou deseti

16. Příklad FP s bází rovnou deseti: Packed Decimal u mikroprocesorů Motorola 68000

17. „Komprimované“ formáty založené na BCD aneb jak uložit tři číslice do deseti bitů

18. Formáty decimal32, decimal64 a decimal128

19. Alternativní formát uložení čísel – zlomky (rational)

20. Odkazy na Internetu

1. Interní reprezentace numerických hodnot: od skutečného počítačového pravěku po IEEE 754–2008 (dokončení)

V první části článku o způsobech reprezentace numerických hodnot jsme se seznámili především s různými variantami použití plovoucí řádové čárky (FP – floating point), což je formát, který byl poměrně masivně používán už na první generaci elektronkových mainframů firmy IBM. Dále jsme si řekli, jak byly numerické hodnoty reprezentovány na některých starších počítačích popř. v knihovnách různých jazyků – Sinclair BASICu, Atari BASICu, Turbo Pascalu atd. Dnes toto poměrně rozsáhlé téma dokončíme. Nejdříve si popíšeme základní formáty definované v normě IEEE 754 (ty ostatně většina programátorů používá prakticky každý den), dále se zmíníme o rozšířených formátech (nazývanými poněkud nepřesně „half precision“, „double extended/temporary“, „quadruple precision“, „octuple precision“), o takzvaných „malých“ FP formátech a samozřejmě nezapomeneme ani na formáty používající BCD, ať již v původní formě, tak i v komprimované podobě.

Obrázek 1: Superpočítač CDC 7600, který lze považovat za předchůdce superpočítačů CRAY. Tyto stroje byly optimalizovány na výpočty, nikoli například na hromadné zpracování dat. Právě v souvislosti se superpočítači CRAY se začala objevovat zkratka MFLOPS (později GFLOPS) udávající rychlost FP výpočtů.

Tabulku s různými formáty numerických hodnot si rozšíříme o další varianty:

Poznámka: pro připomenutí – pokud je ve sloupci Mantisa napsána hodnota n+1, znamená to, že hodnoty jsou normalizovány tak, aby první bit mantisy byl vždy jedničkový. V takovém případě tento bit nemusíme nikam zapisovat (víme, že je jednička) a tudíž se mantisa automaticky o tento jeden bit rozšiřuje. To samozřejmě neplatí pro denormalizované hodnoty (blízké nule).

Obrázek 2: Některé typy programových smyček optimalizovaných překladačem FORTRANu 77 pro počítače Cray-2. Většina optimalizací byla umožněna použitím vektorů s FP hodnotami.
(zdroj: materiály firmy Cray Research)

2. Norma IEEE 754 a IEEE 754–2008

Důležitým milníkem v reprezentaci reálných čísel se stala norma IEEE 754, která se používá u naprosté většiny polovodičových čipů vyrobených v posledním čtvrtstoletí. V normě IEEE 754, jejíž první verze je mimochodem v platnosti již od roku 1985, jsou specifikovány nejenom vlastní formáty uložení numerických hodnot v systému pohyblivé řádové čárky (FP formátu), ale i pravidla implementace základních aritmetických operací s těmito hodnotami, aplikace zaokrouhlovacích režimů, způsoby některých konverzí apod. 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í:
   • součet
   • rozdíl
   • součin
   • podíl
   • zbytek po dělení
   • druhá odmocnina
   • porovnání
3. Režimy zaokrouhlování.
4. Způsob práce s denormalizovanými hodnotami.
5. Pravidla konverze mezi celočíselnými formáty (integer bez a se znaménkem) a formáty s plovoucí řádovou čárkou.
6. Způsob konverze mezi různými formáty s plovoucí řádovou čárkou (single → double atd.).
7. Způsob konverze základního formátu s plovoucí řádovou čárkou na řetězec číslic (včetně nekonečen a nečíselných hodnot).
8. Práce s hodnotami NaN (not a number) a výjimkami, které mohou při výpočtech za určitých předpokladů vzniknout.

Obrázek 3: Mezi nabídkou datových typů pro FP hodnoty Turbo Pascalu 7 nalezneme i typ comp. Ten odpovídá 64bitovým celým číslům (integer), ovšem výpočty s typem comp jsou prováděny v matematickém koprocesoru a nikoli v ALU (ta ostatně byla jen šestnáctibitová).

Podle bitové šířky čísel exp, bias a m se rozlišují základní (basic) a rozšířené (extended) formáty FP čísel; norma IEEE 754 (její původní verze) přitom explicitně zmiňuje dva základní formáty: jednoduchá přesnost (single) a dvojitá přesnost (double). Druhá verze normy IEEE 754–2008 již obsahuje specifikaci většího množství formátů; navíc došlo k přejmenování typů single a double na binary32 a binary64:

Obrázek 4: První čip, který používal formát definovaný v IEEE 754 – Intel 8087.
Zdroj: Wikipedia, Autor: Dirk Oppelt

3. Vliv existence IEEE 754 na další vývoj IT

Podpora vybraných formátů definovaných v IEEE 754 popř. v IEEE 754–2008 je dnes prakticky univerzální a nezávislá na procesorové architektuře a/nebo operačním systému. V minulosti byly FP operace podporovány v samostatných matematických koprocesorech neboli FPU – Floating Point Units. Jednalo se především o čipy Intel 8087, Intel i80287, Intel i80387, Intel i80487, Motorola M68881 a Motorola M68882. Dnes je FPU většinou přímo součástí moderních mikroprocesorů (řada x86 od „plnohodnotných“ mikroprocesorů i486, Motorola M68040, Power PC, ARMy, AArch64, RISC-V, SPARC některé typy mikrořadičů a signálových procesorů atd. (naproti tomu například TMS320C30 vyžaduje konvertor).

Obrázek 5: Mikroprocesory Pentium i všechny další čipy řady 80×86 již implicitně obsahují plnohodnotný FPU. Zlé jazyky tvrdí, že u první řady Pentií byl FPU tak rychlý jen proto, že výsledky pouze odhadoval :-)

Díky široké podpoře IEEE 754 se zjednodušil 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í. 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.

Obrázek 6: Interní struktura mikroprocesorů Itanium. Asi nás nepřekvapí červeně označené bloky s FPU (dvě jednotky) a jeho registry.

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í nějaké alternativy. 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 kvůli 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 int32 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 (dtto pro int64 a double). 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ý speciálně pro peněžní hodnoty – viz další kapitoly.

Obrázek 7: Interní struktura novějších verzí mikroprocesorů s architekturou SPARC, na níž můžeme najít jak moduly pro práci s celými čísly, tak i moduly FPU.

4. Varianta single – hodnoty s jednoduchou přesností

Tento formát, který je v programovacích jazycích označován buď jako single či float, je charakteristický tím, že se pro uložení numerické hodnoty používá třiceti dvou bitů (4 byty), což pro mnoho aplikací představuje velmi dobrý poměr mezi rozsahem hodnot, přesností a nároky na úložný prostor, nehledě na to, že mnoho architektur stále používá 32bitové sběrnice (klasické ARMy, …). Oněch 32 bitů je rozděleno do třech částí. V první části (představované nejvyšším bitem) je uloženo znaménko, následuje osm bitů pro uložení posunutého exponentu a za nimi je zbývajících 23 bitů, které slouží pro uložení mantisy. Celé třiceti dvoubitové slovo s FP hodnotou tedy vypadá následovně:

Exponent je přitom posunutý o hodnotu bias, která je nastavena na 127, protože je použit výše uvedený vztah:

bias=2^eb-1-1

a po dosazení eb=8 (bitů) dostaneme:

bias=2^8–1-1=2⁷-1=128–1=127

Vzorec pro vyjádření reálné hodnoty vypadá následovně:

X_single=(-1)^s × 2^exp-127 × m

Uložení znaménka číselné hodnoty je jednoduché: pokud je znaménkový bit nastavený na jedničku, jedná se o zápornou hodnotu, v opačném případě jde o hodnotu kladnou. Exponent je uložený v takzvané posunuté formě, tj. jako binárně zakódované celé číslo v rozsahu 0..255. Po vyjádření neposunutého exponentu dostáváme rozsah –127..128, obě krajní hodnoty jsou však použity pro speciální účely, proto dostáváme rozsah exponentů pouze –126..127 pro normalizovaná čísla (krajními hodnotami jsou takové exponenty, které mají všechny bity buď jedničkové nebo naopak nulové).

Obrázek 8: Matematický koprocesor vyráběný firmou Weitek. Tento konkrétní čip je určen pro procesory řady 486 (není kompatibilní s 80487), ovšem Weitek vyráběl koprocesory pro celou řadu dalších architektur, od 8087 přes Motoroly řady 68k až po (micro)SPARC.

Ještě si však musíme říci, jakým způsobem je uložena mantisa. Ta je totiž většinou (až na velmi malá čísla) normalizovaná, což znamená, že se do mantisy ukládají pouze hodnoty v rozsahu <1,0;2,0-ε>. Vzhledem k tomu, že první bit umístěný před binární tečkou je u tohoto rozsahu vždy nastavený na jedničku, není ho zapotřebí ukládat, což znamená, že ušetříme jeden bit z třiceti dvoubitového slova (viz úvodní kapitolu). Pro normalizované hodnoty platí následující vztah:

X_single=(-1)^s × 2^exp-127(1.M)₂

kde M je hodnota bitového vektoru mantisy, tj.:

M=m₂₂^-1+m₂₁^-2+m₂₀^-3+…+m₁^-22+m₀^-23

Rozsah hodnot, které je možné reprezentovat ve formátu jednoduché přesnosti v normalizovaném tvaru je –3,4×10³⁸ až 3,4×10³⁸. Nejnižší reprezentovatelná (normalizovaná) hodnota je rovna 1,17549×10^-38, denormalizovaná pak 1,40129×10^-45. Jak jsme k těmto hodnotám došli? Zkuste se podívat na následující vztahy:

5. Varianta double – hodnoty s dvojnásobnou přesností

Formát s dvojitou přesností (double), který je definovaný taktéž normou IEEE 754, se v mnoha ohledech podobá formátu s jednoduchou přesností (single), pouze se zdvojnásobil celkový počet bitů, ve kterých je hodnota uložena, tj. místo 32 bitů se používá 64 bitů. Právě to je hlavní příčinou toho, proč se tento formát nazývá double, ve skutečnosti je totiž přesnost více než dvojnásobná. 64 bitů alokovaných pro FP hodnotu je v tomto případě rozděleno následujícím způsobem:

1. 1 bit pro znaménko
2. 11 bitů pro exponent
3. 52 bitů pro mantisu

Bitově vypadá rozdělení následovně:

Exponent je v tomto případě posunutý o hodnotu bias=2047 a vzorec pro výpočet reálné hodnoty vypadá takto:

X_double=(-1)^s × 2^exp-2047 × m

Přičemž hodnotu mantisy je možné pro normalizované hodnoty získat pomocí vztahu:

m=1+m₅₁^-1+m₅₀^-2+m₄₉^-3+…+m₀^-52

(m_x představuje x-tý bit mantisy)

Rozsah hodnot ukládaných ve dvojité přesnosti je –1,7×10³⁰⁸..1,7×10³⁰⁸, nejmenší možná nenulová hodnota je rovna 2,2×10^-308.

6. Denormalizovaná čísla, hodnoty typu NaN a nekonečna

Ještě si musíme vysvětlit význam těch exponentů, které mají minimální a maximální hodnotu, tj. jsou buď nulové, nebo mají v případě formátu single hodnotu 255 (obě samozřejmě před posunem). Vše je přehledně uvedeno v následující tabulce:

Pojmem denormalizovaná čísla označujeme takové hodnoty, u kterých není první (explicitně nevyjádřený) bit mantisy roven jedničce, ale naopak nule. Výpočty s těmito velmi malými hodnotami nejsou přesné, zejména při násobení a dělení (a samozřejmě i všech odvozených operacích). Při ukládání denormalizovaných čísel je exponent vždy nastaven na nejnižší hodnotu, tj. na –126 a nejvyšší (explicitně neukládaný) bit mantisy je vždy nulový, nikoli jedničkový, jak je tomu u normalizovaných hodnot.

Hodnota typu NaN vznikne v případě, že je použita operace s nejasným výsledkem, například 0/0 nebo, a to v praxi snad nejčastěji, při odmocňování záporných čísel. Nekonečná hodnota vzniká typicky při dělení nulou (zde je možné zjistit znaménko), nebo při vyjádření funkcí typu log(0) atd.

Minimální a maximální hodnota exponentu má speciální význam i u formátu double:

7. Rozšířený formát extended/temporary

Kromě obou základních formátů (tj. jednoduché i dvojité přesnosti) je v normě IEEE 754 povoleno používat i rozšířené formáty. Na platformě x86 je při výpočtech prováděných v FPU používán rozšířený formát nazývaný extended či temporary. Tento formát je zajímavý tím, že pro uložení FP hodnot používá 80 bitů a je do něho možné beze ztráty přesnosti uložit 64bitové hodnoty typu integer (přesně taková je totiž bitová šířka mantisy). Osmdesátibitový vektor je rozdělený do třech částí následujícím způsobem:

• 1 bit pro znaménko
• 15 bitů pro exponent (BIAS je roven 16383)
• 64 bitů pro mantisu (maximální hodnota přesahuje 10⁴⁹³²)

U tohoto formátu je zajímavá funkce bitu s indexem 63. Podle hodnoty tohoto bitu se rozlišují čísla normalizovaná a nenormalizovaná (tento bit ve skutečnosti nahrazuje implicitně nastavovaný nejvyšší bit mantisy, jak ho známe z předchozích formátů). Matematický koprocesor 8087 sice dokáže pracovat s čísly nenormalizovanými, výsledkem jeho aritmetických operací jsou však vždy hodnoty normalizované. Všechny možnosti, které mohou při ukládání extended FP formátu nastat, jsou přehledně vypsány v následující tabulce:

Pro normalizované i nenormalizované hodnoty je možné uloženou hodnotu vyjádřit pomocí vzorce (všimněte si, že bit 63 je umístěn před binární tečkou):

X_extended=(-1)^s × 2^exp-16383 × m

m=m₆₃⁰+m₆₂^-1+m₆₁^-2+…+m₀^-63

8. Varianta quadruple – hodnoty se čtyřnásobnou přesností

„For now the 10-byte Extended format is a tolerable compromise between the value of extra-precise arithmetic and the price of implementing it to run fast; very soon two more bytes of precision will become tolerable, and ultimately a 16-byte format… That kind of gradual evolution towards wider precision was already in view when IEEE Standard 754 for Floating-Point Arithmetic was framed.“
William Kahan, architekt IEEE 754

Rozšiřování šířky mantisy i možných rozsahů exponentu se nezastavilo u výše popsaného formátu extended. Ostatně formát extended byl již v době svého vzniku pouze dočasným řešením, protože tehdejší technologie neumožňovala, aby matematický koprocesor 8087 obsahoval příliš mnoho tranzistorů (jednalo by se o drahé řešení, navíc zvýšení počtu tranzistorů vedlo k menší výtěžnosti výroby, což opět vede ke zdražení). V novější normě IEEE 754–2008 je specifikován nepovinný formát nazvaný binary128, který se ovšem běžně označuje quadruple precision či jen quad precision. Tento formát je založen na slovech širokých 128 bitů (16 bajtů), která jsou rozdělena takto:

1. 1 bit pro znaménko
2. 15 bitů pro exponent
3. 112 bitů pro mantisu

Bitově vypadá rozdělení následovně:

Exponent je v tomto případě posunutý o hodnotu bias=16383. Dekadická přesnost u tohoto formátu dosahuje 34 cifer!

Formát quadruple je podporován těmi procesory s architekturou RISC-V, které implementují rozšíření instrukční sady „Q“. Toto rozšíření je platné pouze pro 64bitové varianty procesorů, které obsahují sadu RV64I (u 32bitových variant CPU nebude „Q“ podporována). V rámci podpory rozšíření instrukční sady „Q“ se zvětšila šířka FP registrů, a to na 128 bitů. Většina původních FP instrukcí zůstala zachována, pouze se změnil jejich postfix určující typ zpracovávaných numerických hodnot. Jediné instrukce, které byly odstraněny, jsou instrukce pro bitovou kopii dat mezi celočíselným registrem a FP registrem (to je vlastně pochopitelné), což znamená nutnost načítání a ukládání operandů přímo do operační paměti. V instrukční sadě „Q“ tedy neexistují tyto dvě instrukce: FMV.X.Q a FMV.Q.X.

Nové instrukce pro načítání a ukládání operandů do operační paměti:

Základní aritmetické operace jsou (opět) prakticky stejné, pouze mají odlišný postfix:

Konverze mezi typy single, float a quadruple:

Operace se znaménkem:

9. Varianta octuple – 256 bitů pro jedno číslo

Jen krátce se zmiňme o poslední variantě FP formátu, který se nazývá binary256 či méně formálně octuple precision. Tento formát využívá slova o šířce plných 256 bitů (32 bajtů) s následujícím rozdělením:

1. 1 bit pro znaménko
2. 19 bitů pro exponent
3. 236 bitů pro mantisu

(povšimněte si, že šířka exponentu nemusí růst nijak radikálně)

Bitově vypadá rozdělení následovně:

Exponent je v tomto případě posunutý o hodnotu bias=262143. Dekadická přesnost u tohoto formátu dosahuje 71 cifer, nejmenší (nenormalizovaná) reprezentovatelná hodnota rozdílná od nuly je přibližně 10⁻⁷⁸⁹⁸⁴, maximální hodnota pak 1.611 ×10⁷⁸⁹¹³ (těžko říct, zda je takový rozsah vůbec reálně využitelný).

10. Varianta half – poloviční přesnost

Formát Minifloat je významný tím, že je implementován v některých grafických procesorech GPU; používají ho i firmy ILM a Pixar atd. Tento formát, někdy (zejména v programovacím jazyku Cg) také nazývaný half či jednoduše fp16, používá pro ukládání FP hodnot pouhých šestnáct bitů, tj. dva byty. Maximální hodnota je rovna 65504 (FFE0₁₆=1111111111100000₂), minimální hodnota přibližně 2,9×10^-8. Předností tohoto formátu je malá bitová šířka (umožňuje paralelní přenos po interních sběrnicích GPU) a také větší rychlost zpracování základních operací, protože pro tak malou bitovou šířku mantisy je možné některé operace „zadrátovat“ a nepočítat pomocí ALU. Také některé iterativní výpočty (sin, cos, sqrt) mohou být provedeny rychleji, než v případě plnohodnotných typů float a single.

Tento formát nalezneme v některých programovacích jazycích a knihovnách určených pro zpracování velkého množství numerických údajů. Příkladem je programovací jazyk Julia s datovým typem Float16 či populární knihovna Numpy s datovým typem s prakticky totožným názvem float16.

Logo programovacího jazyka Julia.

11. Další „malé“ FP varianty

Nejmenším FP formátem, který je ještě možné prakticky použít, je formát neoficiálně nazývaný microfloat. Tento formát, ve kterém jsou hodnoty uložené na pouhých osmi bitech, tj. jednom bytu, se používá například při ukládání hodnot naměřených z nelineárních čidel, digitálních průběhů apod. Předností je značná úspora paměti a také snazší FP operace, které je možné povětšinou zakódovat do vyhledávacích tabulek (na mikrořadičích do paměti PROM). Nevýhodou je (logicky) malý rozsah a současně i přesnost. Kromě normalizovaných číselných hodnot (nejmenší hodnotou je 1/64) je možné ukládat i hodnoty nenormalizované (zde je nejmenší hodnotou 1/512), přičemž je možné odlišit kladnou a zápornou nulu a samozřejmě i kladné a záporné nekonečno. Základní charakteristika tohoto opravdu minimalistického FP formátu je zobrazena v následující tabulce:

Poznámka: pokud se tento formát používá pro přenos naměřených dat z čidel atd., většinou se nepracuje ani s nenormalizovanými hodnotami ani se speciálními (ne)čísly typu NaN či ±∞

Na některých univerzitách se používá ještě menší FP formát s šířkou pouhých šesti bitů. V tomto formátu je jeden bit vyhrazen pro znaménko (logicky), tři bity pro exponent (s biasem 3) a pouhé dva bity pro mantisu. K čemu je takový formát vlastně dobrý? Šesti bity je možné reprezentovat pouze 64 stavů a ty lze snadno namapovat na reálné hodnoty vynesené na číselnou osu. Pokud se u tohoto formátu dodrží všechny mechanismy specifikované v IEEE 754, lze pracovat s hodnotami NaN, +∞, -∞ atd., testovat, za jakých okolností dochází k přetečení, kdy se snižuje přesnost výsledku atd. To, že je mantisa uložena jen ve dvou bitech vůbec nevadí, spíš naopak (zmenšuje se stavový prostor).

Další „mini-FP“ formát používá pouze pět bitů, přičemž dva bity jsou vyhrazeny na exponent a tři na mantisu (bez znaménka). Tento formát se používá na PC pro nastavení rychlosti automatického opakování znaků při držení klávesy. Všech 32 kombinací pěti bitů je převedeno na hodnoty od 8 do 120. Na tomto formátu lze dobře ilustrovat vlastnost všech FP formátů – čím vyšší hodnoty používáme, tím větší krok je mezi dvěma sousedními hodnotami:

12. Použití BCD pro uložení čísel i pro výpočty

Při popisu různých způsobů uložení numerických hodnot nesmíme zapomenout na BCD (Binary-coded decimal), tedy na systém uložení každé desítkové cifry ve čtyřech bitech. Typicky se tedy do jednoho bajtu mohou uložit dvě cifry, do 16bitového slova čtyři cifry, do 32bitového slova osm cifer atd. BCD se v nejjednodušším případě používá pro uložení celých čísel, a to buď bez znaménka (jednotlivé cifry) nebo se znaménkem (potom je znaménko typicky uloženo ve vlastním bitu, nebo se používá dvojkový doplněk, to ovšem méně často). Ovšem můžeme se setkat i s takzvaným FX formátem (fixed point), v němž je desetinná tečka umístěna za předem známou cifrou a je neměnná – počet cifer před desetinnou tečkou a za ní je stále stejný. To znamená, že se v takovém případě nemusí ukládat exponent, který u výše popsaných FP hodnot přímo či nepřímo určoval pozici řádové čárky v uloženém číslu.

13. Podpora pro výpočty v BCD v instrukčních sadách mikroprocesorů

Výpočty s číselnými hodnotami uloženými v kódu BCD se ve výpočetní technice používají již od první generace (elektronkových) mainframů, které společnost IBM vyráběla v padesátých letech minulého století. Dnes se s BCD setkáme například při programování mikrořadičů, protože některé sedmisegmentové LCD, čipy s hodinami reálného času či malé numerické klávesnice kód BCD používají. Ostatně i z tohoto důvodu výpočty v BCD podporuje většina mikrořadičů, s výjimkou některých řad osmibitových mikrořadičů PIC. Čipy podporující výpočty v BCD můžeme rozdělit do tří kategorií:

1. Registry přímo obsahují BCD (typicky dvě číslice 00–99) a ALU taktéž produkuje výsledek v BCD. Typickým příkladem je slavný osmibitový mikroprocesor MOS 6502, který lze přepnout do „dekadického režimu“ instrukcí SED (Set Decimal Mode) či se přepnout zpátky instrukcí CLD (Clear Decimal Mode).
2. ALU sice provádí výpočty v binárním kódu, ale po provedení výpočtu je možné explicitně provést úpravu výsledku na BCD (na základě nastavených příznaků přenosu a polovičního přenosu). Typickým příkladem jsou čipy Intel 8048, Intel 8051, Motorola 6809, Motorola 68HC11 atd. atd. s instrukcí DAA či DA A používanou po operaci součtu a rozdílu. Podobná je instrukce A6AAC u čtyřbitových mikrořadičů TMS-1000.
3. ALU provádí většinu operací v binárním režimu, ovšem některé instrukce ji mohou přepnout do režimu BCD. Příkladem je Motorola 68000 s instrukcemi ABCD (Add Binary Coded Decimal), NBCD (Negate Binary Coded Decimal) a SBCD (Subtract Binary Coded Decimal).

Obrázek 9: Jedna z typických nasazení čtyřbitových mikrořadičů – nejjednodušší kalkulačky .

Některé mikroprocesory obsahují větší množství instrukcí pro úpravu výsledku a/nebo vstupních operandů. Příkladem může být čip 8086 (s instrukční sadou udržovanou dodnes), podporující jak „packed BCD“ (dvě cifry v bajtu), tak i „unpacked BCD“ (jediná cifra v bajtu). V instrukční sadě nalezneme hned šest relevantních instrukcí:

BCD používá i matematický koprocesor x86 (konkrétně čip 8087 a kvůli zpětné kompatibilitě i dnešní CPU+FPU), který dokáže do osmdesáti bitového slova uložit 18 BCD cifer + znaménko (necelé dva bajty se přitom nevyužijí).

Obrázek 10: Segmentem, v němž se BCD používá dodnes, jsou kalkulačky.

14. Od BCD ke kódování EBCDIC

S kódem BCD poměrně úzce souvisí i kódování znaků EBCDIC neboli Extended Binary Coded Decimal Interchange Code. Firma IBM toto kódování vytvořila v letech 1963–1964 v návaznosti na šestibitový kód využívaný u děrných štítků a použila ho u počítačů System/360. Vzhledem k velké popularitě těchto počítačů se kódování EBCDIC i přes jeho mnohé nevýhody (především v porovnání s kódováním ASCII) rozšířilo i na další počítače a jejich operační systémy, například OS/390, z/OS, OS/400 i některé počítačové systémy firem HP či Unisys. V předchozím textu bylo napsáno, že EBCDIC má v porovnání s dnes mnohem častěji používaným kódem ASCII několik nevýhod. Některé z těchto nevýhod si popíšeme v následujícím textu.

Obrázek 11: Architektura počítačů System/360.

EBCDIC je založen na reprezentaci znaků pomocí osmi bitů, což představuje rozdíl oproti sedmibitovému ASCII, i když celkový počet znaků (včetně řídicích kódů) je zhruba stejný – pokrývá totiž potřeby anglického jazyka. Alfanumerické i další znaky však nejsou v tabulce všech 256 kombinací umístěny v přirozené posloupnosti (26 znaků velké abecedy, 26 znaků malé abecedy atd.), ale spíše po skupinách čítajících devět či deset znaků, což je patrné z části této tabulky vypsané na konci kapitoly (rozdíl mezi malými a velkými písmeny však spočívá v negaci jednoho bitu, stejně jako v případě ASCII). Nepravidelnost při tvorbě tabulky představovala pro programátory problém, protože například nebylo jednoduché vygenerovat posloupnost všech písmen, nešlo jednoduše zjistit, zda je nějaký znak platným písmenem (v ASCII záležitost dvou porovnání), EBCDIC se dal hůře zapamatovat (kupodivu i dnes je alespoň základní znalost ASCII pro programátory velkou výhodou) atd.

Navíc se při požadavku na rozšíření základní tabulky o další znaky (například písmen s akcenty, řeckou abecedu, azbuku atd.) musely tyto znaky přidávat na volné pozice rozmístěné po celé tabulce, na rozdíl od sedmibitového kódu ASCII, který bylo možné celkem jednoduše rozšířit přidáním osmého bitu – ostatně přesně tímto způsobem vzniklo například populární kódování Kamenických, kódování dle normy ISO 8859–2 i mnoho dalších kódování, u nichž byl prakticky vždy zachován význam prvních 128 kódů odpovídajících ASCII (jednou z výjimek je kódování použité u jehličkových tiskáren Epson, u nichž se některé znaky s akcenty vkládaly do prvních 128 pozic na místo hranatých závorek a několika dalších znaků, které se v běžně psaném textu vyskytují v malém množství). Z výše zmíněných důvodů nebylo kódování EBCDIC mezi programátory příliš oblíbeno, i když se ho firma IBM kvůli zachování zpětné kompatibility drží prakticky až do dnešní doby.

Povšimněte si, jak je v EBCDIC schován kód BCD – jedná se o poslední řádek s prefixem F-, tj. číslice jsou reprezentovány takto: 1111+BCD:

Obrázek 12: Některá úložná zařízení sálových počítačů firmy IBM – v pozadí jednotky magnetických pásek, v popředí diskové jednotky.

15. Formáty s plovoucí řádovou čárkou s bází rovnou deseti

Již minule jsme se seznámili s poněkud neobvyklým formátem čísel s plovoucí řádovou čárkou, který byl používaný u osmibitových mikropočítačů Atari. Připomeňme si, že se u tohoto formátu používala báze rovna hodnotě 100 (a nikoli 2 či 16, což je u počítačů častější), navíc byla hodnota mantisy uložena pomocí BCD kódu. Tento formát je skutečně v oblasti mikropočítačů poněkud neobvyklý, ovšem poněkud častěji se můžeme setkat s použitím FP formátu, v němž je báze reprezentována hodnotou 10.

Tento formát velmi často nalezneme i u kalkulaček, navíc kombinovaný s mantisou uloženou v BCD. Například slavná HP-35 používá vlastně velmi podobný formát, jako již zmíněné osmibitové mikropočítače Atari, ovšem s mnohem větší přesností:

• Exponent je uložen jako dvojice BCD číslic, může tedy mít hodnotu 0 .. 99 (to je obvyklé u většiny kalkulaček).
• Mantisa je uložena jako deset BCD číslic (jednodušší kalkulačky mají jen osm BCD číslic).
• Další dva čtyřbitové „nibbly“ jsou použity pro uložení znaménka mantisy a exponentu (zde se poněkud plýtvá místem).

Celkově je jedno číslo uloženo v 56 bitech (14×4), což sice může vypadat jako plýtvání místem, ovšem musíme si uvědomit, že kalkulačky pracují pouze se dvěma či třemi registry, popř. u HP se zásobníkem se čtyřmi prvky. Použití báze nastavené na 10 a BCD má své výhody, především není nutné složitě kódovat vstup od uživatele na interní reprezentaci a naopak výsledky dekódovat zpět na displej (nehledě na to, že u báze rovné deseti je zcela přesně známá přesnost vyjádřená v počtu desetinných míst).

16. Příklad FP s bází rovnou deseti: Packed Decimal u mikroprocesorů Motorola 68000

U slavných mikroprocesorů Motorola 68000 se můžeme setkat s formátem nazvaným Packed Decimal (který ovšem nemůže být přímo zpracováván – je nutné použít k tomu určené subrutiny). Tento formát vychází z formátu, který jsme si popsali v předchozí kapitole, ovšem je zvětšen rozsah hodnot i jejich přesnost. Pro uložení numerické hodnoty se používají tři 32bitová slova, tedy dohromady dvanáct bajtů. Exponent je reprezentován třemi dekadickými ciframi (BCD), exponent pak sedmnácti dekadickými ciframi, přičemž jedna cifra je umístěna před desetinnou čárkou, dalších šestnáct cifer za touto čárkou:

V nejvyšším nibble prvního slova se nachází příznaky speciálních hodnot (+∞, -∞, NAN, +0, –0), znaménko mantisy (SM) i znaménko exponentu (SE),

17. „Komprimované“ formáty založené na BCD aneb jak uložit tři číslice do deseti bitů

Samotný BCD není příliš úsporný. Představme si, že máme pracovat s desítkovými hodnotami 0 až 999. Pokud použijeme BCD, budeme pro každou hodnotu potřebovat 12 bitů (3 cifry × 4 bity), zatímco při použití klasického binárního kódu nám bude stačit bitů 10 (2¹⁰ = 1024 > 1000). Aby se tento problém eliminoval, bylo vymyšleno několik způsobů „komprimace“ BCD číslic takovým způsobem, aby bylo možné reprezentovat trojici desítkových cifer v pouhých deseti bitech. Delší čísla se pak jednoduše získají skládáním trojice cifer za sebe. Existuje hned několik variant tohoto řešení, z nichž nejznámější je formát DPD (Densely Packed Decimal), jehož jednodušší varianta byla navržena Chen–Ho(em).

V Chen-Hoově kódování, které je velmi elegantní, se desítková čísla 0 až 999 rozdělují do několika skupin, přičemž každá skupina se kóduje odlišným způsobem:

Poznámka: xxx lze považovat za zkrácený BCD, který dokáže reprezentovat cifru 0–7 (osm stavů). y je jediný bit, který rozlišuje mezi cifrou 8 a 9.

18. Formáty decimal32, decimal64 a decimal128

Na DPD (Densely Packed Decimal) jsou založeny formáty decimal32, decimal64 a decimal128, které jsou taktéž popsány v normě IEEE 754–2008. Základní vlastnosti těchto formátů jsou shrnuty v následující tabulce:

Kvůli implicitnímu umístění desetinné tečky za první cifru jsou rozsahy nejmenší (nenulové) hodnoty a největší hodnoty následující:

Poznámka: kódování je symetrické, takže největší kladná a nejmenší záporná hodnota se liší pouze znaménkem.

Kromě běžných hodnot existují i bitové kombinace pro NaN, +∞ i pro -∞.

19. Alternativní formát uložení čísel – zlomky (rational)

V mnoha programovacích jazycích odvozených od LISPu se setkáme s podporou zlomků; tento formát se většinou nazývá rational či jen ratio. Se zlomky lze pracovat například v jazyce Clojure, ve Scheme i v jazyku Pixie odvozeném od Clojure. Konkrétní implementace zlomků se v různých jazycích od sebe odlišuje. Většinou se jedná buď o dvojici celých čísel (například 32bitových integerů) nebo o dvojici hodnot typu big integer, které mají neomezený rozsah. Ostatně právě tato reprezentace je použita v jazyku Clojure pro jeho datový typ Ratio. Se zlomky se v LISPovských jazycích pracuje jednoduše, protože zápis x/y znamená skutečně zápis zlomku a nikoli násobení (to se zapisuje prefixovou funkcí). Většina výpočtů provádí automatické zjednodušování zlomků:

(/ 1 2)
1/2

(/ 1 2 3)
1/6

(/ 3 2)
3/2

(/ (+ 1 2) (+ 3 4))
3/7

(+ 1/2 (* 3/4 (/ 5/6 7/8)))
17/14

Převod na zlomek si můžeme i vynutit konverzní funkcí, ovšem výsledek samozřejmě nebude přesný, protože není přesný samotný vstup do konverzní funkce:

(rationalize Math/PI)
3141592653589793/1000000000000000

Další příklad: kombinace takzvaného threading makra, konstruktoru sekvence, funkce vyššího řádu reduce a zlomků:

(->> (repeat 10 3/7) (reduce *))
59049/282475249

Použití zlomků může být v mnoha oblastech výhodné, protože jimi lze nahradit typy decimal či FP s bází rovnou deseti. Zaplatíme za to ovšem delším časem výpočtu, protože zlomky nejsou přímo podporovány v hardware a navíc se musí výsledek výpočtu (dvě celočíselné hodnoty x a y) zjednodušovat.

Obrázek 13: Design počítače Connection Machine 5 (s paralelním LISPem) se skutečně povedl, jedná se pravděpodobně o nejelegantnější superpočítač, který byl kdy vyroben.

20. Odkazy na Internetu

1. Norma IEEE 754 a příbuzní: formáty plovoucí řádové tečky
   https://www.root.cz/clanky/norma-ieee-754-a-pribuzni-formaty-plovouci-radove-tecky/
2. IEEE-754 Floating-Point Conversion
   http://babbage.cs.qc.cuny.edu/IEEE-754.old/32bit.html
3. Small Float Formats
   https://www.khronos.org/o­pengl/wiki/Small_Float_For­mats
4. Binary-coded decimal
   https://en.wikipedia.org/wiki/Binary-coded_decimal
5. Chen–Ho encoding
   https://en.wikipedia.org/wi­ki/Chen%E2%80%93Ho_encoding
6. Densely packed decimal
   https://en.wikipedia.org/wi­ki/Densely_packed_decimal
7. A Summary of Chen-Ho Decimal Data encoding
   http://speleotrove.com/decimal/chen-ho.html
8. Art of Assembly language programming: The 80×87 Floating Point Coprocessors
   https://courses.engr.illi­nois.edu/ece390/books/arto­fasm/CH14/CH14–3.html
9. Art of Assembly language programming: The FPU Instruction Set
   https://courses.engr.illi­nois.edu/ece390/books/arto­fasm/CH14/CH14–4.html
10. INTEL 80387 PROGRAMMER'S REFERENCE MANUAL
    http://www.ragestorm.net/dow­nloads/387intel.txt
11. Floating-Point Formats
    http://www.quadibloc.com/com­p/cp0201.htm
12. Mainframe family tree and chronology
    http://www-03.ibm.com/ibm/history/ex­hibits/mainframe/mainframe_FT1­.html
13. 704 Data Processing System
    http://www-03.ibm.com/ibm/history/ex­hibits/mainframe/mainframe_PP704­.html
14. 705 Data Processing System
    http://www-03.ibm.com/ibm/history/ex­hibits/mainframe/mainframe_PP705­.html
15. The IBM 704
    http://www.columbia.edu/a­cis/history/704.html
16. IBM Mainframe album
    http://www-03.ibm.com/ibm/history/ex­hibits/mainframe/mainframe_al­bum.html
17. Mainframe computer
    http://en.wikipedia.org/wi­ki/Mainframe_computer
18. IBM mainframe
    http://en.wikipedia.org/wi­ki/IBM_mainframe
19. IBM 700/7000 series
    http://en.wikipedia.org/wi­ki/IBM₇₀₀/7000_series
20. IBM System/360
    http://en.wikipedia.org/wi­ki/IBM_System/360
21. IBM System/370
    http://en.wikipedia.org/wi­ki/IBM_System/370
22. IBM Floating Point Architecture
    http://en.wikipedia.org/wi­ki/IBM_Floating_Point_Archi­tecture
23. Extended Binary Coded Decimal Interchange Code
    http://en.wikipedia.org/wiki/EBCDIC
24. ASCII/EBCDIC Conversion Table
    http://docs.hp.com/en/32212–90008/apcs01.html
25. EBCDIC
    http://www.hansenb.pdx.edu/DMKB/dic­t/tutorials/ebcdic.php
26. EBCDIC tables
    http://home.mnet-online.de/wzwz.de/temp/eb­cdic/cc_en.htm
27. The Mainframe Blog
    http://mainframe.typepad.com/blog/2006/11/my_per­sonal_mai.html
28. IBM Tightens Stranglehold Over Mainframe Market Gets Hit with Antitrust Complaint in Europe
    http://www.ccianet.org/ar­tmanager/publish/news/IBM_Tig­htens_Stranglehold_Over_Ma­inframe_Market_Gets_Hit_wit­h_Antitrust_Complaint_in_E­urope.shtml
29. Lectures in the History of Computing: Mainframes
    http://www.computinghisto­rymuseum.org/teaching/lec­tures/pptlectures/9-MainframeComputers.ppt
30. 36-bit
    http://en.wikipedia.org/wiki/36-bit_word_length
31. 36bit.org
    http://www.36bit.org/
32. Applesoft BASIC
    https://en.wikipedia.org/wi­ki/Applesoft_BASIC
33. How did the Apple II do floating point?
    https://groups.google.com/fo­rum/#!topic/comp.emulator­s.apple2/qSBiG2TAlRg
34. IBM Floating Point Architecture
    https://en.wikipedia.org/wi­ki/IBM_Floating_Point_Archi­tecture
35. The Arithmetic Subroutines
    http://www.users.waitrose­.com/~thunor/mmcoyzx81/chap­ter17.html
36. ZX Floating point to Decimal code in BASIC
    http://www.sinclairzxworld­.com/viewtopic.php?t=1422
37. Floating Point Arithmetic Package
    http://www.retrocomputing­.net/parts/atari/800/docs/a­tari_os/atari_os_user_manu­al₀₈.htm
38. 704 Data Processing System
    https://www-03.ibm.com/ibm/history/ex­hibits/mainframe/mainframe_PP704­.html
39. Turbo Pascal Real
    http://www.shikadi.net/mod­dingwiki/Turbo_Pascal_Real
40. THE FLOATING POINT ARITHMETIC PACKAGE
    http://www.atarimax.com/fre­enet/freenet_material/5.8-BitComputersSupportArea/7­.TechnicalResourceCenter/sho­warticle.php?14
41. Sinclair ZX81 BASIC Programming (by Steven Vickers)
    http://www.worldofspectrum­.org/ZX81BasicProgramming/
42. The Most Expensive One-byte Mistake: Did Ken, Dennis, and Brian choose wrong with NUL-terminated text strings?
    http://queue.acm.org/deta­il.cfm?id=2010365
43. UCSD Pascal
    https://en.wikipedia.org/wi­ki/UCSD_Pascal
44. D Language: Strings
    https://dlang.org/spec/arra­ys.html#strings
45. The History Behind the Definition of a ‚String‘
    https://stackoverflow.com/qu­estions/880195/the-history-behind-the-definition-of-a-string
46. Libc: Representation of Strings
    https://www.gnu.org/softwa­re/libc/manual/html_node/Re­presentation-of-Strings.html
47. ATARI BASIC
    http://www.atariarchives.or­g/dere/chapt10.php
48. BASIC (Wikipedia EN)
    http://en.wikipedia.org/wiki/BASIC
49. BASIC (Wikipedia CZ)
    http://cs.wikipedia.org/wiki/BASIC
50. Turbo BASIC (Wikipedia CZ)
    http://cs.wikipedia.org/wi­ki/Turbo_BASIC
51. Sinclair BASIC (Wikipedia CZ)
    http://cs.wikipedia.org/wi­ki/Sinclair_BASIC
52. More BASIC Computer Games
    http://www.atariarchives.or­g/morebasicgames/
53. Dartmouth College Computation Center: 1964 – The original Dartmouth BASIC manual
    http://www.bitsavers.org/pdf/dar­tmouth/BASIC_Oct64.pdf
54. The Original BASIC
    http://www.truebasic.com/
55. BASIC – Beginners All-purpose Symbolic Instruction Code
    http://hopl.murdoch.edu.au­/showlanguage.prx?exp=176
56. Universal Coded Character Set
    https://en.wikipedia.org/wi­ki/Universal_Coded_Charac­ter_Set
57. UTF-16
    https://en.wikipedia.org/wiki/UTF-16
58. PEP 393 – Flexible String Representation
    https://www.python.org/dev/peps/pep-0393/
59. In-memory size of a Python structure
    https://stackoverflow.com/qu­estions/1331471/in-memory-size-of-a-python-structure
60. What is internal representation of string in Python 3.x
    https://stackoverflow.com/qu­estions/1838170/what-is-internal-representation-of-string-in-python-3-x#9079985
61. How to profile memory usage in Python
    https://www.pluralsight.com/blog/tu­torials/how-to-profile-memory-usage-in-python
62. What's the rationale for null terminated strings?
    https://stackoverflow.com/qu­estions/4418708/whats-the-rationale-for-null-terminated-strings
63. Unicode
    https://en.wikipedia.org/wiki/Unicode
64. The Development of the C Language
    https://www.bell-labs.com/usr/dmr/www/chist.html
65. Borland Pascal Wiki: String operations
    http://borlandpascal.wiki­a.com/wiki/String_operati­ons
66. Pascal Strings
    https://www.tutorialspoin­t.com/pascal/pascal_strin­gs.htm
67. PChar – Null terminated strings
    https://www.freepascal.org/docs-html/ref/refsu12.html
68. Comparison of Pascal and C
    https://en.wikipedia.org/wi­ki/Comparison_of_Pascal_an­d_C
69. FORTRAN 66
    http://fortranwiki.org/for­tran/show/FORTRAN+66
70. Fortran: strings
    https://en.wikibooks.org/wi­ki/Fortran/strings
71. Strings in Atari BASIC
    http://www.cyberroach.com/a­nalog/an11/strings.htm
72. String Arrays in Atari BASIC
    http://www.atarimagazines­.com/compute/issue11/52_1_STRIN­G_ARRAYS_IN_ATARI_BASIC.php
73. An Atari BASIC Tutorial
    http://www.cyberroach.com/a­nalog/an25/basictutorial.htm
74. Basic Multilingual Plane
    https://en.wikipedia.org/wi­ki/Plane_(Unicode)#Basic_Mul­tilingual_Plane