Aritmetika sytosti - Saturation arithmetic

Aritmetika sytosti je verze aritmetický ve kterém jsou všechny operace, jako je sčítání a násobení, omezeny na pevný rozsah mezi minimální a maximální hodnotou.

Pokud je výsledek operace větší než maximum, je nastavena ("upnutý ") na maximum; pokud je pod minimem, je upnuto na minimum. Název pochází z toho, jak se hodnota stane„ nasycenou ", jakmile dosáhne extrémních hodnot; další přírůstky k maximu nebo odčítání od minima nebudou změnit výsledek.

Například pokud je platný rozsah hodnot od -100 do 100, následující saturační aritmetické operace vytvoří následující hodnoty:

• 60 + 30 → 90.
• 60 + 43 → 100. (ne očekávaných 103.)
• (60 + 43) − (75 + 75) → 0. (ne očekávané −47.) (100 - 100 → 0.)
• 10 × 11 → 100. (ne očekávaných 110.)
• 99 × 99 → 100. (ne očekávaných 9801.)
• 30 × (5 − 1) → 100. (ne očekávaných 120.) (30 × 4 → 100.)
• (30 × 5) − (30 × 1) → 70. (ne očekávaných 120. ne předchozí 100.) (100 - 30 → 70.)

Jak je patrné z těchto příkladů, známé vlastnosti jako asociativita a distribučnost může selhat v aritmetice nasycení.^[1] Díky tomu je v abstraktní matematice nepříjemné se s ním vypořádat, ale má v tom důležitou roli digitální hardware a algoritmy, kde hodnoty mají maximální a minimální reprezentativní rozsahy.

Moderní využití

Typicky, univerzální mikroprocesory neimplementujte celočíselné aritmetické operace pomocí aritmetiky nasycení; místo toho používají snadnější implementaci modulární aritmetika, ve kterých hodnoty překračují maximální hodnotu "obalit „na minimální hodnotu, jako jsou hodiny na hodinách od 12 do 1. V hardwaru modulární aritmetika s minimem nuly a maximem rⁿ - 1, kde r je základ lze implementovat jednoduchým vyřazením všech kromě těch nejnižších n číslice. U binárního hardwaru, který je naprostou většinou moderního hardwaru, je radix 2 a číslice jsou bity.

Přestože je obtížnější jej implementovat, má saturační aritmetika řadu praktických výhod. Výsledek se co nejvíce numericky blíží skutečné odpovědi; pro 8bitovou binární aritmetiku se znaménkem, když je správná odpověď 130, je podstatně méně překvapivé získat odpověď 127 ze saturující aritmetiky, než získat odpověď −126 z modulární aritmetiky. Stejně tak pro 8bitovou binární aritmetiku bez znaménka, když je správná odpověď 258, je méně překvapivé získat odpověď 255 ze saturující aritmetiky, než získat odpověď 2 z modulární aritmetiky.

Aritmetika nasycení také umožňuje konzistentně detekovat přetečení sčítání a násobení bez přetečení bitu nebo nadměrného výpočtu, jednoduchým porovnáním s maximální nebo minimální hodnotou (za předpokladu, že vztažný bod není povolen na tyto hodnoty).

Aritmetika nasycení navíc umožňuje efektivní algoritmy pro mnoho problémů, zejména v zpracování digitálních signálů. Například nastavení úrovně hlasitosti zvukového signálu může mít za následek přetečení a sytost způsobí výrazně menší zkreslení zvuku, než je tomu u okrajů. Podle slov vědců G. A. Constantinides et al .:^[2]

Když přidáváte dvě čísla pomocí reprezentace dvou doplňků, přetečení má za následek fenomén „wrap-around“. Výsledkem může být katastrofická ztráta poměru signálu k šumu v systému DSP. Signály v designech DSP jsou proto obvykle buď vhodně upraveny, aby se zabránilo přetečení pro všechny kromě nejextrémnějších vstupních vektorů, nebo jsou vytvářeny pomocí aritmetických komponent saturace.

Implementace

Aritmetické operace nasycení jsou k dispozici na mnoha moderních platformách a byly zejména jednou z rozšíření od společnosti Intel MMX platforma, konkrétně pro takové aplikace pro zpracování signálu. Tato funkce je k dispozici také v širších verzích v SSE2 a AVX2 celočíselné instrukční sady.

Aritmetika saturace pro celá čísla byla také implementována do softwaru pro řadu programovacích jazyků včetně C, C ++, tak jako Sbírka překladačů GNU,^[3], LLVM IR a Eiffelova. To pomáhá programátorům lépe předvídat a porozumět účinkům přetečení a v případě překladačů obvykle vybrat optimální řešení.

Saturace je náročné efektivně implementovat do softwaru na stroji pouze s modulárními aritmetickými operacemi, protože jednoduché implementace vyžadují větve, které vytvářejí velké zpoždění potrubí. Je však možné implementovat saturační sčítání a odčítání v softwaru bez větví, používající pouze modulární aritmetické a bitové logické operace, které jsou k dispozici na všech moderních procesorech a jejich předchůdcích, včetně všech procesorů x86 (zpět na původní Intel 8086 ) a některé populární 8bitové procesory (některé, například Zilog Z80, jsou stále ve výrobě). Na druhou stranu na jednoduchých 8bitových a 16bitových procesorech může být větvicí algoritmus ve skutečnosti rychlejší, pokud je naprogramován v sestavě, protože neexistují žádné kanály, které by se mohly zastavit, a každá instrukce vždy trvá několik hodinových cyklů. Na x86, který poskytuje příznaky přetečení a podmíněné pohyby, je možný velmi jednoduchý kód bez poboček.^[4]

Ačkoli je aritmetika sytosti méně oblíbená pro celočíselnou aritmetiku v hardwaru, Standard IEEE s plovoucí desetinnou čárkou, nejpopulárnější abstrakce pro práci s přibližnými reálnými čísly, používá formu sytosti, při které se přetečení převádí na „nekonečno“ nebo „záporné nekonečno“ a jakákoli další operace s tímto výsledkem nadále produkuje stejnou hodnotu. To má tu výhodu oproti jednoduchému nasycení, že pozdější operace snižující hodnotu neskončí s klamně „rozumným“ výsledkem, jako například ve výpočtu ${ displaystyle { sqrt {x ^ {2} -y ^ {2}}}}$. Alternativně mohou existovat speciální stavy, například „přetečení exponentů“ (a „podtečení exponentů“), které budou podobně přetrvávat v následných operacích nebo způsobí okamžité ukončení nebo budou testovány jako v KDYŽ AKUMULÁTOR PŘETOČÍ ... jako ve FORTRANU pro IBM704 (říjen 1956).

Viz také

• Cenzura (statistika)

Poznámky

externí odkazy

• SARITH: Safe ARITHmetic - Zpráva o pokroku: Zpráva o aritmetické složce sytosti pro Eiffelova.
• nasycení, C ++ knihovna pouze pro záhlaví pro nasycení arimetiky, pokud jde o vestavěné GCC Overflow.