Nierówności spowodowane niedokładnością pływaka

15

Przynajmniej w Javie, jeśli napiszę ten kod:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b + b;
float d = b + b + a;
boolean e = c == d;

wartość byłaby . Uważam, że jest to spowodowane faktem, że liczby zmiennoprzecinkowe są bardzo ograniczone w zakresie dokładnego przedstawiania liczb. Ale nie rozumiem, dlaczego zmiana pozycji może spowodować tę nierówność. $e$ $false$ $a$

I zmniejszył e jednego zarówno w przewód 3 i 4, jak to poniżej, wartość jednak staje : $b$ $e$ $true$

float a = 1000.0F;
float b = 0.00004F;
float c = a + b;
float d = b + a;
boolean e = c == d;

Co dokładnie wydarzyło się w liniach 3 i 4? Dlaczego operacje dodawania z pływakami nie są skojarzone?

Z góry dziękuję.

arithmetic floating-point numerical-algorithms

— Znana Zeta
źródło

16

Jak pokazuje twój przykład, dodawanie zmiennoprzecinkowe jest przemienne. Ale to nie jest skojarzenie.

— Yuval Filmus

1

Zachęcam do zapoznania się z podstawowymi definicjami. Zauważ też, że kompilator analizuje

jako

(dodatek jest powiązany z lewej).

r + s + t

$r+s+t$

(r + s) + t

$(r+s)+t$

— Yuval Filmus,

2

Aby łatwo zrozumieć, dlaczego tak się dzieje, rozważ Xbardzo dużą liczbę i Ybardzo małą liczbę, taką jak ta X + Y = X. Tutaj X + Y + -Xbędzie zero. Ale X + -X + Ybędzie Y.

— David Schwartz,

1

Dla porównania, kanoniczny: Co każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej

— J ...

1

@J ... I co każdy programista powinien wiedzieć o arytmetyki zmiennoprzecinkowej .

— Gilles „SO- przestań być zły”

20

W typowych implementacjach zmiennoprzecinkowych wynik pojedynczej operacji jest generowany tak, jakby operacja została wykonana z nieskończoną precyzją, a następnie zaokrąglana do najbliższej liczby zmiennoprzecinkowej.

Porównaj i : Wynik każdej operacji wykonanej z nieskończoną precyzją jest taki sam, dlatego te same wyniki nieskończonej precyzji są zaokrąglane w identyczny sposób. Innymi słowy, dodawanie zmiennoprzecinkowe jest przemienne. $a+b$ $b+a$

Weź : jest liczbą zmiennoprzecinkową. W przypadku binarnych liczb zmiennoprzecinkowych jest także liczbą zmiennoprzecinkową (wykładnik jest większy o jeden), więc jest dodawane bez żadnego błędu zaokrąglania. Następnie dodaje się do dokładnej wartości . Wynikiem jest dokładna wartość , zaokrąglona do najbliższej liczby zmiennoprzecinkowej. $b + b + a$ $b$ $2b$ $b+b$ $a$ $b+b$ $2b + a$

Weź : dodaje się , a wystąpi błąd zaokrąglenia , więc otrzymamy wynik . Dodaj , a wynikiem będzie dokładna wartość , zaokrąglona do najbliższej liczby zmiennoprzecinkowej. $a + b + b$ $a + b$ $r$ $a+b+r$ $b$ $2b + a + r$

Tak więc w jednym przypadku , zaokrąglone. W drugim przypadku , zaokrąglone. $2b + a$ $2b + a + r$

PS. To, czy dla dwóch konkretnych liczb i oba obliczenia dadzą ten sam wynik, czy nie, zależy od liczb i błędu zaokrąglenia w obliczeniach i jest zwykle trudne do przewidzenia. Zastosowanie pojedynczej lub podwójnej precyzji zasadniczo nie ma znaczenia dla problemu, ale ponieważ błędy zaokrąglania są różne, pojawią się wartości aib, gdzie w pojedynczej precyzji wyniki są równe, a w podwójnej precyzji nie są, lub odwrotnie. Precyzja będzie znacznie wyższa, ale problem polegający na tym, że dwa wyrażenia są matematycznie takie same, ale nie takie same w arytmetyki zmiennoprzecinkowej, pozostaje ten sam. $a$ $b$ $a + b$

PPS. W niektórych językach arytmetykę zmiennoprzecinkową można wykonywać z większą precyzją lub z większym zakresem liczb niż podane w rzeczywistych instrukcjach. W takim przypadku znacznie bardziej prawdopodobne (ale nadal nie jest to gwarantowane), że obie sumy dają ten sam wynik.

PPPS. W komentarzu zapytano, czy powinniśmy zapytać, czy liczby zmiennoprzecinkowe są równe, czy nie. Absolutnie, jeśli wiesz, co robisz. Na przykład, jeśli posortujesz tablicę lub zaimplementujesz zestaw, wpadniesz w straszne kłopoty, jeśli chcesz użyć pojęcia „w przybliżeniu równego”. W graficznym interfejsie użytkownika może być konieczne ponowne obliczenie rozmiarów obiektu, jeśli rozmiar obiektu się zmienił - porównujesz oldSize == newSize, aby uniknąć tego ponownego obliczenia, wiedząc, że w praktyce prawie nigdy nie masz prawie identycznych rozmiarów, a twój program jest poprawny nawet jeśli nastąpi niepotrzebne przeliczenie.

— gnasher729
źródło

W tym szczególnym przypadku b staje się okresowe po konwersji na binarną, więc wszędzie występują błędy zaokrąglania.

— André Souza Lemos

1

@ AndréSouzaLemos bw tej odpowiedzi to nie 0,00004, to jest to, co otrzymujesz po konwersji i zaokrągleniu.

— Aleksiej Romanow

„W typowych implementacjach zmiennoprzecinkowych wynik pojedynczej operacji jest generowany tak, jakby operacja została wykonana z nieskończoną precyzją, a następnie zaokrąglona do najbliższej liczby zmiennoprzecinkowej.” - jest to faktycznie wymagane przez specyfikację, ku mojemu przerażeniu kiedy próbowałem to zaimplementować w kategoriach bramek logicznych (symulator mógł obsługiwać tylko magistrale 64-bitowe).

— John Dvorak,

Naiwne pytanie: czy testowanie równości typu float ma kiedykolwiek sens? Dlaczego większość języków programowania pozwala na test aa == b, w którym oba lub jeden jest zmiennoprzecinkowy?

— curious_cat

Odpowiednia definicja z Wikipedii: „ Maszyna Epsilon określa górną granicę błędu względnego z powodu zaokrąglenia w arytmetyki zmiennoprzecinkowej”.

— Blackhawk

5

Binarny format zmiennoprzecinkowy obsługiwany przez komputery jest zasadniczo podobny do dziesiętnej notacji naukowej stosowanej przez ludzi.

Liczba zmiennoprzecinkowa składa się ze znaku, mantysy (stała szerokość) i wykładnika (stała szerokość), jak poniżej:

+/-  1.0101010101 × 2^12345
sign   ^mantissa^     ^exp^

Regularna notacja naukowa ma podobny format:

+/- 1.23456 × 10^99

Jeśli wykonamy arytmetykę w notacji naukowej ze skończoną precyzją, zaokrąglając po każdej operacji, otrzymamy te same złe efekty, co binarne zmiennoprzecinkowe.

Przykład

Aby to zilustrować, załóżmy, że używamy dokładnie 3 cyfr po przecinku.

a = 99990 = 9.999 × 10^4
b =     3 = 3.000 × 10^0

(a + b) + b

Teraz obliczamy:

c = a + b
  = 99990 + 3      (exact)
  = 99993          (exact)
  = 9.9993 × 10^4  (exact)
  = 9.999 × 10^4.  (rounded to nearest)

Oczywiście w następnym kroku:

d = c + b
  = 99990 + 3 = ...
  = 9.999 × 10^4.  (rounded to nearest)

Stąd (a + b) + b = 9 999 × 10 ⁴ .

(b + b) + a

Ale jeśli wykonaliśmy operacje w innej kolejności:

e = b + b
  = 3 + 3  (exact)
  = 6      (exact)
  = 6.000 × 10^0.  (rounded to nearest)

Następnie obliczamy:

f = e + a
  = 6 + 99990      (exact)
  = 99996          (exact)
  = 9.9996 × 10^4  (exact)
  = 1.000 × 10^5.  (rounded to nearest)

Stąd (b + b) + a = 1,000 x 10 ⁵ , który różni się od innych naszych odpowiedzi.

— Nayuki
źródło

5

Java korzysta z binarnej reprezentacji zmiennoprzecinkowej IEEE 754, która dedykuje 23 cyfry binarne mantysie, która jest znormalizowana na początek pierwszej cyfry znaczącej (pominięta, aby zaoszczędzić miejsce).

$0.00004_{10} = 0.00000000000000101001111100010110101100010001110001101101000111..._{2} = [1.]\color{red}{01001111100010110101100}010001110001101101000111..._{2} \times 2^{-15}$

$1000_{10}+0.00004_{10} =1111101000.00000000000000101001111100010110101100010001110001101101000111..._{2}=[1.]\color{red}{11110100000000000000000}\color{blue}{1}01001111100010110101100010001110001101101000111..._{2}\times 2^{9}$

Części w kolorze czerwonym to mantysy, ponieważ są one faktycznie reprezentowane (przed zaokrągleniem).

$(1000_{10} +0.00004_{10})+0.00004_{10}$ $(0.00004_{10}+0.00004_{10})+1000_{10}$

— André Souza Lemos
źródło

0

Ostatnio natrafiliśmy na podobny problem z zaokrąglaniem. Powyższe odpowiedzi są poprawne, ale dość techniczne.

Znalazłem następujące wyjaśnienie, dlaczego istnieją błędy zaokrąglania. http://csharpindepth.com/Articles/General/FloatingPoint.aspx

TLDR: binarne zmiennoprzecinkowe nie mogą być dokładnie odwzorowane na dziesiętne zmiennoprzecinkowe. Powoduje to niedokładności, które mogą się komplikować podczas operacji matematycznych.

Przykład wykorzystujący liczby zmiennoprzecinkowe dziesiętne: 1/3 + 1/3 + 1/3 zwykle byłby równy 1. Jednak w liczbach dziesiętnych: 0,3333333 + 0,333 333 + 0,333333 nigdy nie jest dokładnie równy 1,000000

To samo dzieje się podczas wykonywania operacji matematycznych na liczbach dziesiętnych binarnych.

— Freek Sanders
źródło