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

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 f a l s e . 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 a 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ść E jednak staje t r u e :$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ę.

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

Weź : dodaje się a + b , a wystąpi błąd zaokrąglenia r , więc otrzymamy wynik a + b + r . Dodaj b , a wynikiem będzie dokładna wartość 2 b + a + r , 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 2 b + a + r , zaokrąglone.$2b + a$$2b + a + r$

PS. To, czy dla dwóch konkretnych liczb i b oba obliczenia dadzą ten sam wynik, czy nie, zależy od liczb i błędu zaokrąglenia w obliczeniach a + b 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.

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.

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}$

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.