Laden...

Gleichheit von Gleitkommazahlen (inkl. etwas Theorie)

Erstellt von gfoidl vor 12 Jahren Letzter Beitrag vor 12 Jahren 11.159 Views
Information von gfoidl vor 12 Jahren

Dies ist ein Thread, auf den aus der FAQ verwiesen wird. Bitte keine weitere Diskussion, sondern nur wichtige Ergänzungen und diese bitte knapp und präzise. Vielen Dank!

gfoidl Themenstarter:in
6.911 Beiträge seit 2009
vor 12 Jahren
Gleichheit von Gleitkommazahlen (inkl. etwas Theorie)

Hallo zusammen,

ergänzend zu [FAQ] Double und Float: Fehler beim Vergleich und Rundungsfehler schreibe ich mal etwas aus der Praxis mit dem Umgang von Vergleichen mit Gleitkommazahlen und stelle dabei eine Hilfs-Klasse zur Verfügung.

Definition der Maschinengenauigkeit:
epsilon ist die kleinste positive Gleitkommazahl, die zur Gleitkommazahl 1.0 addiert eine von 1.0 verschiedene Summe ergibt, also die Ungleichung 1 + epsilon > 1 erfüllt.

Für einen imaginären Supercomputer, der reelle Arithmetik exakt berechnen kann, gibt es keine Zahl, die diese Definition erfüllt. Wohl aber auf einen realen Computer mit endlicher Genauigkeit und für diesen kann der Zahlenwert näherungsweise per binärer Suche wie folgt ermittelt werden.


double tau     = 1.0;
double epsilon = 1.0;
double test    = 0.0;

while (1.0 != test )
{
    epsilon = tau;
    tau    *= 0.5;
    test    = 1.0 + tau;
}

Debug.Assert(1.0 < 1.0 + epsilon);

In Worten: Ein angenommenes epsilon wird solange halbiert (binäre Suche), bis die Summe aus der Addition mit 1.0 sich nicht mehr von 1.0 unterscheidet. Das Resultat, also die Näherung der Maschinengenauigkeit, ist somit der Wert von epsilon vor dem letzten Halbieren.

Diese Berechnung ist wie erwähnt nur eine Näherung. Die direkte Berechnung von epsilon nach IEEE 754 ist:


epsilon = b[sup]-p[/sup]

wobei b die Basis und p die Mantissenlänge (p für Precision) der Gleitkommadarstellung ist. Für double ergibt sich somit:


epsilon = 2[sup]-52[/sup] = 2.2204460 * 10[sup]-16[/sup]

Gezeigt wurde die Maschinengenauigkeit an double, für float gehts analog (mit b = 2 und p = 23) und beträgt für float 1.19209 * 10-07.

Fehler:
Ist x der (unbekannte) wahre Wert eines Rechenergebnisses und x' der entsprechende "Näherungswert", so nennt man


eps_a = x - x'

den absoluten Fehler und


eps_r = eps_a / x' = (x - x') / x'

den relativen Fehler. Die Beträge werden hier nicht verwendet, denn die Abweichung (der Fehler) kann positiv od. negativ sein.

Anmerkung: Beim Fehler wird als Bezug das Rechenergebnis verwendet. Es mag auf den ersten Blick einleuchtender sein, wenn eps_a = x' - x gelten würde, sowie es bei Soll-/Istwert-Vergleichen der Fall ist. Der wahre Wert ist aber unbekannt, das Rechenergebnis (der Näherungswert) ist jedoch bekannt und der Fehler kann geschätzt/berechnet werden. Somit kann der wahre Wert als Taylorreihenentwicklung x = x' + eps_a (hier nur das lineare Glied) angeschrieben werden. Spezielle Bedeutung hat dies in der Fehlerfortpflanzungsrechnung. Darum wurde diese Fehlerdefinition mit dem Bezug zum Näherungswert/Rechenergebnis zum üblichen Standard in der Numerik und Messtechnik, da es einfach leichter im Umgang damit wird.

In der numerischen Praxis wird dem relativen Fehler der Vorzug gegeben. Folgendes Beispiel zeigt warum:


   x       x'   eps_a   eps_r
   0.1    0.09  0.01    ~0.1
1000.0  999.99  0.01    ~0.00001

Ein kleiner absoluter Fehler fällt bei einem großen Endergebnis weniger ins Gewicht als ein kleiner absoluter Fehler bei einem kleinen Endergebnis. Und genau das kommt im relativen Fehler zum Audruck. Wobei das nur für Enderegebnisse gilt. Bei Zwischenergebnissen kann auch ein kleiner absoluter Fehler bei einer großen Zahl in der weiteren Rechnung sehr stark auswirken, z.B. wenn diese große Zahl von einer fast gleich großen abgezogen wird.

Vergleiche mit dem absoluten Fehler können verwendet werden, wenn der Bereich des erwarteten Ergebnisses bekannt ist. Dann ist der Vergleich mit dem absoluten Fehler einfach und effektiv. Es muss nur sichergestellt sein, dass der (zugelassene) absolute Fehler größer als die minimal darstellbare Differenz des Bereichs ist.

Vergleich mit dem relativen Fehler:
Vorbemerkung: In Anlehnung an die Literatur hab ich bisher x für den wahren Wert und x' für den Näherungswert verwendet. Diese Bezeichner lassen sich in C# jedoch nicht sinnvoll darstellen und deshalb wird ab jetzt a und b stattdessen verwendet.

Laut obiger Definition des relativen Fehlers muss der erwartete exakte Wert vorhanden sein. Dies ist jedoch (sehr) selten der Fall. Für den Vergleich könnte folgende Methode verwendet werden:


static bool IsEqual(double a, double b)
{
    if (a == b) return true;

    double relativeError = (a - b) / b;

    return Math.Abs(relativeError) < _epsilon;
}

Es wurde erwähnt, dass Gleitkommazahlen nicht mit == verglichen werden sollen. Warum also gleich zu Beginn der Methode dieser Vergleich?
Wenn a = b dann ist der relative Fehler 0 und die Bedingung erfüllt - das Ergebnis entspricht dem erwarteten Verhalten. Falls a = b = 0 gilt, wäre dies die undefinierte Division 0 / 0 welche als Ergebnis double.NaN liefert. NaN (not a number) würde immer zu false führen.

Das Problem obiger Methode - und auch der Grund warum sie nicht verwendet werden sollte - ist, dass IsEqual(a, b) != IsEqual(b, a) ist, weil immer durch das zweite Argument dividiert wird. Der Vergleich bzw. die Methode, welche den Vergleich durchführt, sollte und muss transitiv sein. D.h. a == b muss b == a entsprechen bzw. für die Methode muss die Reihenfolge der Argumente vertauschbar sein. Daher wird obiger Ansatz verbessert, indem immer durch das größere Argument dividiert wird:


static bool IsEqual(double a, double b)
{
    if (a == b) return true;

    if (Math.Abs(b) > Math.Abs(a))
        return Math.Abs((a - b) / b) < _epsilon;

    return Math.Abs((a - b) / a) < _epsilon;
}

Diese Methode hat noch ihre Eigenheiten, wenn Zahlen im Bereich um 0 verglichen werden sollen. Beispielsweise eine nur leicht von 0 verschiedene positive Zahl und eine nur leicht von 0 verschiedene negative Zahl würde einen relativen Fehler von ~2.0 ergeben. Um diese Zahlen vergleichen zu können, muss ein Prüfung des absoluten Fehlers zusätzlich angewandt werden. Die Methode muss true zurückgegeben, wenn entweder der absolute Fehler oder der relative Fehler kleiner als der erlaubte Fehler sind. Hier muss der erlaubte Fehler eine sehr kleine Zahl sein. Die Methode ändert sich somit zu:


static bool IsEqual(double a, double b, double eps_a)
{
    if (a == b) return true;
    if (Math.Abs(a - b) < eps_a) return true;

    if (Math.Abs(b) > Math.Abs(a))
        return Math.Abs((a - b) / b) < _epsilon;

    return Math.Abs((a - b) / a) < _epsilon;
}

Es gibt noch weitere Möglichkeiten die Gleitkommazahlen zu vergleichen. Eine ist durch den Vergleich von signifikanten Stellen, d.h. die Gleitkommazahlen werden in eine Ganzzahl übergeführt, wobei die signifikanten Stellen erhalten bleiben, und dann die Ganzzahlen (exakt) verglichen. Dazu wird die Gleitkommazahl mit 10signifikante Stellen (10 hoch Anzahl signifikanter Stellen) multipliziert.


static bool IsEqual(double a, double b, long precision)
{
    if (a == b) return true;

    if (precision < 0)
        throw new ArgumentOutOfRangeException("precision");

    double test = Math.Pow(10d, precision);
    if (double.IsInfinity(test) || test > long.MaxValue)
        throw new ArgumentOutOfRangeException("precision");

    precision = (long)test;
    return (long)(a * precision) == (long)(b * precision);
}

Mit diesem Wissen kann eine Hilfsklasse zum Vergleichen erstellt werden. Etwa so:


using System;

namespace gfoidl.Numerics
{
    public static class Comparison
    {
        private static readonly double _epsilon = Math.Pow(2, -52);
        public static double Epsilon
        {
            get { return _epsilon; }
        }
        //---------------------------------------------------------------------
        public static bool IsEqualTo(this double a, double b)
        {
            return IsEqualTo(a, b, _epsilon);
        }
        //---------------------------------------------------------------------
        public static bool IsEqualTo(this double a, double b, double eps_a)
        {
            if (CheckSpecialCases(a, b)) return true;
            if (Math.Abs(a - b) < eps_a) return true;

            if (Math.Abs(b) > Math.Abs(a))
                return Math.Abs((a - b) / b) < _epsilon;

            return Math.Abs((a - b) / a) < _epsilon;
        }
        //---------------------------------------------------------------------
        public static bool IsEqualTo(this double a, double b, long precision)
        {
            if (CheckSpecialCases(a, b)) return true;

            if (precision < 0)
                throw new ArgumentOutOfRangeException("precision");

            double test = Math.Pow(10d, precision);
            if (double.IsInfinity(test) || test > long.MaxValue)
                throw new ArgumentOutOfRangeException("precision");

            precision = (long)test;
            return (long)(a * precision) == (long)(b * precision);
        }
        //---------------------------------------------------------------------
        private static bool CheckSpecialCases(double a, double b)
        {
            if (double.IsPositiveInfinity(a)) return double.IsPositiveInfinity(b);
            if (double.IsNegativeInfinity(a)) return double.IsNegativeInfinity(b);
            if (double.IsNaN(a))              return double.IsNaN(b);
            if (a == b)                       return true;

            return false;
        }
    }
}

Trivial-Beispiel:


double d1 = 3.3;
double d2 = 2.2 + 1.1;

bool naiveAndWrong     = d1 == d2;                  // false
bool equals            = d1.IsEqualTo(d2);          // true
bool equalsByPrecision = d1.IsEqualTo(d2, 10);      // true

Anmerkung:
Die Maschinengenauigkeit gibt nur die Genauigkeit per Definition zurück. Sie ist nicht immer geeignet um einen Vergleich damit durchzuführen. Wie aus obigen Ausführungen ersichtlich, müssen die erlaubten Fehler/Abweichungen individuell gewählt und an das Problem angepasst werden.

Numerik, auch in der einfachsten Form, ist schon recht kompliziert, wenn alles richtig gemacht werden soll. Neben dem Wissen über Numerik gehört auch Fehlerrechnung/-Schätzung dazu.

In .NET gibt es mit double.Epsilon auch ein "epsilon", aber das entspricht nicht der Maschinengenauigkeit. double.Epsilon ist die kleinste darstellbare Zahl die von 0 verschieden ist.
Zum Vergleich:


double.Epsilon     ~ 5e-324
Epsilon für double ~ 2e-16

mfG Gü

Schlagwörter: double, System.Double, Vergleich, Gleichheit, Fehler, Rundungsfehler, Maschinengenauigkeit, Genauigkeit, Numerik, epsilon

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

5.742 Beiträge seit 2007
vor 12 Jahren

Inhaltliche Diskussionen, Fragen und Verbesserungsvorschläge zu dem Snippet bitte in Diskussion zu: Gleichheit von Gleitkommazahlen (inkl. etwas Theorie)