Warum liefert das Ändern der Summenreihenfolge ein anderes Ergebnis?

294

Warum liefert das Ändern der Summenreihenfolge ein anderes Ergebnis?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

Sowohl Java als auch JavaScript geben die gleichen Ergebnisse zurück.

Ich verstehe, dass aufgrund der Art und Weise, wie Gleitkommazahlen binär dargestellt werden, einige rationale Zahlen ( wie 1/3 - 0,333333 ... ) nicht genau dargestellt werden können.

Warum wirkt sich eine einfache Änderung der Reihenfolge der Elemente auf das Ergebnis aus?

Marlon Bernardes
quelle
28
Die Summe der reellen Zahlen ist assoziativ und kommutativ. Gleitkommazahlen sind keine reellen Zahlen. Tatsächlich haben Sie gerade bewiesen, dass ihre Operationen nicht kommutativ sind. Es ist ziemlich einfach zu zeigen, dass sie auch nicht assoziativ sind (z (2.0^53 + 1) - 1 == 2.0^53 - 1 != 2^53 == 2^53 + (1 - 1). B. ). Daher ja: Seien Sie vorsichtig bei der Auswahl der Reihenfolge der Beträge und anderer Operationen. Einige Sprachen bieten eine integrierte Funktion zum Ausführen von "hochpräzisen" Summen (z. B. Pythons math.fsum). Daher sollten Sie diese Funktionen möglicherweise anstelle des naiven Summenalgorithmus verwenden.
Bakuriu
1
@RBerteig Dies kann ermittelt werden, indem die Reihenfolge der Operationen der Sprache auf arithmetische Ausdrücke untersucht wird. Sofern die Darstellung von Gleitkommazahlen im Speicher nicht unterschiedlich ist, sind die Ergebnisse gleich, wenn die Operatorprioritätsregeln gleich sind. Ein weiterer wichtiger Punkt: Ich frage mich, wie lange die Entwickler, die Bankanwendungen entwickeln, gebraucht haben, um dies herauszufinden. Diese zusätzlichen 0000000000004 Cent summieren sich wirklich!
Chris Cirefice
3
@ChrisCirefice: Wenn Sie 0,00000004 Cent haben , machen Sie es falsch. Sie sollten niemals einen binären Gleitkommatyp für Finanzberechnungen verwenden.
Daniel Pryden
2
@DanielPryden Ach, leider war es ein Witz ... nur die Idee herumzuwerfen, dass Leute, die wirklich diese Art von Problem lösen müssen, einen der wichtigsten Jobs hatten, die Sie kennen, den Geldstatus der Leute und all das zu halten . Ich war sehr sarkastisch ...
Chris Cirefice
6
Sehr trocken (und alt, aber immer noch relevant): Was jeder Informatiker über Gleitkomma-Arithmetik wissen sollte
Brian

Antworten:

276

Vielleicht ist diese Frage dumm, aber warum wirkt sich eine einfache Änderung der Reihenfolge der Elemente auf das Ergebnis aus?

Dadurch werden die Punkte, an denen die Werte gerundet werden, basierend auf ihrer Größe geändert. Nehmen wir als Beispiel für die Art der Dinge, die wir sehen, an, dass wir anstelle des binären Gleitkommas einen dezimalen Gleitkommatyp mit 4 signifikanten Stellen verwenden, bei dem jede Addition mit "unendlicher" Genauigkeit ausgeführt und dann auf gerundet wird die nächste darstellbare Zahl. Hier sind zwei Summen:

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)

Wir brauchen nicht einmal Nicht-Ganzzahlen, damit dies ein Problem darstellt:

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

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

Dies zeigt möglicherweise deutlicher, dass der wichtige Teil darin besteht, dass wir eine begrenzte Anzahl von signifikanten Stellen haben - nicht eine begrenzte Anzahl von Dezimalstellen . Wenn wir immer die gleiche Anzahl von Dezimalstellen beibehalten könnten, wären wir zumindest mit Addition und Subtraktion in Ordnung (solange die Werte nicht überlaufen). Das Problem ist, dass bei größeren Zahlen kleinere Informationen verloren gehen - in diesem Fall wird der 10001 auf 10000 gerundet. (Dies ist ein Beispiel für das Problem, das Eric Lippert in seiner Antwort festgestellt hat .)

Es ist wichtig zu beachten, dass die Werte in der ersten Zeile der rechten Seite in allen Fällen gleich sind. Obwohl es wichtig ist zu verstehen, dass Ihre Dezimalzahlen (23,53, 5,88, 17,64) nicht genau als doubleWerte dargestellt werden, ist dies der Fall nur ein Problem wegen der oben gezeigten Probleme.

Jon Skeet
quelle
10
May extend this later - out of time right now!warten gespannt auf das @ Jon
Prateek
3
Wenn ich sage, dass ich später auf eine Antwort zurückkommen werde, ist die Community etwas weniger freundlich zu mir. <Geben Sie hier eine Art unbeschwertes Emoticon ein, um zu zeigen, dass ich einen Scherz mache und kein Idiot. Ich werde später darauf zurückkommen.
Grady Player
2
@ZongZhengLi: Während es sicherlich wichtig ist, das zu verstehen, ist es in diesem Fall nicht die Hauptursache. Sie könnten ein ähnliches Beispiel mit Werten schreiben , die sind genau binär dargestellt, und die gleiche Wirkung sehen. Das Problem hierbei ist, dass Informationen in großem Maßstab und Informationen in kleinem Maßstab gleichzeitig beibehalten werden.
Jon Skeet
1
@Buksy: Auf 10000 gerundet - weil es sich um einen Datentyp handelt, der nur 4 signifikante Ziffern speichern kann. (also x.xxx * 10 ^ n)
Jon Skeet
3
@meteors: Nein, es verursacht keinen Überlauf - und Sie verwenden die falschen Zahlen. Es ist 10001, das auf 10000 gerundet wird, nicht 1001, das auf 1000 gerundet wird. Um es klarer zu machen, würde 54321 auf 54320 gerundet werden - weil das nur vier signifikante Stellen hat. Es gibt einen großen Unterschied zwischen "vier signifikanten Ziffern" und "einem Maximalwert von 9999". Wie ich bereits sagte, repräsentieren Sie im Grunde genommen x.xxx * 10 ^ n, wobei für 10000 x.xxx 1.000 und n 4 wäre. Dies ist genau wie doubleund floatbei sehr großen Zahlen aufeinanderfolgende darstellbare Zahlen sind mehr als 1 voneinander entfernt.
Jon Skeet
52

Hier ist, was in binären los ist. Wie wir wissen, können einige Gleitkommawerte nicht genau binär dargestellt werden, selbst wenn sie genau dezimal dargestellt werden können. Diese 3 Zahlen sind nur Beispiele für diese Tatsache.

Mit diesem Programm gebe ich die hexadezimalen Darstellungen jeder Zahl und die Ergebnisse jeder Addition aus.

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);
   }
}

Die printValueAndInHexMethode ist nur ein Hex-Drucker-Helfer.

Die Ausgabe ist wie folgt:

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

Die ersten 4 Zahlen sind x, y, zund shexadezimalen Darstellungen s‘. In der IEEE-Gleitkomma-Darstellung repräsentieren die Bits 2-12 den binären Exponenten , dh die Skala der Zahl. (Das erste Bit ist das Vorzeichenbit und die verbleibenden Bits für die Mantisse .) Der dargestellte Exponent ist tatsächlich die Binärzahl minus 1023.

Die Exponenten für die ersten 4 Zahlen werden extrahiert:

    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

Erster Satz von Ergänzungen

Die zweite Zahl ( y) ist kleiner. Wenn Sie diese beiden Zahlen addieren x + y, werden die letzten 2 Bits der zweiten Zahl ( 01) außerhalb des Bereichs verschoben und nicht in die Berechnung einbezogen.

Der zweite Zusatz fügt x + yund zund fügt zwei Zahlen derselben Skala hinzu.

Zweiter Satz von Ergänzungen

Hier x + ztritt zuerst auf. Sie haben den gleichen Maßstab, aber sie ergeben eine Zahl, die höher ist:

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

Die zweite Addition fügt x + zund hinzu y, und jetzt werden 3 Bits entfernt y, um die Zahlen ( 101) hinzuzufügen . Hier muss es eine Runde nach oben geben, da das Ergebnis die nächste Gleitkommazahl ist: 4047866666666666für den ersten Satz von Ergänzungen vs. 4047866666666667für den zweiten Satz von Ergänzungen. Dieser Fehler ist signifikant genug, um im Ausdruck der Gesamtsumme angezeigt zu werden.

Seien Sie abschließend vorsichtig, wenn Sie mathematische Operationen an IEEE-Zahlen ausführen. Einige Darstellungen sind ungenau und werden noch ungenauer, wenn die Skalen unterschiedlich sind. Addiere und subtrahiere Zahlen ähnlichen Maßstabs, wenn du kannst.

rgettman
quelle
Die unterschiedlichen Skalen sind der wichtige Teil. Sie könnten (in Dezimalzahl) die genauen Werte schreiben, die binär als Eingaben dargestellt werden, und dennoch das gleiche Problem haben.
Jon Skeet
@rgettman Als Programmierer gefällt mir Ihre Antwort besser =)+1 für Ihren Hex-Drucker-Helfer ... das ist wirklich ordentlich!
ADTC
44

Jons Antwort ist natürlich richtig. In Ihrem Fall ist der Fehler nicht größer als der Fehler, den Sie bei einer einfachen Gleitkommaoperation akkumulieren würden. Sie haben ein Szenario, in dem in einem Fall kein Fehler und in einem anderen ein winziger Fehler auftritt. Das ist eigentlich kein so interessantes Szenario. Eine gute Frage ist: Gibt es Szenarien, in denen die Änderung der Berechnungsreihenfolge von einem winzigen Fehler zu einem (relativ) enormen Fehler führt? Die Antwort lautet eindeutig ja.

Betrachten Sie zum Beispiel:

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;

Offensichtlich wären sie in exakter Arithmetik gleich. Es ist unterhaltsam zu versuchen, Werte für a, b, c, d, e, f, g, h zu finden, so dass sich die Werte von x1 und x2 und x3 um eine große Menge unterscheiden. Sehen Sie, ob Sie das können!

Eric Lippert
quelle
Wie definieren Sie eine große Menge? Sprechen wir in der Größenordnung von 1000steln? 100stel? 1's ???
Cruncher
3
@Cruncher: Berechnen Sie das genaue mathematische Ergebnis sowie die x1- und x2-Werte. Nennen Sie den genauen mathematischen Unterschied zwischen den wahren und berechneten Ergebnissen e1 und e2. Es gibt jetzt verschiedene Möglichkeiten, über die Fehlergröße nachzudenken. Das erste ist: Können Sie ein Szenario finden, in dem entweder | e1 / e2 | oder | e2 / e1 | sind groß? Können Sie den Fehler des einen zehnmal so groß machen wie den Fehler des anderen? Das interessantere ist jedoch, wenn Sie den Fehler von einem zu einem signifikanten Bruchteil der Größe der richtigen Antwort machen können.
Eric Lippert
1
Mir ist klar, dass er über Laufzeit spricht, aber ich frage mich: Wenn der Ausdruck ein Ausdruck zur Kompilierungszeit (z. B. constexpr) war, sind Compiler intelligent genug, um den Fehler zu minimieren?
Kevin Hsu
@kevinhsu im Allgemeinen nein, der Compiler ist nicht so schlau. Natürlich könnte der Compiler die Operation in exakter Arithmetik ausführen, wenn er dies wünscht, aber normalerweise nicht.
Eric Lippert
8
@frozenkoi: Ja, der Fehler kann sehr leicht unendlich sein. Betrachten Sie zum Beispiel das C #: double d = double.MaxValue; Console.WriteLine(d + d - d - d); Console.WriteLine(d - d + d - d);- Die Ausgabe ist Infinity dann 0.
Jon Skeet
10

Dies deckt tatsächlich viel mehr als nur Java und Javascript ab und würde wahrscheinlich jede Programmiersprache beeinflussen, die Floats oder Doubles verwendet.

Im Speicher verwenden Gleitkommazahlen ein spezielles Format nach IEEE 754 (der Konverter bietet eine viel bessere Erklärung als ich).

Wie auch immer, hier ist der Schwimmerkonverter.

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

Die Sache mit der Reihenfolge der Operationen ist die "Feinheit" der Operation.

Ihre erste Zeile ergibt 29,41 aus den ersten beiden Werten, was uns 2 ^ 4 als Exponenten gibt.

Ihre zweite Zeile ergibt 41,17, was uns 2 ^ 5 als Exponenten gibt.

Wir verlieren eine signifikante Zahl, indem wir den Exponenten erhöhen, was wahrscheinlich das Ergebnis verändern wird.

Wenn Sie das letzte Bit ganz rechts für 41,17 ein- und ausschalten, können Sie sehen, dass etwas so "unbedeutendes" wie 1/2 ^ 23 des Exponenten ausreicht, um diese Gleitkommadifferenz zu verursachen.

Bearbeiten: Für diejenigen unter Ihnen, die sich an bedeutende Zahlen erinnern, würde dies unter diese Kategorie fallen. 10 ^ 4 + 4999 mit einer signifikanten Zahl von 1 wird 10 ^ 4 sein. In diesem Fall ist die signifikante Zahl viel kleiner, aber wir können die Ergebnisse mit der daran angehängten .00000000004 sehen.

Kompass
quelle
9

Gleitkommazahlen werden im IEEE 754-Format dargestellt, das eine bestimmte Bitgröße für die Mantisse (Signifikand) bereitstellt. Leider gibt Ihnen dies eine bestimmte Anzahl von 'Bruchbausteinen', mit denen Sie spielen können, und bestimmte Bruchwerte können nicht genau dargestellt werden.

Was in Ihrem Fall passiert, ist, dass im zweiten Fall die Addition aufgrund der Reihenfolge, in der die Additionen ausgewertet werden, wahrscheinlich auf ein genaues Problem stößt. Ich habe die Werte nicht berechnet, aber es könnte zum Beispiel sein, dass 23,53 + 17,64 nicht genau dargestellt werden können, während 23,53 + 5,88 dies können.

Leider ist es ein bekanntes Problem, mit dem Sie sich nur befassen müssen.

jbx
quelle
6

Ich glaube, das hat mit der Reihenfolge der Auswertung zu tun. Während die Summe in einer mathematischen Welt natürlich dieselbe ist, ist sie in der binären Welt anstelle von A + B + C = D gleich

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

Es gibt also diesen zweiten Schritt, in dem Gleitkommazahlen aussteigen können.

Wenn Sie die Reihenfolge ändern,

A + C = F
F + B = D(2)
Hotforfeature
quelle
4
Ich denke, diese Antwort vermeidet den wahren Grund. "Es gibt diesen zweiten Schritt, in dem Gleitkommazahlen aussteigen können". Dies ist natürlich wahr, aber wir möchten erklären, warum .
Zong