Ungleichheit durch Ungenauigkeit des Schwimmers

15

Zumindest in Java, wenn ich diesen Code schreibe:

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

der Wert von wäre . Ich glaube, dies liegt an der Tatsache, dass Floats in Bezug auf die genaue Darstellung von Zahlen sehr begrenzt sind. Aber ich verstehe nicht, warum nur das Ändern der Position von diese Ungleichheit verursachen kann.f a l s eefeinlseein

Ich habe das s in Zeile 3 und 4 wie folgt auf eins reduziert , der Wert von jedoch :betrue

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

Was genau ist in Zeile 3 und 4 passiert? Warum sind Additionsoperationen mit Floats nicht assoziativ?

Danke im Voraus.

Bekannte Zeta
quelle
16
Als Ihr Beispiel zeigt, zeigen zusätzlich schwimmend ist kommutativ. Aber es ist nicht assoziativ.
Yuval Filmus
1
Ich ermutige Sie, die grundlegenden Definitionen nachzuschlagen. Beachten Sie auch, dass der Compiler als analysiert (der Zusatz wird links zugeordnet). ( r + s ) + tr+s+t(r+s)+t
Yuval Filmus
2
Betrachten Sie Xeine sehr große und Yeine sehr kleine Zahl, um zu sehen, warum dies der Fall sein sollte X + Y = X. Hier X + Y + -Xwird Null sein. Aber X + -X + Ywird Y.
David Schwartz
1
@J ... und was jeder Programmierer über Gleitkomma-Arithmetik wissen sollte .
Gilles 'SO- hör auf böse zu sein'

Antworten:

20

In typischen Gleitkommaimplementierungen wird das Ergebnis einer einzelnen Operation so erzeugt, als ob die Operation mit unendlicher Genauigkeit ausgeführt und dann auf die nächste Gleitkommazahl gerundet wurde.

Vergleichen Sie und b + a : Das Ergebnis jeder mit unendlicher Genauigkeit ausgeführten Operation ist das gleiche, daher werden diese identischen Ergebnisse mit unendlicher Genauigkeit auf identische Weise gerundet. Mit anderen Worten ist die Gleitkommazugabe kommutativ.ein+bb+ein

Nehmen wir : ist eine Gleitkommazahl. Bei binären Gleitkommazahlen ist auch eine Gleitkommazahl (der Exponent ist um eins größer), daher wird ohne Rundungsfehler addiert. Dann auf dem zusätzlichen genauen Wert . Das Ergebnis ist der exakte Wert , gerundet auf die nächste Gleitkommazahl.b 2 b b + b a b + b 2 b + ab+b+einb2bb+beinb+b2b+ein

Nehmen Sie : wird addiert und es tritt ein Rundungsfehler , so dass wir das Ergebnis . Addiere und das Ergebnis ist der exakte Wert , gerundet auf die nächste Gleitkommazahl.a + b r a + b + r b 2 b + a + rein+b+bein+brein+b+rb2b+ein+r

Also in einem Fall , gerundet. Im anderen Fall ist gerundet.2 b + a + r2b+ein2b+ein+r

PS. Ob für zwei bestimmte Zahlen und beide Berechnungen das gleiche Ergebnis liefern oder nicht, hängt von den Zahlen und dem Rundungsfehler in der Berechnung und ist normalerweise schwer vorherzusagen. Die Verwendung von einfacher oder doppelter Genauigkeit macht im Prinzip keinen Unterschied zum Problem, aber da die Rundungsfehler unterschiedlich sind, gibt es Werte für a und b, bei denen die Ergebnisse bei einfacher Genauigkeit gleich sind und bei doppelter Genauigkeit nicht oder umgekehrt. Die Genauigkeit wird viel höher sein, aber das Problem, dass zwei Ausdrücke mathematisch gleich, aber in der Gleitkomma-Arithmetik nicht gleich sind, bleibt gleich.b a + beinbein+b

PPS. In einigen Sprachen kann die Gleitkomma-Arithmetik mit höherer Genauigkeit oder einem höheren Zahlenbereich als in den tatsächlichen Anweisungen angegeben ausgeführt werden. In diesem Fall wäre es sehr viel wahrscheinlicher (aber immer noch nicht garantiert), dass beide Summen das gleiche Ergebnis liefern.

PPPS. In einem Kommentar wurde gefragt, ob Gleitkommazahlen gleich sind oder nicht. Absolut, wenn Sie wissen, was Sie tun. Wenn Sie beispielsweise ein Array sortieren oder eine Menge implementieren, geraten Sie in große Schwierigkeiten, wenn Sie den Begriff "ungefähr gleich" verwenden möchten. In einer grafischen Benutzeroberfläche müssen Sie möglicherweise die Objektgrößen neu berechnen, wenn sich die Größe eines Objekts geändert hat. Sie vergleichen oldSize == newSize, um diese Neuberechnung zu vermeiden, da Sie in der Praxis fast nie nahezu identische Größen haben und Ihr Programm korrekt ist auch wenn es eine unnötige Neuberechnung gibt.

gnasher729
quelle
In diesem speziellen Fall wird b periodisch, wenn es in binär umgewandelt wird, so dass es überall Rundungsfehler gibt.
André Souza Lemos
1
@ AndréSouzaLemos bin dieser Antwort ist nicht 0,00004, es ist das, was Sie nach der Umrechnung und Rundung erhalten.
Alexey Romanov
"In typischen Gleitkommaimplementierungen wird das Ergebnis einer einzelnen Operation so erzeugt, als ob die Operation mit unendlicher Genauigkeit ausgeführt und dann auf die nächste Gleitkommazahl gerundet worden wäre." Als ich versuchte, dies tatsächlich in Form von Logikgattern zu implementieren (der Simulator konnte nur 64-Bit-Busse verarbeiten).
John Dvorak
Naive Frage: Ist es jemals sinnvoll, auf Gleichheit mit dem Schwimmer zu prüfen? Warum erlauben die meisten Programmiersprachen einen aa == b-Test, bei dem beide oder einer float ist?
curious_cat
Relevante Definition aus Wikipedia: " Machine Epsilon gibt eine Obergrenze für den relativen Fehler aufgrund von Rundungen in Gleitkomma-Arithmetik an."
Blackhawk
5

Das von Computern unterstützte binäre Gleitkommaformat ähnelt im Wesentlichen der vom Menschen verwendeten wissenschaftlichen Dezimalschreibweise.

Eine Gleitkommazahl besteht aus einem Vorzeichen, einer Mantisse (feste Breite) und einem Exponenten (feste Breite) wie folgt:

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

Regelmäßige wissenschaftliche Notation hat ein ähnliches Format:

+/- 1.23456 × 10^99

Wenn wir in wissenschaftlicher Notation mit endlicher Genauigkeit rechnen und nach jeder Operation runden, erhalten wir alle die gleichen schlechten Effekte wie bei binären Gleitkommazahlen.


Beispiel

Nehmen wir zur Veranschaulichung an, wir verwenden genau drei Nachkommastellen.

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

(a + b) + b

Nun berechnen wir:

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

Im nächsten Schritt natürlich:

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

Daher ist (a + b) + b = 9,999 × 10 4 .

(b + b) + a

Aber wenn wir die Operationen in einer anderen Reihenfolge durchgeführt haben:

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

Als nächstes berechnen wir:

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

Daher ist (b + b) + a = 1.000 × 10 5 , was sich von unserer anderen Antwort unterscheidet.

Nayuki
quelle
5

Java verwendet die IEEE 754-Gleitkommadarstellung, bei der der Mantisse 23 Binärziffern zugewiesen werden, die zu Beginn mit der ersten signifikanten Ziffer normalisiert werden (aus Platzgründen weggelassen).

0,0000410=0.000000000000001010011111000101101100010001110001101101000111 ...2=[1.]01001111100010110101100010001110001101101000111 ...2×2-15

100010+0,0000410=1111101000.00000000000000101001111100010110101100010001110001101101000111 ...2=[1.]11110100000000000000000101001111100010110101100010001110001101101000111 ...2×29

Die roten Teile sind die Mantissen, wie sie tatsächlich dargestellt sind (vor dem Runden).

(100010+0,0000410)+0,0000410(0,0000410+0,0000410)+100010

André Souza Lemos
quelle
0

Wir sind kürzlich auf ein ähnliches Rundungsproblem gestoßen. Die oben genannten Antworten sind richtig, jedoch recht technisch.

Ich fand das Folgende eine gute Erklärung dafür, warum Rundungsfehler existieren. http://csharpindepth.com/Articles/General/FloatingPoint.aspx

TLDR: Binäre Gleitkommazahlen können nicht genau auf dezimale Gleitkommazahlen abgebildet werden. Dies führt zu Ungenauigkeiten, die sich bei mathematischen Operationen verschlimmern können.

Ein Beispiel mit dezimalen Gleitkommazahlen: 1/3 + 1/3 + 1/3 wäre normalerweise gleich 1. In Dezimalzahlen: 0,333333 + 0,333333 + 0,333333 ist jedoch niemals genau gleich 1,000000

Gleiches gilt für mathematische Operationen mit binären Dezimalstellen.

Freek Sanders
quelle