Was verursacht Gleitkomma-Rundungsfehler?

Dies liegt daran, dass einige Brüche eine sehr große (oder sogar unendliche) Anzahl von Stellen benötigen, um ohne Rundung ausgedrückt zu werden. Dies gilt für die Dezimalschreibweise ebenso wie für die binäre oder eine andere. Wenn Sie die Anzahl der Dezimalstellen für Ihre Berechnungen begrenzen würden (und vermeiden würden, Berechnungen in Bruchnotation durchzuführen), müssten Sie sogar einen einfachen Ausdruck auf 1/3 + 1/3 runden. Anstatt 2/3 zu schreiben, müssten Sie daher 0,33333 + 0,33333 = 0,66666 schreiben, was nicht mit 2/3 identisch ist.

Bei einem Computer ist die Anzahl der Ziffern durch die technische Natur begrenzt seiner Speicher- und CPU-Register. Die intern verwendete binäre Notation führt zu weiteren Schwierigkeiten. Computer können normalerweise keine Zahlen in Bruchschreibweise ausdrücken, obwohl einige Programmiersprachen diese Fähigkeit hinzufügen, wodurch diese Probleme bis zu einem gewissen Grad vermieden werden können.

Was jeder Informatiker über Gleitkomma-Arithmetik wissen sollte

Kommentare

• Genau richtig. Aber ich würde auch beachten, dass einige Zahlen das In Dezimalzahl beenden ‚ Nicht in Binärform beenden. Insbesondere ist 0.1 eine wiederkehrende Zahl in Binärform, sodass keine Gleitkomma-Binärzahl genau 0,1 darstellen kann.
• Floating Punkte sind ‚ nicht nur für viele Dezimalstellen nützlich. 32-Bit-Ganzzahlen können nur bis zu 4 Milliarden zählen, aber ein 32-Bit-Float kann fast unendlich groß sein.
• Insbesondere sind die Brüche, die wir als endliche Dezimalstellen ausdrücken können, diejenigen, deren Nenner ‚ Primfaktorisierung nur 2 und 5 enthält (z. B. können wir 3/10 und 7/25 ausdrücken , aber nicht 11/18). Wenn wir zur Binärdatei übergehen, verlieren wir den Faktor 5, so dass nur die dyadischen Rationalitäten (z. B. 1/4, 3/128) genau ausgedrückt werden können.

Rundungsfehler entstehen hauptsächlich durch die Tatsache, dass die Unendlichkeit aller reellen Zahlen kann unmöglich durch den endlichen Speicher eines Computers dargestellt werden, geschweige denn durch einen winzigen Speicherabschnitt wie eine einzelne Gleitkommavariable , so dass viele gespeicherte Zahlen gerecht sind Annäherungen an die Anzahl, die sie darstellen sollen.

Da es nur eine begrenzte Anzahl von Werten gibt, die nicht eine Annäherung, und jede Operation zwischen einer Annäherung und einer anderen Zahl führt zu einer Annäherung, Rundungsfehler sind fast unvermeidlich .

Das Wichtige Die Sache ist, zu erkennen, wann sie wahrscheinlich ein Problem verursachen, und Maßnahmen zu ergreifen, um die Risiken zu mindern.

Zusätzlich zu David Goldberg ist das wesentliche What Every Computer Scientis t sollte etwas über Gleitkomma-Arithmetik wissen (neu veröffentlicht von Sun / Oracle als Anhang zu ihrer -Numerik Berechnungshandbuch ), das von thorsten , dem ACCU Journal Überladung hat eine ausgezeichnete Artikelserie von Richard Harris über die Gleitkomma-Blues .

Die Serie begann mit

• Sie müssen nachdenken! in Überladung # 99 ( pdf , S. 5-10):

Numerical co mputing hat viele tücken. Richard Harris beginnt nach einer Silberkugel zu suchen.

Der Drache des numerischen Fehlers wird nicht oft aus seinem Schlaf geweckt, aber wenn er sich unachtsam nähert, fügt er den Berechnungen des unachtsamen Programmierers gelegentlich katastrophalen Schaden zu. P. >

So sehr, dass einige Programmierer, die ihn in den Wäldern der Gleitkomma-Arithmetik nach IEEE 754 zufällig getroffen haben, ihren Kollegen davon abraten, in diesem schönen Land zu reisen.

In dieser Artikelserie werden wir uns damit befassen die Welt des numerischen Rechnens, die Gleitkomma-Arithmetik mit einigen der Techniken kontrastiert, die als sicherer Ersatz dafür vorgeschlagen wurden. Wir werden lernen, dass das Territorium des Drachen tatsächlich weitreichend ist und dass wir im Allgemeinen vorsichtig vorgehen müssen, wenn wir seine fürchten verheerende Aufmerksamkeit.

Richard erklärt zunächst die Taxonomie von reellen Zahlen, rational, irrational, algebraisch und transzendent. Anschließend erklärt er die IEEE754-Darstellung, bevor er auf Stornierungsfehler und Ausführungsreihenfolgeprobleme eingeht.

Wenn Sie nicht tiefer lesen, haben Sie eine hervorragende Grundlage für die mit Gleitkommazahlen verbundenen Probleme

Wenn Sie jedoch mehr wissen möchten, fährt er mit

• Warum Fixpunkt Ihren Gleitkomma-Blues nicht heilt in Überladung # 100 ( pdf , p15-22)
• Warum Rationals nicht Heilen Sie Ihren Gleitkomma-Blues in Überladung # 101 ( pdf , p9-13)
• Warum Computeralgebra Ihren Gleitkomma-Blues nicht heilt in Überladung # 102 ( pdf , p9- 14).
• Warum Intervallarithmetik Ihren Gleitkomma-Blues nicht heilt in Überladung 103 ( pdf , p19-24)

Er versucht dann, Ihnen bei der Heilung Ihres Calculus Blues

und zu guter Letzt gibt es

• Warum die automatische Differenzierung Ihren Calculus Blues nicht heilt in Überladung 108 ( pdf , p4-11).

Die gesamte Artikelserie ist Es lohnt sich, einen Blick darauf zu werfen, und mit insgesamt 66 Seiten sind sie immer noch kleiner als die 77 Seiten des Goldberg-Papiers .

Währenddessen Die Serie deckt einen Großteil des gleichen Gebiets ab. Ich fand sie eher zugänglich als Goldbergs -Papier . Ich fand es auch einfacher, die komplexeren Teile des Papiers zu verstehen, nachdem ich die früheren Artikel von Richards gelesen hatte, und nach diesen frühen Artikeln verzweigt sich Richard in viele interessante Bereiche, die vom Goldberg-Papier nicht berührt werden.

Als sprach ak in den Kommentaren erwähnt:

Als Autor von Diese Artikel möchte ich erwähnen, dass ich interaktive Versionen davon in meinem Blog www.thusspakeak.com erstellt habe, beginnend mit thusspakeak.com/ak/2013/06 .

Kommentare

• Als Autor dieser Artikel möchte ich ‚ erwähnen, dass ich interaktive Versionen davon in meinem Blog www.thusspakeak.com erstellt habe, beginnend mit thusspakeak.com/ak/2013/06 .
• Danke @ thusspakea.k. Ich ‚ habe eine Notiz hinzugefügt auf meine Antwort und tho Diese interaktiven Elemente funktionieren sehr gut.

Nun, thorsten hat den endgültigen -Link . Ich würde hinzufügen:

Jede Form der Darstellung weist für eine bestimmte Zahl einen Rundungsfehler auf. Versuchen Sie, 1/3 im IEEE-Gleitkomma oder in Dezimalzahl auszudrücken. Keiner kann es genau machen. Dies geht über die Beantwortung Ihrer Frage hinaus, aber ich habe diese Faustregel erfolgreich angewendet:

• Speichern Sie vom Benutzer eingegebene Werte in Dezimalzahlen (da sie mit ziemlicher Sicherheit in einer Dezimaldarstellung eingegeben wurden – sehr wenige Benutzer wird binär oder hex) verwenden. Auf diese Weise haben Sie immer die genaue vom Benutzer eingegebene Darstellung.
• Wenn Sie vom Benutzer eingegebene Brüche speichern müssen, speichern Sie den Zähler und den Nenner (auch in Dezimalzahl).
• Wenn Sie eine haben System mit mehreren Maßeinheiten für dieselbe Menge (wie Celsius / Fahrenheit), und der Benutzer kann beide eingeben, den eingegebenen Wert und die eingegebenen Einheiten speichern. Versuchen Sie nicht, als einzelne Darstellung zu konvertieren und zu speichern. Es sei denn, Sie können dies ohne Verlust an Präzision / Genauigkeit tun. Verwenden Sie die gespeicherten Werte und in allen Berechnungen.
• Speichern Sie maschinengenerierte Werte im IEEE-Gleitkomma (dies können generierte Zahlen sein durch ein elektronisches Messgerät, wie einen analogen Sensor mit einem A / D-Wandler oder das ungerundete Ergebnis einer Berechnung). Beachten Sie, dass dies nicht gilt, wenn Sie einen Sensor über eine serielle Verbindung lesen und es bereits gibt Sie geben den Wert in einem Dezimalformat (z. B. 18,2 ° C) an.
• Speichern Sie vom Benutzer sichtbare Summen usw. in Dezimalzahlen (wie bei einem Bankkonto) Balance). Runden Sie entsprechend, aber verwenden Sie diesen Wert als endgültigen Wert für alle zukünftigen Berechnungen.

Kommentare

• Ich würde hinzufügen: Erwägen Sie die Verwendung eines Mathematikpaket mit beliebiger Genauigkeit wie ARPREC oder decNumber.
• I ‚ t Dezimal (im Gegensatz zu binär) hat große Vorteile für ganzzahlige Werte wie den Zähler und Nenner eines Bruchs. Beide können exakte Ganzzahlwerte speichern, und Binär ist effizienter. ‚ verursacht einige Kosten beim Hin- und Herkonvertieren für Eingabe und Ausgabe, aber ‚ wird wahrscheinlich durch die physischen Kosten überschwemmt Durchführen der E / A.

Was bisher anscheinend nicht erwähnt wurde, sind die Konzepte eines instabilen Algorithmus und ein schlecht konditioniertes Problem . Ich werde zuerst auf Ersteres eingehen, da dies für Anfänger eine häufigere Gefahr zu sein scheint.

Betrachten Sie die Berechnung der Potenzen des (reziproken) Goldenen Schnitts φ=0.61803…; Eine Möglichkeit besteht darin, die Rekursionsformel φ^n=φ^(n-2)-φ^(n-1) zu verwenden, beginnend mit φ^0=1 und φ^1=φ. Wenn Sie diese Rekursion in Ihrer bevorzugten Computerumgebung ausführen und die Ergebnisse mit genau ausgewerteten Leistungen vergleichen, werden Sie eine langsame Erosion signifikanter Zahlen feststellen. Folgendes passiert beispielsweise in Mathematica :

ph = N[1/GoldenRatio]; Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51] {0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, -2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, -5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, -9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, -1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, -2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, -5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, -9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, -1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 7.136559332847351*^-7, -1.1547195563277288*^-6} 

Das angebliche Ergebnis für φ^41 hat das falsche Vorzeichen, und noch früher haben die berechneten und tatsächlichen Werte für φ^39 keine gemeinsamen Ziffern (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Der Algorithmus ist daher instabil, und man sollte diese Rekursionsformel nicht in ungenauer Arithmetik verwenden Die inhärente Natur der Rekursionsformel: Es gibt eine „zerfallende“ und „wachsende“ Lösung für diese Rekursion, und der Versuch, die „zerfallende“ Lösung durch Vorwärtslösung zu berechnen, wenn es eine alternative „wachsende“ Lösung gibt, bittet um numerischen Kummer. Man sollte daher sicherstellen, dass seine numerischen Algorithmen stabil sind.

Nun zum Konzept eines schlecht konditionierten Problems: Auch wenn es einen stabilen Weg gibt Etwas numerisch kann es sehr gut sein, dass das Problem Sie ha ve kann einfach nicht von Ihrem Algorithmus gelöst werden. Dies ist die Schuld des Problems selbst und nicht der Lösungsmethode. Das kanonische Beispiel in der Numerik ist die Lösung linearer Gleichungen mit der sogenannten „Hilbert-Matrix“:

Die Matrix ist das kanonische Beispiel einer schlecht konditionierten Matrix: Der Versuch, ein System mit einer großen Hilbert-Matrix zu lösen, kann zu einer ungenauen Lösung führen.

Hier „sa Mathematica Demonstration: Vergleichen Sie die Ergebnisse der exakten Arithmetik

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}] {{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}} 

und der ungenauen Arithmetik

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}] {{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 1.00342}} 

(Wenn Sie es in Mathematica ausprobiert haben, werden Sie einige Fehlermeldungen bemerken, die vor dem Auftreten einer schlechten Konditionierung warnen.)

In beiden Fällen erhöhen Sie einfach die Präzision ist keine Heilung; Dies wird nur die unvermeidliche Erosion von Zahlen verzögern.

Dies ist, was Sie möglicherweise konfrontiert werden. Die Lösungen könnten schwierig sein: Zum einen gehen Sie entweder zum Zeichenbrett zurück oder stöbern in Zeitschriften / Büchern / was auch immer, um herauszufinden, ob jemand anderes eine bessere Lösung gefunden hat als Sie; Zum zweiten geben Sie entweder auf oder formulieren Ihr Problem in etwas Besseres um.

Ich werde Ihnen ein Zitat von Dianne O „Leary hinterlassen:

Das Leben kann uns einige schlecht konditionierte Probleme bereiten, aber es gibt keinen guten Grund, sich mit einem instabilen Algorithmus zufrieden zu geben.

, da Dezimalzahlen der Basis 10 nicht in Basis 2

oder mit anderen Worten 1/10 nicht ausgedrückt werden können transformiert in einen Bruch mit einer Potenz von 2 im Nenner (was im Wesentlichen Gleitkommazahlen sind)

Kommentare

• Nicht genau wahr: 0,5 und 0,25 können in Basis 2 ausgedrückt werden. Ich denke, Sie meinen “ nicht alle Dezimalzahlen der Basis 10 „.
• Genauer. Nicht alle Bruchzahlen können mit einer Gleitkommanotation exakt dargestellt werden (dh mit der. Sowohl Basis 2 als auch Basis 10 haben genau dieses Problem). Versuchen Sie, 9*3.3333333 dezimal auszuführen, und vergleichen Sie es mit 9*3 1/3
• Dies ist die häufigste Gleitkommaquelle Verwechslung. .1 + .1 != .2, da Gleitkomma-Binärcodierung verwendet wird, nicht dezimal.
• @SeanMcMillan: Und 1.0/3.0*3.0 != 1.0, weil Gleitkomma -punkt-Binärcodierung wird verwendet, nicht trinär.

In der Mathematik gibt es unendlich viele rationale Zahlen . Eine 32-Bit-Variable kann nur 2 32 unterschiedliche Werte haben, und eine 64-Bit-Variable kann nur 2 ⁶⁴ -Werte haben. Daher gibt es unendlich viele rationale Zahlen, die keine genaue Darstellung haben.

Wir könnten Schemata entwickeln, mit denen wir 1/3 oder 1/100 perfekt darstellen können. Es stellt sich heraus, dass dies für viele praktische Zwecke nicht sehr nützlich ist. Es gibt eine große Ausnahme: Im Finanzbereich tauchen häufig Dezimalbrüche auf. Das liegt hauptsächlich daran, dass Finanzen im Wesentlichen eine menschliche Aktivität sind, keine physische.

Daher verwenden wir normalerweise binäre Gleitkommazahlen und runden jeden Wert, der nicht binär dargestellt werden kann. Im Finanzbereich wählen wir jedoch manchmal dezimale Gleitkommazahlen und runden Werte auf den nächsten Dezimalwert .

Kommentare

• Schlimmer noch, während eine unendliche (zählbar unendliche) Speichermenge es einem ermöglichen würde, alle Rationalitäten darzustellen, würde dies nicht der Fall sein Ausreichend für die Darstellung der Realzahlen. Noch schlimmer ist, dass fast alle reellen Zahlen keine berechenbaren Zahlen sind. Das Beste, was wir mit einer endlichen Speichermenge tun können, ist, eine Teilmenge der Realzahlen mit endlichem Bereich zu approximieren.
• @ Kevin: Sie ‚ sprechen über die berechenbaren Zahlen, bei denen es sich um eine winzige Teilmenge (eine Teilmenge mit Maß Null) der Realwerte handelt.
• +1 für die grundlegendste Erklärung: Sie ‚ versuchen, eine unendliche Anzahl von Zahlen mit einer endlichen Anzahl von Bits darzustellen.
• @DavidHammen: Berechenbare Zahlen sind eine winzige Teilmenge ( von Maß Null) der Reals – aber jede Zahl, mit der Sie ‚ jemals in einem Programm arbeiten werden, ist per Definition berechenbar.
• @Giorgio: If Wenn Sie die richtige Darstellung auswählen, kann die Quadratwurzel von 2 dargestellt werden, z. B. als Zeichenfolge "√2". (Mein alter HP-48-Rechner konnte genau das, und das Quadrieren dieses Werts führte zu genau 2.0.) Es gibt nur eine zählbare Unendlichkeit darstellbarer reeller Zahlen für any endliche Darstellung – aber keine Berechnung kann eine Zahl ergeben, die im Prinzip nicht darstellbar ist. In der Praxis begrenzt der binäre Gleitkommawert die Menge der darstellbaren Zahlen drastisch, mit dem Vorteil einer rasanten Geschwindigkeit und einer winzigen Speicherung im Vergleich zu symbolischen Darstellungen.

Das einzige wirklich offensichtliche „Rundungsproblem“ bei Gleitkommazahlen, an das ich denke, sind Filter mit gleitendem Durchschnitt:

$$ \ begin {align} y [n] & = \ frac {1} {N} \ sum \ limit_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] – x [nN]) \ \ end {align} $$

, damit dies ohne funktioniert Wenn Sie Rauschen aufbauen, möchten Sie sicherstellen, dass das $ x [n] $, das Sie in den aktuellen Samples hinzufügen, genau dem $ x [nN] $ entspricht, das Sie in Zukunft $ N $ Samples subtrahieren werden. Wenn dies nicht der Fall ist, ist ein kleiner Trottel, der in Ihrer Verzögerungsleitung stecken bleibt und niemals herauskommt, anders. Dies liegt daran, dass dieser Filter für den gleitenden Durchschnitt tatsächlich mit einem IIR aufgebaut ist, der einen geringfügig stabilen Pol bei $ z = 1 $ und eine Null hat, die ihn im Inneren aufhebt. Aber es ist ein Integrator, und jeder Mist, der integriert und nicht vollständig entfernt wird, wird für immer in der Integratorsumme vorhanden sein. Hier hat der Festkomma nicht das gleiche Problem wie Gleitkommazahlen.

Kommentare

• Hey, funktioniert ‚ nicht? $ LaTeX $ math markup funktioniert im prog.SE Forum ??? that ‚ ist wirklich lahm, wenn es nicht ‚ t ist.
• Siehe dies auf meta.SO und verknüpften Fragen