funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

99.00000000000000009 problémů s floating point čísly

24. 1. 2017 — k47

Flo­a­ting point čísla a jejich IEEE 754 va­ri­anta jsou jednou z těch věcí, které mě nikdy ne­pře­sta­nou fas­ci­no­vat. Jde o uži­teč­nou věc, která člo­věka skoro pře­svědčí, že všechno bude ok, že svět má svůj řád, že se stačí ode­vzdat flo­a­ting vlnám a už se není třeba o nic starat. Hned potom ale narazí na za­o­krouh­lo­vací chyby, ne­ko­nečna, NaNy, ne­ga­tivní nulu, de­nor­mální čísla a hned z toho nar­ko­tic­kého blaha vy­stříz­liví.

V tomto duchu začal 13. sraz přátel PHP – his­tor­kou o kla­sic­kém pří­padě, kdy floaty ne­po­u­ží­vat – k re­pre­zen­taci peněz.

Floaty po­cho­pi­telně nejsou přesné a za­o­krouh­lo­vací chyby vzni­kají i v tri­vi­ál­ních pří­pa­dech. Na­pří­klad 0.1 + 0.2 je 0.30000000000000004. Pokud to šlo peníze, na­jed­nou jsem z ničeho vy­tvo­řil čtyři fem­to­ha­líře.

Tyto chyby jsou malé a ne­ná­padné a člověk si je uvě­domí až ve chvíli, kdy mu kan­ce­lář začnou ob­lé­hat au­di­toři s be­ra­ni­dly a po­kři­kují něco o tom, že nesedí účet­nic­tví. Kdyby se peníze uklá­daly do intů, tak v nej­hor­ším pří­padě částka pře­teče do vel­kého množ­ství zá­por­ných peněz a to je chyba, které si nově vzniklý zá­porný mi­li­o­nář snadno všimne.

Sa­mo­zřejmě, na peníze a jiné kvan­tity, které je třeba vést na­prosto přesně, se musí použít něco jako Bi­gIn­te­ger nebo BigDe­ci­mal.

A to je jenom za­čá­tek.

Ně­které jazyky jako třeba PHP nebo Ja­vaScript při­dá­vají svoje spe­ci­a­lity, pro­tože v nich celá čísla au­to­ma­ticky pře­té­kají do floatů.

Na­pří­klad tento PHP kód

for ($i = 0; $i != ($i+1); $i++) { echo "lol"; }

vypadá jak ne­ko­nečná smyčka, pro­tože se přece nikdy nemůže stát, že $i je stejné jako $i+1. PHP na to má ale jiný názor. Int even­tu­álně pře­teče do double floatu s nižší přes­ností, které mají krok mezi dvěma sou­sed­ními čísly větší než 1, součet nic ne­změní a smyčka skončí. V PHP je int jen double, který čeká na svůj oka­mžik slávy.

Ve sluš­ných ja­zy­cích, by int pře­tekl do zá­por­ných hodnot, ale pořád by pla­tilo, že ii+1 jsou roz­dílné.

Pro za­jí­ma­vost: celá čísla v in­ter­valu [-224, 224] můžou být v single pre­ci­sion floatu ulo­ženy přesně bez za­o­krouh­lo­va­cích chyb.


Aso­ci­a­ti­vita je uži­tečná vlast­nost, která je stě­žejní pro pa­ra­le­li­zaci. Tomu si, jak doufám, žádný slušný člověk ne­do­volí od­po­ro­vat. Floaty po­cho­pi­telně aso­ci­a­tivní nejsou.

val ds = Array.fill(10000)(util.Random.nextDouble)
assert(ds.sum - util.Random.shuffle(ds).sum == 0.0)

val ds = Array.fill(10000) {
  val a, b, c = util.Random.nextDouble
  ((a+b)+c) - (a+(b+c))
}
assert(ds.forall(d => d == 0.0))

Obě aserce selžou, pro­tože součty pro­vá­děné v růz­ných po­řa­dích, uvedou různé za­o­krouh­lo­vací chyby a to vede k různým fi­nál­ním vý­sled­kům.

Tohle je po­měrně dů­le­žité, pro­tože to kom­pi­lá­to­rům sva­zuje ruce v op­ti­ma­li­za­cích, které můžou bez­pečně udělat. Změna pořadí ope­rací může vést ke zrych­lení, ale taky k od­liš­nému vý­sledku.1


IEEE 754 spe­ci­fi­kuje bi­to­vou re­pre­zen­taci floatů a toho se dá využít k různým trikům. Jedním z nich je mož­nost trans­for­mo­vat float na int s tím, že vztah mezi floaty je stejný jako mezi nově vy­tvo­ře­nými inty. Tedy, když platí

a < b

tak platí i

floatToInt(a) < floatToInt(b)

a zá­ro­veň exis­tuje trans­for­mace zpátky

intToFloat(floatToInt(f)) = f

Jde o pár ope­rací, které ve Scale vy­pa­dají takto:

def flip(f: Int) = f ^ (-(f >>> 31) & 0x7FFFFFFF)

def floatToInt(f: Float) = flip(Float.floatToRawIntBits(f))
def intToFloat(i: Int)   = Float.intBitsToFloat(flip(i))

Kód je za­lo­žený na tomto článku, jen jsem ho upra­vil pro zna­mén­kové inty Javy. V pod­statě jde o to, že pokud je float zá­porný, pře­vrá­tím všechny bity kromě zna­ménka. Tím se bitová re­pre­zen­tace bude chovat stejně jako int.

Když vynesu průběh intů a floatů na in­ter­valu všech bi­to­vých hodnot od samých nul nalevo až po samé jed­ničky na­pravo, inty mají ta­ko­vý­hle průběh:

Floaty zase ta­ko­výto (NaNy by měly být někde za ne­ko­nečny, ale ty si teď do­vo­lím ig­no­ro­vat):

Kód jen pře­klopí druhou po­lo­vinu in­ter­valu.

To­ho­hle triku se dá využít k jed­no­du­chému řazení floatů radix sortem. Na za­čátku floaty pře­vedu na inty za­cho­vá­va­jící pořadí, roz­jedu radix sort pro inty a na konci vý­sle­dek pře­píšu zpátky na foaty. Exis­tují i přímé způ­soby, jak ra­di­x­sor­to­vat floaty, ale ty jsou kom­pli­ko­va­nější.


Dále k tématu


Pozn.

  1. Ně­které ar­chi­tek­tury můžou pro­vá­dět vý­po­čty s vyšší přes­ností, třeba 80 bitů na­místo 64 a vý­sle­dek na­ko­nec za­o­krouh­lit na 64, viz strictpf.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články