Ein Beispiel in Gotw 67

Question

Es gibt ein Beispiel in http://www.gotw.ca/gotw/067.htm

int main()
{
  double x = 1e8;
  //float x = 1e8;
  while( x > 0 )
  {
    --x;
  }
}

Wenn Sie double in float ändern, ist das in VS2008 eine Endlosschleife. Gemäß der Gotw-Erklärung:

Was ist, wenn der Schwimmer nicht genau das kann, was er will? 1e8? Dann beginnt das geänderte Programm mit dem Rückwärtszählen, wird aber irgendwann einen Wert N erreichen, der nicht dargestellt werden kann und bei dem N-1 == N (wegen der unzureichenden Fließkommagenauigkeit)... und dann bleibt die Schleife bei diesem Wert hängen, bis der Rechner, auf dem das Programm läuft, keinen Strom mehr hat.

Von dem, was ich verstehe, ist die IEEE754 Float eine einfache Präzision (32 Bits) und der Bereich der Float sollte +/- 3.4e +/- 38 und es sollte eine 7 Ziffern signifikant sein.

Aber ich verstehe immer noch nicht, wie genau das geschieht: "schließlich einen Wert N erreichen, der nicht dargestellt werden kann und für den N-1 == N ist (wegen unzureichender Gleitkommagenauigkeit)". Kann jemand versuchen, diesen Teil zu erklären?

Ein paar zusätzliche Informationen: Wenn ich double x = 1e8 verwende, ist es in etwa 1 Sekunde fertig, wenn ich es in float x = 1e8 ändere, läuft es viel länger (läuft immer noch nach 5 Minuten), auch wenn ich es ändere in float x = 1e7; war es in etwa 1 Sekunde beendet.

Meine Testumgebung ist VS2008.

Übrigens bin ich NICHT Ich frage nach der grundlegenden Erklärung des IEEE-754-Formats, da ich dieses bereits verstehe.

Danke

Answer 1

Nehmen wir einmal an, wir haben einen Prozessor, der eine Fließkommazahl mit 7 signifikanten Dezimalstellen und eine Mantisse mit, sagen wir, 2 Dezimalstellen darstellt. Dann würde die Zahl 1e8 wie folgt gespeichert werden

1.000 000 e 08

(wobei das "." und das "e" nicht tatsächlich gespeichert werden müssen).

Sie wollen nun also "1e8 - 1" berechnen. 1 wird dargestellt als

1.000 000 e 00

Um nun die Subtraktion durchzuführen, führen wir zunächst eine Subtraktion mit unendlicher Genauigkeit durch, normalisieren dann so, dass die erste Ziffer vor dem "." zwischen 1 und 9 liegt, und runden schließlich auf den nächsten darstellbaren Wert (z. B. mit Bruch bei Gerade). Das Ergebnis von "1e8 - 1" mit unendlicher Genauigkeit ist

0.99 999 999 e 08

oder normalisiert

9.9 999 999 e 07

Wie man sieht, benötigt das Ergebnis mit unendlicher Genauigkeit eine Stelle mehr im Signifikanten, als unsere Architektur tatsächlich zur Verfügung stellt; daher müssen wir das unendlich genaue Ergebnis auf 7 signifikante Stellen runden (und neu normalisieren), was zu folgendem Ergebnis führt

1.000 000 e 08

Am Ende steht also "1e8 - 1 == 1e8" und die Schleife wird nie beendet.

In Wirklichkeit verwenden Sie binäre IEEE 754-Fließkommazahlen, die ein wenig anders sind, aber das Prinzip ist in etwa dasselbe.

Answer 2

Die Operation x-- ist (in diesem Fall) gleichbedeutend mit x = x - 1 . Das bedeutet, dass der ursprüngliche Wert von x genommen wird, 1 wird subtrahiert (mit unendlicher Genauigkeit, wie in IEEE 754-1985 vorgeschrieben), und das Ergebnis wird auf den nächsten Wert der float Wertebereich.

Das gerundete Ergebnis für die Zahlen 1.0e8f + i ist gegeben für i in [-10;10] unten:

 -10: 9.9999992E7     (binary +|10011001|01111101011110000011111)
  -9: 9.9999992E7     (binary +|10011001|01111101011110000011111)
  -8: 9.9999992E7     (binary +|10011001|01111101011110000011111)
  -7: 9.9999992E7     (binary +|10011001|01111101011110000011111)
  -6: 9.9999992E7     (binary +|10011001|01111101011110000011111)
  -5: 9.9999992E7     (binary +|10011001|01111101011110000011111)
  -4: 1.0E8           (binary +|10011001|01111101011110000100000)
  -3: 1.0E8           (binary +|10011001|01111101011110000100000)
  -2: 1.0E8           (binary +|10011001|01111101011110000100000)
  -1: 1.0E8           (binary +|10011001|01111101011110000100000)
   0: 1.0E8           (binary +|10011001|01111101011110000100000)
   1: 1.0E8           (binary +|10011001|01111101011110000100000)
   2: 1.0E8           (binary +|10011001|01111101011110000100000)
   3: 1.0E8           (binary +|10011001|01111101011110000100000)
   4: 1.0E8           (binary +|10011001|01111101011110000100000)
   5: 1.00000008E8    (binary +|10011001|01111101011110000100001)
   6: 1.00000008E8    (binary +|10011001|01111101011110000100001)
   7: 1.00000008E8    (binary +|10011001|01111101011110000100001)
   8: 1.00000008E8    (binary +|10011001|01111101011110000100001)
   9: 1.00000008E8    (binary +|10011001|01111101011110000100001)
  10: 1.00000008E8    (binary +|10011001|01111101011110000100001)

Sie können also sehen, dass 1.0e8f y 1.0e8f + 4 und einige andere Zahlen haben die gleiche Darstellung. Da Sie die Details der IEEE 754-1985 Fließkommaformate bereits kennen, wissen Sie auch, dass die verbleibenden Ziffern abgerundet sein müssen.

Answer 3

Was ist das Ergebnis von n - 1 wenn n - 1 y n aufgrund des approximativen Charakters von Gleitkommazahlen beide eine identische Darstellung haben?

Answer 4

Bezüglich des "Erreichens" eines Wertes, der nicht dargestellt werden kann, denke ich, dass Herb die Möglichkeit von ziemlich esoterischen Fließkommadarstellungen einschloss.

Bei jeder gewöhnlichen Fließkommadarstellung beginnt man entweder mit einem solchen Wert (d. h. man bleibt beim ersten Wert hängen), oder man befindet sich irgendwo im zusammenhängenden Bereich von Ganzzahlen, die um Null herum zentriert sind und genau dargestellt werden können, so dass der Countdown erfolgreich ist.

Für IEEE 754 ist die 32-Bit-Darstellung, typischerweise float in C++ hat eine Mantisse von 23 Bits, während die 64-Bit-Darstellung, typischerweise double in C++, hat eine Mantisse von 52 Bit. Das bedeutet, dass mit double können Sie zumindest die ganzen Zahlen im Bereich -(2^52-1) ... 2^52-1 genau darstellen. Ich bin mir nicht ganz sicher, ob der Bereich mit einem weiteren Faktor 2 erweitert werden kann. Mir wird ein bisschen schwindelig, wenn ich daran denke :-)

Prost & hth.,