<< Zpět

 

  Česky: , English:

Proč 1 + 1 nejsou vždy 2?

Možná jste se s tím už setkali. Rozdělím koláč na desetiny. Odeberu 7 desetin a potom 3 desetiny. Kolik zbude? Počítač tvrdí, že mu zbyl ještě malý kousek 0.00000001! Jak k tomu přišel? Je vadný? Bohužel chyba není v počítači, ale na opačné straně obrazovky. Probereme si zde problematiku přesnosti float čísel.

Binární reprezentace čísla

První problém je v číselné soustavě. Příroda (nebo Anunnaki?) nás obdařila deseti prsty, které se tak skvěle hodí na počítání ovcí, až jsme si je zavedli jako číselnou soustavu. Tím jsme si to tak trochu zavařili, protože 10 se velmi špatně dělí na stále menší poloviny. A právě dělení dvěma je ten nejvýhodnější způsob vyjádření informací, protože si vystačíme jen se 2 stavy, ANO a NE, černá a bílá, ZAP a VYP, 1 a 0.

Na binárním způsobu fungují počítače. Je proto zřejmé, že i čísla je pro ně nejvýhodnější vyjadřovat binárním způsobem. A abychom mohli náš způsob počítání převést do formy srozumitelné pro počítače, musíme číslo zkonvertovat z dekadické formy do binární.

U celých čísel je to celkem ještě snadné - číslo rozložíme na násobky mocniny 2. Např. číslo 753 rozložíme na:

753 = 1*2^9 + 0*2^8 + 1*2^7 + 1*2^6 + 1*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 1*2^0

To je v binárním zápisu 10111100001, v HEX formátu 0x2F1.

Podobně můžeme rozložit desetinné číslo, s tím rozdílem, že pro násobky mocnin 2 použijeme záporné exponenty. Např. číslo 0.1 rozložíme na:

0.1 = 0*2^-1 + 0*2^-2 + 0*2^-3 + 1*2^-4 + 1*2^-5 + 0*2^-6 + 0*2^-7 + 1*2^-8 + 1*2^-9 ...

Ale ouha - jak můžeme zjistit, převod nikdy nekončí a nikdy se nedostaneme k přesné hodnotě 0.1! Co je v dekadické reprezentaci číslo s konečným počtem číslic, může v binárním tvaru znamenat nekonečný počet číslic a tudíž číslo nevyjádřitelné přesně. Ve formátu float čísel (single-precision, 4 bajty na číslo) by hodnota 0.1 vypadala takto:

0xCD 0xCC 0xCC 0x3D

Exponent je 0x7B (= -4 bez biasu), mantisa 0xCCCCCD (s doplněnou skrytou "1"). V přesném vyjádření by číslo 0.1 obsahovalo v mantise nekonečný počet číslic 0xC, ale z důvodu omezení délky čísla je poslední číslice mantisy zaokrouhlena nahoru, na číslici 0xD.

Zobrazíme-li takové číslo, dostaneme očekávaný výsledek 0.1 pouze při zaokrouhlení na nižší přesnost než je plný rozsah čísla. Příklad v C:

printf("Zaokrouhleno: %.8f\n", 0.1f);
printf("Plna presnost: %.9f\n", 0.1f);

Vytiskne:

Zaokrouhleno: 0.10000000
Plna presnost: 0.100000001

Zdánlivě jsme zadali "hezké" číslo, s konečným počtem číslic, a aniž jsme provedli jakoukoliv operaci, počítač nám už není schopný takové číslo vrátit. Není to chyba, je to vlastnost, se kterou musíme počítat.

Binární čísla versus BCD čísla

Náprava uvedeného problému by mohla spočívat v BCD reprezentaci čísla. V BCD formátu není číslo v paměti počítače uloženo v binární formě, ale jako dekadické číslice 0 až 9. Tímto způsobem počítaly (a dosud počítají) kalkulačky. Procesor s čísly počítá stejným způsobem, jako to dělá člověk. Čísla nepřevádí do binární formy, pouze si zadané číslo uloží jako posloupnost číslic a s číslicemi také počítá. To sebou přináší několik úskalí:

První úskalí, vyšší paměťové nároky, se snaží řešit nové formáty normy IEEE754 s desítkovou aritmetikou - decimal32, decimal64 a decimal128. Tyto formáty mohou mít dvě varianty. Jednak klasickou variantu s binárním BCD kódováním, kdy 2 číslice obsadí 1 bajt, a jednak DPD kódování, kdy se 3 dekadické číslice zakódují do 10 bitů. Při použití DPD kódování je efektivita uložení čísla srovnatelná s binárním formátem čísla.

Ovšem práce s DPD kódováním není snadná. Má velké nároky na kompresi a dekompresi čísel a je proto pomalejší i než pomalý BCD režim. Masivnější nasazení DPD formátu zatím čeká na hardwarovou podporu od matematického koprocesoru a je proto zatím spíš teoretickou záležitostí. Jako referenční normu vydal Intel knihovnu pro podporu těchto nových formátů: Intel Decimal Floating-Point Math Library https://software.intel.com/content/www/us/en/develop/articles/intel-decimal-floating-point-math-library.html . DPD formát spolu s Intel knihovnou byl využit např. v kalkulačce DM42 ( https://www.swissmicros.com/product/dm42 ), která díky tomu podporuje 128-bitová BCD čísla s přesností 34 číslic a exponentem +-6143. Jak bývá u kalkulaček zvykem, nízká rychlost výpočtů se tam moc neřeší. Obzvláště když je kompenzovaná výkonným procesorem STM32L476VGT6.

Je ovšem otázkou, zda v dnešní době rychle klesajících cen pamětí má smysl zabývat se vyššími paměťovými nároky čísel v BCD formátu. Rozdíl nároků na paměť není až tak propastný aby se vyplatila časově velmi náročná obsluha DPD formátu. Rozumné využití nastane teprve až bude formát plně podporován hardwarovým koprocesorem, bez ztráty rychlosti.

Nízká rychlost je největším úskalím BCD formátu. Pro srovnání, jak vypadá součet 2 bajtů mantisy v binárním formátu u procesoru ATmega:

	adc	r1,r10
A jak zhruba vypadá součet odpovídajících 2 BCD číslic v BCD formátu (vytrženo z kontextu, detaily nezkoumejte, je to jen pro náznak :-) ):
	andi	r21,0x0f	; mask lower digit 1
	add	r23,r21		; add input carry

	; load low digit 2
	mov	r25,r24		; save byte
	andi	r24,0x0f	; mask lower digit of mantissa
	andi	r25,0xf0	; mask higher digit of mantissa

	; add low digit
	add	r24,r23		; add 1st digit with carry
	clr	r23		; clear carry
	cpi	r24,10		; carry?
	brcs	2f		; no carry, save result
	subi	r24,10		; carry correction
	ldi	r23,1		; new carry

	; compose digit
2:	or	r24,r25		; compose digits
	swap	r21		; swap digits
	swap	r24		; swap digits

	; load high digit
	mov	r25,r24		; save byte
	andi	r24,0x0f	; mask lower digit of mantissa
	andi	r25,0xf0	; mask higher digit of mantissa

	; add high digits
	add	r24,r23		; add carry
	clr	r23		; clear carry
	cpi	r24,10		; carry?
	brcs	2f		; no carry, save result
	subi	r24,10		; carry correction
	ldi	r23,1		; new carry

	; compose digit
2:	or	r24,r25		; compose digits
	swap	r24		; swap digits

Nižší rychlost výpočtů v BCD formátu je trochu kompenzována vyšší rychlostí převodů mezi textovým a interním vyjádřením čísla. Zobrazení BCD čísla je velmi jednoduché, stačí jen převzít z mantisy potřebné číslice. U binárního formátu je převod velmi obtížný. Nejdříve je potřeba rozdělit číslo na mantisu a exponent - a to tak, že číslo bude děleno či násobeno mocninami exponentu tak, až se mantisa dostane do intervalu 1 až 10. Jednotlivé číslice mantisy se pak získají opakovaným násobením mantisy číslem 10 a odstraňováním celočíselné části čísla.

Z výše uvedených důvodů se BCD formát používá u kalkulaček a malých zařízení, kde nevadí nízká rychlost výpočtu a spíš se upřednostňují rychlé časté převody mezi interním a textovým formátem čísla. Binární formát se přednostně používá u počítačů, kde se převody do textového tvaru nedělají často a důležitější je vysoká rychlost výpočtů.

Akumulace chyby

Vzhledem k tomu, že čísla v interním formátu mají omezenou přesnost, bude vždy docházet k akumulaci chyby. Odchylce od správné hodnoty nelze zabránit a při opakovaných výpočtech se tato odchylka dále navyšuje. Běžně se floatová čísla zobrazují s rezervou a zaokrouhlením, ale po více operacích může chyba dosáhnout zobrazené části. Příklad:

	for (float n = 0; n != 0.4f; n += 0.1f) printf("n=%.9f\n", n);

Jako parametr cyklu použijeme float zvyšovaný o 0.1f. Cyklus ukončíme dosažením hodnoty 0.4f. Program vypíše podle očekávání:

n=0.000000000
n=0.100000001
n=0.200000003
n=0.300000012

Zvyšme hraniční hodnotu na 0.7f. Program se rozběhne a už se nikdy nezastaví. Akumulací chyby vznikla odchylka od očekávané hodnoty 0.7f.

Při práci s desetinnými čísly nemůžeme čísla porovnávat s přesnou hodnotou. Díky odchylkám se číslo může mírně lišit. Řešením je porovnávání čísel v intervalu, s odchylkou epsilon. Program bychom v tom případě upravili takto:

	for (float n = 0; abs(n - 0.7f) > 0.0001f; n += 0.1f) printf("n=%.9f\n", n);

Program poběží do té doby, dokud bude odchylka od koncové hodnoty větší než nastavená minimální odchylka.

U programovatelných kalkulátorů tuto kontrolu zajistí již kalkulátor. Během operace porovnání se čísla od sebe odečtou. Pokud kalkulátor počítá na 13 číslic a zobrazuje na 10 číslic, ví že má 3 číslice k dispozici pro svou interní potřebu, pro nepřesnosti. Dostane-li se při porovnání hodnota rozdílu čísel mimo zobrazený rozsah (rozdíl exponentů operandů a výsledku je vyšší než 10), ví že se nejedná o údaj od uživatele, ale jedná se o odchylku nepřesnosti a v tom případě považuje čísla za shodná.

Miroslav Němeček

<< Zpět