Převod do celočíselné aritmetiky

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Jako převod do celočíselné aritmetiky lze označit přepis výpočtu s reálnými konstantami na výpočet s konstantami celočíselnými. Jedná se metodu optimalizace, jejímž důsledkem je vznik zaokrouhlovacích chyb.

Výpočet realizovaný s čísly v plovoucí řádové čárce (FP) je z principu pomalejší než výpočet s čísly celými. Podstatou převodu výpočtu do celočíselné aritmetiky je náhrada násobení celého čísla reálnou konstantou v plovoucí řádové čárce za násobení tohoto čísla konstantou celočíselnou s následným dělením výsledku jinou celočíselnou konstantou. Protože je ovšem dělení výpočetně náročná operace, je vhodné jej nahradit bitovým posunem výsledku vpravo. Takovým výpočtem se ovšem akumulují chyby.

Celočíselná konstanta se získá součinem původní reálné konstanty s 2^n, kde n je vhodně zvolená délka posunu. Následný bitový posun vpravo odpovídá dělení touto konstantou (2^n). Tímto posunem vznikne značná zaokrouhlovací chyba. Pokud je výpočet složen z opakovaného násobení reálnou konstantou, není vhodné provádět bitový posun vpravo po každém takovém převodu. Mnohem přesnější je provést součiny s odpovídajícími celočíselnými konstantami a nakonec provést jediný bitový posun vpravo. Délka tohoto posunu bude odpovídat celkovému součtu vynechaných posunů. Je třeba dát pozor na to, aby použitý celočíselný datový typ svým rozsahem dostačoval k uložení takto rozšířeného čísla.

Například výpočet součinu celého čísla x s reálnou konstantou R (v jazyce C zapsáno jako x * R) lze přepsat jako součin x s celočíselnou konstantou I následovaný bitovým posunem o S bitů vpravo ((x * I) >> S), kde I = round(2^S R), S je celočíselná konstanta a round() značí zaokrouhlení na nejbližší celé číslo. Se stoupající hodnotou konstanty S roste přesnost výpočtu.

příklad
int a, b, c;
 
// výpočet s ve FP
c = 2.7519 * a + 6.5627 * b;
 
// lze s rozšířením o 4 bity přepsat na
c = (44 * a + 105 * b) >> 4;