Přetečení: co se stane, když se to nevejde

Tohle je statická kopie kapitoly pro vyhledávače. Interaktivní verze má animované obrázky, kontrolní otázky a tlačítka, která příklad načtou do kalkulačky.

Přetečení: co se stane, když se to nevejde

Osmibitové počitadlo na hodnotě 255 dostane pokyn přičíst jedničku. Nespadne a nenahlásí chybu — přejde na nulu. To není porucha; je to definované chování, protože devátý bit nemá kam.

Zadej hodnotu, která se do zvolené šířky nevejde, a sleduj, kolik celých otáček udělá, než se zastaví. Zkus i menší šířky — u čtyř bitů se to stane skoro hned.

Nejužitečnější obrázek je kruh, ne přímka. Čísla nekončí, obtočí se. Aritmetika bez znaménka je aritmetika modulo 2ⁿ, a to je matematicky poctivá struktura — ne selhání.

výsledek = (a + b) mod 2ⁿbez znaménka

Se znaménkem je to horší

U hodnot bez znaménka je obtočení definované. U hodnot se znaménkem je v jazyce C přetečení nedefinované chování, a to je podstatný rozdíl: překladač smí předpokládat, že nenastane, a podle toho optimalizovat. Test if (x + 1 < x) se dá legálně vyhodit jako vždy nepravdivý, protože „přece nemůže přetéct“. Kontrola přetečení tedy musí být napsaná před operací, ne po ní.

Ariane 5, let 501, 4. června 1996. Šedesátičtyřbitová hodnota vodorovné rychlosti se převáděla na šestnáctibitové celé číslo se znaménkem. U Ariane 4 se tam vešla vždycky. Ariane 5 letěla rychleji, číslo se nevešlo, převod skončil výjimkou, záložní jednotka běžela týž kód a selhala stejně o čtyřicet milisekund dřív. Raketa se rozpadla 37 sekund po startu. Ta část programu v tu chvíli nedělala nic užitečného — dobíhala z předstartovní sekvence.

Kde na to člověk narazí v praxi

Časovače. Milisekundový čítač v 32 bitech přeteče po 49,7 dnech. Rozdíl now − then ale přeteče taky, a proto vyjde správně — pokud se odečítá bez znaménka a interval je kratší než polovina rozsahu. Porovnání now > deadline správně nevyjde.
Sčítání sum. Součet stovky šestnáctibitových měření se do šestnácti bitů nevejde. Akumulátor musí být širší než sčítance, a to je pravidlo, ne opatrnost.
Střed intervalu. (lo + hi) / 2 přeteče, když jsou obě velké. Správně je lo + (hi − lo) / 2. Tahle chyba byla v binárním vyhledávání v knihovně Javy devět let.