Dlaczego zmiana kolejności sum zwraca inny wynik?

Dlaczego zmiana kolejności sum zwraca inny wynik?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

Zarówno Java, jak i JavaScript zwracają te same wyniki.

Rozumiem, że ze względu na sposób, w jaki liczby zmiennoprzecinkowe są reprezentowane w postaci binarnej, niektórych liczb wymiernych ( jak 1/3 - 0,333333 ... ) nie można dokładnie przedstawić.

Dlaczego zmiana kolejności elementów wpływa na wynik?

Być może to pytanie jest głupie, ale dlaczego po prostu zmiana kolejności elementów wpływa na wynik?

Zmieni to punkty, w których wartości są zaokrąglane, w zależności od ich wielkości. Jako przykład tego rodzaju rzeczy, które widzimy, udawajmy, że zamiast binarnej zmiennoprzecinkową, używaliśmy ułamek dziesiętny pływającą typu punkt z 4 cyfr znaczących, gdzie każdy dodatek jest przeprowadzanych na „nieskończonej” precyzją, a następnie zaokrąglane do najbliższy reprezentowalny numer. Oto dwie kwoty:

1/3 + 2/3 + 2/3 = (0.3333 + 0.6667) + 0.6667
                = 1.000 + 0.6667 (no rounding needed!)
                = 1.667 (where 1.6667 is rounded to 1.667)

2/3 + 2/3 + 1/3 = (0.6667 + 0.6667) + 0.3333
                = 1.333 + 0.3333 (where 1.3334 is rounded to 1.333)
                = 1.666 (where 1.6663 is rounded to 1.666)

Nie potrzebujemy nawet liczb całkowitych, aby był to problem:

10000 + 1 - 10000 = (10000 + 1) - 10000
                  = 10000 - 10000 (where 10001 is rounded to 10000)
                  = 0

10000 - 10000 + 1 = (10000 - 10000) + 1
                  = 0 + 1
                  = 1

To prawdopodobnie bardziej wyraźnie pokazuje, że ważną częścią jest to, że mamy ograniczoną liczbę cyfr znaczących - a nie ograniczoną liczbę miejsc dziesiętnych . Gdybyśmy zawsze mogli zachować tę samą liczbę miejsc po przecinku, to z dodawaniem i odejmowaniem przynajmniej byłoby dobrze (o ile wartości się nie przelały). Problem polega na tym, że gdy dojdziesz do większej liczby, mniejsze informacje zostaną utracone - w tym przypadku 10001 zostanie zaokrąglone do 10000. (Jest to przykład problemu, który zauważył Eric Lippert w swojej odpowiedzi ).

Należy zauważyć, że wartości w pierwszym wierszu po prawej stronie są takie same we wszystkich przypadkach - dlatego ważne jest, aby zrozumieć, że liczby dziesiętne (23,53, 5,88, 17,64) nie będą reprezentowane dokładnie jako doublewartości, to znaczy tylko problem z powodu problemów pokazanych powyżej.

Oto, co dzieje się w systemie binarnym. Jak wiemy, niektórych wartości zmiennoprzecinkowych nie można przedstawić dokładnie w postaci binarnej, nawet jeśli można je przedstawić dokładnie w postaci dziesiętnej. Te 3 liczby są tylko przykładami tego faktu.

Za pomocą tego programu wypisuję szesnastkową reprezentację każdej liczby i wyniki każdego dodania.

public class Main{
   public static void main(String args[]) {
      double x = 23.53;   // Inexact representation
      double y = 5.88;    // Inexact representation
      double z = 17.64;   // Inexact representation
      double s = 47.05;   // What math tells us the sum should be; still inexact

      printValueAndInHex(x);
      printValueAndInHex(y);
      printValueAndInHex(z);
      printValueAndInHex(s);

      System.out.println("--------");

      double t1 = x + y;
      printValueAndInHex(t1);
      t1 = t1 + z;
      printValueAndInHex(t1);

      System.out.println("--------");

      double t2 = x + z;
      printValueAndInHex(t2);
      t2 = t2 + y;
      printValueAndInHex(t2);
   }

   private static void printValueAndInHex(double d)
   {
      System.out.println(Long.toHexString(Double.doubleToLongBits(d)) + ": " + d);
   }
}

Ta printValueAndInHexmetoda to tylko pomocnik drukarki szesnastkowej.

Dane wyjściowe są następujące:

403787ae147ae148: 23.53
4017851eb851eb85: 5.88
4031a3d70a3d70a4: 17.64
4047866666666666: 47.05
--------
403d68f5c28f5c29: 29.41
4047866666666666: 47.05
--------
404495c28f5c28f6: 41.17
4047866666666667: 47.050000000000004

Pierwsze 4 numery są x, y, zi s„s reprezentacje szesnastkowym. W reprezentacji zmiennoprzecinkowej IEEE bity 2-12 reprezentują wykładnik binarny , to znaczy skalę liczby. (Pierwszy bit jest bitem znaku, a pozostałe bity mantysy .) Przedstawiony wykładnik to tak naprawdę liczba binarna minus 1023.

Wykładniki dla pierwszych 4 liczb są wyodrębniane:

    sign|exponent
403 => 0|100 0000 0011| => 1027 - 1023 = 4
401 => 0|100 0000 0001| => 1025 - 1023 = 2
403 => 0|100 0000 0011| => 1027 - 1023 = 4
404 => 0|100 0000 0100| => 1028 - 1023 = 5

Pierwszy zestaw dodatków

Druga liczba ( y) ma mniejszą wartość. Podczas dodawania tych dwóch liczb w celu uzyskania x + y, ostatnie 2 bity drugiej liczby ( 01) są przesuwane poza zakres i nie są uwzględniane w obliczeniach.

Drugi dodatek dodaje x + yi zdodaje dwie liczby w tej samej skali.

Drugi zestaw dodatków

Tutaj x + zpojawia się pierwszy. Są tej samej skali, ale dają liczbę wyższą w skali:

404 => 0|100 0000 0100| => 1028 - 1023 = 5

Drugi dodatek dodaje x + zi y, a teraz 3 bity są usuwane, yaby dodać liczby ( 101). Tutaj musi być zaokrąglenie w górę, ponieważ wynikiem jest następna liczba zmiennoprzecinkowa w górę: 4047866666666666dla pierwszego zestawu dodatków vs. 4047866666666667dla drugiego zestawu dodatków. Ten błąd jest wystarczająco znaczący, aby pokazać go na wydruku sumy.

Podsumowując, zachowaj ostrożność podczas wykonywania operacji matematycznych na liczbach IEEE. Niektóre reprezentacje są niedokładne i stają się jeszcze bardziej niedokładne, gdy skale są różne. Dodaj i odejmij liczby o podobnej skali, jeśli możesz.

Odpowiedź Jona jest oczywiście poprawna. W twoim przypadku błąd nie jest większy niż błąd, który kumulowałbyś się podczas wykonywania dowolnej prostej operacji zmiennoprzecinkowej. Masz scenariusz, w którym w jednym przypadku występuje błąd zerowy, aw innym niewielki błąd; to nie jest tak interesujący scenariusz. Dobre pytanie brzmi: czy istnieją scenariusze, w których zmiana kolejności obliczeń zmienia się z drobnego błędu na (relatywnie) ogromny błąd? Odpowiedź jest jednoznaczna: tak.

Rozważ na przykład:

x1 = (a - b) + (c - d) + (e - f) + (g - h);

vs

x2 = (a + c + e + g) - (b + d + f + h);

vs

x3 = a - b + c - d + e - f + g - h;

Oczywiście w dokładnej arytmetyce byłyby takie same. Zabawne jest próbowanie znalezienia wartości dla a, b, c, d, e, f, g, h tak, aby wartości x1 oraz x2 i x3 różniły się dużą ilością. Sprawdź, czy możesz to zrobić!

W rzeczywistości obejmuje to znacznie więcej niż tylko Javę i JavaScript, i prawdopodobnie wpłynęłoby na każdy język programowania przy użyciu liczb zmiennoprzecinkowych lub podwójnych.

W pamięci zmiennoprzecinkowe używają specjalnego formatu zgodnego z normą IEEE 754 (konwerter zapewnia znacznie lepsze wyjaśnienie niż mogę).

Tak czy inaczej, oto konwerter pływaka.

http://www.h-schmidt.net/FloatConverter/

Kolejność operacji polega na „dokładności” operacji.

Twój pierwszy wiersz daje 29,41 z pierwszych dwóch wartości, co daje nam 2 ^ 4 jako wykładnik potęgi.

Twoja druga linia daje 41,17, co daje nam 2 ^ 5 jako wykładnik.

Tracimy znaczącą liczbę, zwiększając wykładnik, co może zmienić wynik.

Spróbuj zaznaczyć ostatni bit z prawej i prawej strony przy 41.17, a zobaczysz, że coś tak „nieznaczącego” jak 1/2 ^ 23 wykładnika byłoby wystarczające, aby spowodować tę różnicę zmiennoprzecinkową.

Edycja: dla tych z was, którzy pamiętają znaczące liczby, mieści się to w tej kategorii. 10 ^ 4 + 4999 ze znaczącą liczbą 1 będzie wynosić 10 ^ 4. W tym przypadku znacząca liczba jest znacznie mniejsza, ale możemy zobaczyć wyniki z dołączonym .00000000004.

Liczby zmiennoprzecinkowe są reprezentowane przy użyciu formatu IEEE 754, który zapewnia określony rozmiar bitów dla mantysy (znaczenia). Niestety daje to określoną liczbę „ułamkowych elementów budulcowych” do zabawy, a niektórych wartości ułamkowych nie można dokładnie przedstawić.

W twoim przypadku dzieje się tak, że w drugim przypadku dodanie prawdopodobnie napotyka pewne problemy z precyzją ze względu na kolejność, w jakiej dodatki są oceniane. Nie obliczyłem wartości, ale może być na przykład, że 23,53 + 17,64 nie można dokładnie przedstawić, podczas gdy 23,53 + 5,88 może.

Niestety jest to znany problem, z którym musisz sobie poradzić.

Uważam, że ma to związek z kolejnością ewakuacji. Chociaż suma jest naturalnie taka sama w świecie matematyki, w świecie binarnym zamiast A + B + C = D, to

A + B = E
E + C = D(1)

Jest więc drugi krok, w którym liczby zmiennoprzecinkowe mogą zejść.

Kiedy zmienisz zamówienie,

A + C = F
F + B = D(2)