Lösungen für Gleitkomma-Rundungsfehler

18

Beim Erstellen einer Anwendung, die sich mit vielen mathematischen Berechnungen befasst, bin ich auf das Problem gestoßen, dass bestimmte Zahlen Rundungsfehler verursachen.

Ich verstehe zwar, dass Fließkommazahlen nicht exakt sind , aber das Problem besteht darin, wie ich mit exakten Zahlen umgehe, um sicherzustellen, dass beim Ausführen von Berechnungen mit Fließkomma-Rundungen keine Probleme auftreten.

JNL
quelle
2
Gibt es ein bestimmtes Problem, mit dem Sie konfrontiert sind? Es gibt viele Möglichkeiten zum Testen, alles in Ordnung für ein Problem. Fragen, die mehrere Antworten haben können, passen schlecht zum Q & A-Format. Es ist am besten, wenn Sie das Problem so definieren, dass es eine richtige Antwort gibt, anstatt ein Netz für Ideen und Empfehlungen zu bilden.
Ich erstelle eine Softwareanwendung mit vielen mathematischen Berechnungen. Ich verstehe, dass NUNIT- oder JUNIT-Tests gut wären, hätte aber gerne eine Idee, wie man die Probleme mit mathematischen Berechnungen angeht.
JNL
1
Können Sie ein Beispiel für eine Berechnung nennen, die Sie testen würden? Normalerweise wäre es nicht Unit Testing Raw Math (es sei denn, Sie testen Ihre eigenen numerischen Typen), aber das Testen von etwas Ähnlichem distanceTraveled(startVel, duration, acceleration)würde getestet.
Ein Beispiel wird sich mit Dezimalstellen befassen. Nehmen wir zum Beispiel an, wir bauen eine Wand mit speziellen Einstellungen für dist x-0 bis x = 14.589 und dann einige Anordnungen von x = 14.589 bis x = Ende der Wand. Die Distanz .589, wenn sie in binär umgewandelt wird, ist nicht die gleiche .... Besonders wenn wir einige Distanzen hinzufügen ... wie 14.589 + 0.25 wird nicht gleich 14.84 in binär sein .... Ich hoffe, es ist nicht verwirrend?
JNL
1
@MichaelT, vielen Dank, dass Sie die Frage bearbeitet haben. Hat mir sehr geholfen. Da bin ich neu dabei, nicht zu gut, wie man die Fragen einrahmt. :) ... wird aber bald gut.
JNL

Antworten:

22

Es gibt drei grundlegende Ansätze zum Erstellen alternativer numerischer Typen, die frei von Gleitkommarundungen sind. Das gemeinsame Thema bei diesen ist, dass sie stattdessen auf verschiedene Arten Ganzzahl-Mathematik verwenden.

Rationals

Stellen Sie die Zahl als Ganzes und als rationale Zahl mit einem Zähler und einem Nenner dar. Die Nummer 15.589würde dargestellt als w: 15; n: 589; d:1000.

Bei einer w: 0; n: 1; d: 4Addition auf 0,25 (das heißt ) wird der LCM berechnet und anschließend die beiden Zahlen addiert. Dies funktioniert in vielen Situationen gut, kann jedoch zu sehr großen Zahlen führen, wenn Sie mit vielen rationalen Zahlen arbeiten, die relativ zueinander primieren.

Fixpunkt

Sie haben den ganzen Teil und den Dezimalteil. Alle Zahlen sind auf diese Genauigkeit gerundet (es gibt das Wort - aber Sie wissen, wo es ist). Sie könnten zum Beispiel einen festen Punkt mit 3 Dezimalstellen haben. 15.589+ 0.250wird addiert 589 + 250 % 1000für den Dezimalteil (und dann ein beliebiger Übertrag für den gesamten Teil). Dies funktioniert sehr gut mit vorhandenen Datenbanken. Wie bereits erwähnt, gibt es eine Rundung, aber Sie wissen, wo sie sich befindet, und können sie präziser als erforderlich angeben (Sie messen nur mit 3 Dezimalstellen, also korrigieren Sie sie mit 4).

Floating Fixpunkt

Speichern Sie einen Wert und die Genauigkeit. 15.589wird wie 15589für den Wert und 3für die Genauigkeit 0.25gespeichert , während als 25und gespeichert wird 2. Dies kann mit beliebiger Präzision umgehen. Ich glaube, das ist es, was die Interna von Javas BigDecimal verwenden (haben es in letzter Zeit nicht angeschaut). Irgendwann werden Sie es wieder aus diesem Format entfernen und anzeigen wollen - und das kann mit einer Rundung einhergehen (wiederum steuern Sie, wo es sich befindet).


Sobald Sie die Auswahl für die Darstellung festgelegt haben, können Sie entweder vorhandene Bibliotheken von Drittanbietern finden, die diese verwenden, oder Ihre eigenen erstellen. Wenn Sie Ihre eigenen schreiben, stellen Sie sicher, dass Sie die Einheit testen und sicherstellen, dass Sie die Mathematik korrekt ausführen.


quelle
2
Das ist ein guter Anfang, aber natürlich löst es das Rundungsproblem nicht vollständig. Irrationale Zahlen wie π, e und √2 haben keine streng numerische Darstellung. Sie müssen symbolisch dargestellt werden, wenn Sie eine exakte Darstellung wünschen, oder Sie müssen sie so spät wie möglich auswerten, wenn Sie nur den Rundungsfehler minimieren möchten.
Caleb
Bei @Caleb für Irrationalen müsste man sie dahin auswerten, wo eine Rundung Probleme verursachen könnte. Zum Beispiel ist 22/7 auf 0,1% von pi genau, 355/113 ist auf 10 ^ -8 genau. Wenn Sie nur mit Zahlen mit 3 Dezimalstellen arbeiten, sollten mit 3.141592653 Rundungsfehler mit 3 Dezimalstellen vermieden werden.
@MichaelT: Um rationale Zahlen hinzuzufügen, müssen Sie das LCM nicht finden, und es geht schneller (und schneller, wenn Sie danach "LSB-Nullen" löschen und nur dann vollständig vereinfachen, wenn dies unbedingt erforderlich ist). Für rationale Zahlen ist es im Allgemeinen nur "Zähler / Nenner" oder "Zähler / Nenner << Exponent" (und nicht "ganzer Teil + Zähler / Nenner"). Auch Ihr "Gleitkomma" ist eine Gleitkommadarstellung und würde besser als "Gleitkomma beliebiger Größe" beschrieben (um es von "Gleitkomma fester Größe" zu unterscheiden).
Brendan
Ein Teil Ihrer Terminologie ist etwas fragwürdig - Floating Fixed Point macht keinen Sinn - ich denke, Sie versuchen, Floating Decimal zu sagen.
jk.
10

Wenn Gleitkommawerte Rundungsprobleme haben und Sie nicht auf Rundungsprobleme stoßen möchten, folgt logischerweise, dass die einzige Vorgehensweise darin besteht, keine Gleitkommawerte zu verwenden.

Nun stellt sich die Frage: "Wie kann ich mit nicht ganzzahligen Werten ohne Gleitkommavariablen rechnen?" Die Antwort liegt bei Datentypen mit willkürlicher Genauigkeit . Berechnungen sind langsamer, weil sie in Software anstatt in Hardware implementiert werden müssen, aber sie sind genau. Sie haben nicht angegeben, welche Sprache Sie verwenden, daher kann ich kein Paket empfehlen, aber für die meisten gängigen Programmiersprachen sind beliebige Präzisionsbibliotheken verfügbar.

Mason Wheeler
quelle
Ich benutze gerade VC ++ ... Ich würde mich aber über weitere Informationen bezüglich anderer Programmiersprachen freuen.
JNL
Auch ohne Gleitkommawerte gibt es immer noch runde Probleme.
Tschad
2
@Chad Stimmt, aber das Ziel ist nicht, Rundungsprobleme zu beseitigen (die immer auftreten werden, da es in jeder von Ihnen verwendeten Basis Zahlen gibt, die nicht genau dargestellt sind und Sie nicht über unendlich viel Speicher und Rechenleistung verfügen) Reduzieren Sie es auf den Punkt, an dem es keine Auswirkung auf die Berechnung hat, die Sie ausführen möchten.
Iker
@Iker Du hast recht. Sie oder die Person, die die Frage gestellt hat, haben jedoch genau angegeben, welche Berechnungen sie ausführen möchten und welche Genauigkeit sie wünschen. Er muss diese Frage zuerst beantworten, bevor er die Waffe in die Zahlentheorie springt. Nur zu sagen lot of mathematical calculationsist weder hilfreich noch die gegebenen Antworten. In den allermeisten Fällen (wenn Sie nicht mit Währungen zu tun haben) sollte Float wirklich ausreichen.
Tschad
@Chad das ist ein fairer Punkt, es gibt sicherlich nicht genug Daten aus dem OP, um zu sagen, was genau das Präzisionsniveau ist, das sie benötigen.
Iker
7

Fließkomma-Arithmetik ist normalerweise ziemlich genau (15 Dezimalstellen für a double) und ziemlich flexibel. Die Probleme treten auf, wenn Sie mathematische Aufgaben ausführen, bei denen die Anzahl der Stellen für die Genauigkeit erheblich verringert wird. Hier sind einige Beispiele:

  • Abbruch bei Subtraktion: 1234567890.12345 - 1234567890.12300Das Ergebnis 0.0045hat nur zwei Dezimalstellen Genauigkeit. Dies trifft immer dann zu, wenn Sie zwei Zahlen gleicher Größe abziehen.

  • Verschlucken von Präzision: 1234567890.12345 + 0.123456789012345Wertet bis aus 1234567890.24691, die letzten zehn Stellen des zweiten Operanden gehen verloren.

  • Multiplikationen: Wenn Sie zwei 15-stellige Zahlen multiplizieren, müssen 30 Stellen gespeichert werden. Sie können sie jedoch nicht speichern, sodass die letzten 15 Bits verloren gehen. Dies ist besonders lästig in Kombination mit sqrt()(wie in sqrt(x*x + y*y): Das Ergebnis hat nur eine Genauigkeit von 7,5 Stellen.

Dies sind die wichtigsten Fallstricke, die Sie beachten müssen. Und sobald Sie sich ihrer bewusst sind, können Sie versuchen, Ihre Mathematik so zu formulieren, dass sie sie vermeidet. Wenn Sie beispielsweise einen Wert in einer Schleife immer wieder inkrementieren müssen, vermeiden Sie Folgendes:

for(double f = f0; f < f1; f += df) {

Nach ein paar Iterationen wird der größere fTeil der Präzision von verschluckt df. Schlimmer noch, die Fehler summieren sich und führen zu der kontraintuitiven Situation, dass ein kleinerer Fehler dfzu schlechteren Gesamtergebnissen führen kann. Schreiben Sie besser folgendes:

for(int i = 0; i < (f1 - f0)/df; i++) {
    double f = f0 + i*df;

Da Sie die Inkremente in einer einzigen Multiplikation kombinieren, ist das Ergebnis fauf 15 Dezimalstellen genau.

Dies ist nur ein Beispiel. Es gibt andere Möglichkeiten, um Genauigkeitsverluste aus anderen Gründen zu vermeiden. Aber es hilft schon viel, über die Größe der beteiligten Werte nachzudenken und sich vorzustellen, was passieren würde, wenn Sie mit Stift und Papier rechnen und nach jedem Schritt auf eine feste Anzahl von Ziffern runden würden.

In cmaster stellst du Monica wieder her
quelle
2

So stellen Sie sicher, dass Sie keine Probleme haben: Informieren Sie sich über Gleitkomma-Rechenprobleme, stellen Sie jemanden ein, der dies tut, oder verwenden Sie einen gesunden Menschenverstand.

Das erste Problem ist die Präzision. In vielen Sprachen haben Sie "float" und "double" (double steht für "double precision"), und in vielen Fällen haben Sie mit "float" eine Genauigkeit von etwa 7 Stellen, während Sie mit double eine Genauigkeit von 15 haben In Situationen, in denen Präzision ein Problem sein könnte, sind 15 Stellen viel besser als 7 Stellen. In vielen leicht problematischen Situationen bedeutet die Verwendung von "double", dass Sie damit durchkommen, und "float", dass Sie dies nicht tun. Nehmen wir an, die Marktkapitalisierung eines Unternehmens beträgt 700 Milliarden Dollar. Stellen Sie dies in float dar und das niedrigste Bit ist $ 65536. Stellen Sie es mit double dar, und das niedrigste Bit beträgt ungefähr 0,012 Cent. Wenn Sie also nicht wirklich genau wissen, was Sie tun, verwenden Sie double und nicht float.

Das zweite Problem ist eher eine Grundsatzfrage. Wenn Sie zwei verschiedene Berechnungen durchführen, die zum gleichen Ergebnis führen sollen, ist dies häufig nicht der Fall, da Rundungsfehler vorliegen. Zwei Ergebnisse, die gleich sein sollten, sind "fast gleich". Wenn zwei Ergebnisse nahe beieinander liegen, sind die tatsächlichen Werte möglicherweise gleich. Oder vielleicht auch nicht. Sie müssen dies berücksichtigen und Funktionen schreiben und verwenden, die besagen, dass "x definitiv größer als y ist" oder "x definitiv kleiner als y ist" oder "x und y könnten gleich sein".

Dieses Problem wird noch schlimmer, wenn Sie die Rundung verwenden, zum Beispiel "x auf die nächste ganze Zahl abrunden". Wenn Sie 120 * 0,05 multiplizieren, sollte das Ergebnis 6 sein, aber Sie erhalten "eine Zahl, die sehr nahe an 6 liegt". Wenn Sie dann "auf die nächste ganze Zahl abrunden", ist diese "Zahl sehr nahe an 6" möglicherweise "etwas kleiner als 6" und wird auf 5 gerundet. Es spielt keine Rolle, wie nahe Ihr Ergebnis bei 6 liegt, solange es weniger als 6 beträgt.

Und drittens sind einige Probleme schwierig . Das heißt, es gibt keine einfache und schnelle Regel. Wenn Ihr Compiler "long double" genauer unterstützt, können Sie "long double" verwenden und prüfen, ob dies einen Unterschied macht. Wenn es keinen Unterschied macht, sind Sie entweder in Ordnung oder Sie haben ein echtes kniffliges Problem. Wenn es die Art von Unterschied macht, die Sie erwarten würden (wie eine Änderung bei der 12. Dezimalstelle), dann sind Sie wahrscheinlich in Ordnung. Wenn es Ihre Ergebnisse wirklich ändert, haben Sie ein Problem. Bitte um Hilfe.

gnasher729
quelle
1
Es gibt keinen "gesunden Menschenverstand" über Gleitkomma-Mathematik.
Whatsisname
Erfahren Sie mehr darüber.
gnasher729
0

Die meisten Leute machen den Fehler, wenn sie doppelt sehen, dass sie BigDecimal schreien, obwohl sie das Problem gerade woanders hingestellt haben. Double gibt Vorzeichenbit: 1 Bit, Exponentenbreite: 11 Bit. Signifikante und Präzision: 53 Bits (52 explizit gespeichert). Aufgrund der Art des Double verlieren Sie mit zunehmender Größe des gesamten Intergers an relativer Genauigkeit. Zur Berechnung der relativen Genauigkeit, die wir hier verwenden, wird Folgendes angezeigt.

Relative Genauigkeit von double in der Berechnung verwenden wir das folgende Foluma 2 ^ E <= abs (X) <2 ^ (E + 1)

epsilon = 2 ^ (E-10)% Für einen 16-Bit-Float (halbe Genauigkeit)

 Accuracy Power | Accuracy -/+| Maximum Power | Max Interger Value
 2^-1           | 0.5         | 2^51          | 2.2518E+15
 2^-5           | 0.03125     | 2^47          | 1.40737E+14
 2^-10          | 0.000976563 | 2^42          | 4.39805E+12
 2^-15          | 3.05176E-05 | 2^37          | 1.37439E+11
 2^-20          | 9.53674E-07 | 2^32          | 4294967296
 2^-25          | 2.98023E-08 | 2^27          | 134217728
 2^-30          | 9.31323E-10 | 2^22          | 4194304
 2^-35          | 2.91038E-11 | 2^17          | 131072
 2^-40          | 9.09495E-13 | 2^12          | 4096
 2^-45          | 2.84217E-14 | 2^7           | 128
 2^-50          | 8.88178E-16 | 2^2           | 4

Mit anderen Worten: Wenn Sie eine Genauigkeit von +/- 0,5 (oder 2 ^ -1) wünschen, kann die maximale Größe der Zahl 2 ^ 52 sein. Jeder größere Wert und der Abstand zwischen Gleitkommazahlen ist größer als 0,5.

Wenn Sie eine Genauigkeit von +/- 0,0005 (ungefähr 2 ^ -11) wünschen, ist die maximale Größe, die die Zahl sein kann, 2 ^ 42. Jeder größere Wert und der Abstand zwischen Gleitkommazahlen ist größer als 0,0005.

Eine bessere Antwort kann ich nicht geben. Der Benutzer muss herausfinden, welche Genauigkeit er bei der Durchführung der erforderlichen Berechnung und deren Einheitswert (Meter, Füße, Zoll, mm, cm) haben möchte. In den allermeisten Fällen reicht float für einfache Simulationen aus, abhängig von der Größe der Welt, die Sie simulieren möchten.

Obwohl es etwas zu sagen ist, wenn Sie nur eine Welt von 100 mal 100 Metern simulieren wollen, werden Sie eine Genauigkeit in der Größenordnung von 2 ^ -45 haben. Dies geht nicht einmal darauf ein, wie moderne FPUs innerhalb der CPU Berechnungen außerhalb der nativen Schriftgröße ausführen. Erst wenn die Berechnung abgeschlossen ist, werden sie (abhängig vom FPU-Rundungsmodus) auf die native Schriftgröße gerundet.

Tschad
quelle