Welches ist die effektivste Methode für einen Float- und Double-Vergleich?

Question

Was wäre der effizienteste Weg, um zwei double oder zwei float Werte?

Dies einfach zu tun, ist nicht korrekt:

bool CompareDoubles1 (double A, double B)
{
   return A == B;
}

Aber so etwas wie:

bool CompareDoubles2 (double A, double B) 
{
   diff = A - B;
   return (diff < EPSILON) && (-diff < EPSILON);
}

Das scheint eine Verschwendung von Bearbeitungszeit zu sein.

Kennt jemand einen intelligenteren Float-Vergleicher?

Answer 1

Wie bereits erwähnt, ist die Verwendung eines festen Exponenten (z. B. 0,0000001) nutzlos für Werte außerhalb des Epsilon-Wertes. Wenn Ihre beiden Werte zum Beispiel 10000.000977 und 10000 sind, dann gibt es NO 32-Bit-Gleitkommawerte zwischen diesen beiden Zahlen - 10000 und 10000,000977 - sind so nah wie möglich beieinander, ohne Bit für Bit identisch zu sein. Hier ist ein Epsilon von weniger als 0,0009 bedeutungslos; Sie könnten genauso gut den Gleichheitsoperator verwenden.

Wenn sich die beiden Werte der Größe von Epsilon annähern, wächst der relative Fehler auf 100 % an.

Der Versuch, eine Festkommazahl wie 0,00001 mit Fließkommazahlen (bei denen der Exponent beliebig ist) zu mischen, ist daher eine sinnlose Übung. Dies wird nur dann funktionieren, wenn Sie sicher sein können, dass die Operandenwerte innerhalb eines engen Bereichs liegen (d. h. in der Nähe eines bestimmten Exponenten), und wenn Sie einen Epsilonwert für diesen speziellen Test richtig auswählen. Wenn Sie eine Zahl aus dem Hut zaubern ("Hey! 0,00001 ist klein, also muss das gut sein!"), sind Sie zu numerischen Fehlern verdammt. Ich habe viel Zeit damit verbracht, schlechten numerischen Code zu debuggen, bei dem irgendein armer Trottel willkürliche Epsilon-Werte eingegeben hat, damit ein weiterer Testfall funktioniert.

Wenn Sie in irgendeiner Form numerisch programmieren und glauben, dass Sie zu Festkomma-Epsilons greifen müssen, LESEN SIE DEN ARTIKEL VON BRUCE ÜBER DEN VERGLEICH VON GLEITKOMMAZAHLEN .

Vergleich von Fließkommazahlen

Answer 2

Qt implementiert zwei Funktionen, vielleicht können Sie von ihnen lernen:

static inline bool qFuzzyCompare(double p1, double p2)
{
    return (qAbs(p1 - p2) <= 0.000000000001 * qMin(qAbs(p1), qAbs(p2)));
}

static inline bool qFuzzyCompare(float p1, float p2)
{
    return (qAbs(p1 - p2) <= 0.00001f * qMin(qAbs(p1), qAbs(p2)));
}

Und Sie benötigen möglicherweise die folgenden Funktionen, da

Beachten Sie, dass der Vergleich von Werten, bei denen entweder p1 oder p2 gleich 0,0 ist, nicht funktioniert, ebenso wenig wie der Vergleich von Werten, bei denen einer der Werte NaN oder unendlich ist. Wenn einer der Werte immer 0,0 ist, verwenden Sie stattdessen qFuzzyIsNull. Wenn einer der der Werte wahrscheinlich 0,0 ist, besteht eine Lösung darin, zu beiden Werten 1,0 Werten zu addieren.

static inline bool qFuzzyIsNull(double d)
{
    return qAbs(d) <= 0.000000000001;
}

static inline bool qFuzzyIsNull(float f)
{
    return qAbs(f) <= 0.00001f;
}

Answer 3

Sie müssen diese Verarbeitung für Fließkomma-Vergleiche durchführen, da Fließkomma-Typen nicht so perfekt verglichen werden können wie Ganzzahl-Typen. Hier finden Sie Funktionen für die verschiedenen Vergleichsoperatoren.

Fließkomma gleich ( == )

Ich bevorzuge auch die Subtraktionstechnik, anstatt mich auf fabs() o abs() aber ich müsste ein Geschwindigkeitsprofil auf verschiedenen Architekturen erstellen, vom 64-Bit-PC bis zum ATMega328-Mikrocontroller (Arduino), um wirklich zu sehen, ob es einen großen Leistungsunterschied gibt.

Vergessen wir also den ganzen Kram mit den absoluten Werten und machen wir einfach ein paar Subtraktionen und Vergleiche!

Geändert von Das Beispiel von Microsoft hier :

/// @brief      See if two floating point numbers are approximately equal.
/// @param[in]  a        number 1
/// @param[in]  b        number 2
/// @param[in]  epsilon  A small value such that if the difference between the two numbers is
///                      smaller than this they can safely be considered to be equal.
/// @return     true if the two numbers are approximately equal, and false otherwise
bool is_float_eq(float a, float b, float epsilon) {
    return ((a - b) < epsilon) && ((b - a) < epsilon);
}
bool is_double_eq(double a, double b, double epsilon) {
    return ((a - b) < epsilon) && ((b - a) < epsilon);
}

Beispiel für die Verwendung:

constexpr float EPSILON = 0.0001; // 1e-4
is_float_eq(1.0001, 0.99998, EPSILON);

Ich bin mir nicht ganz sicher, aber es scheint mir, dass einige der Kritikpunkte am epsilonbasierten Ansatz, wie sie in den folgenden Kommentaren beschrieben werden diese hoch bewertete Antwort kann durch die Verwendung einer Variablen epsilon gelöst werden, die entsprechend den zu vergleichenden Fließkommazahlen skaliert wird, etwa so:

float a = 1.0001;
float b = 0.99998;
float epsilon = std::max(std::fabs(a), std::fabs(b)) * 1e-4;

is_float_eq(a, b, epsilon);

Auf diese Weise skaliert der Epsilon-Wert mit den Fließkommawerten und ist daher nie so klein, dass er unbedeutend wird.

Der Vollständigkeit halber fügen wir noch den Rest hinzu:

Größer als ( > ), und weniger als ( < ):

/// @brief      See if floating point number `a` is > `b`
/// @param[in]  a        number 1
/// @param[in]  b        number 2
/// @param[in]  epsilon  a small value such that if `a` is > `b` by this amount, `a` is considered
///             to be definitively > `b`
/// @return     true if `a` is definitively > `b`, and false otherwise
bool is_float_gt(float a, float b, float epsilon) {
    return a > b + epsilon;
}
bool is_double_gt(double a, double b, double epsilon) {
    return a > b + epsilon;
}

/// @brief      See if floating point number `a` is < `b`
/// @param[in]  a        number 1
/// @param[in]  b        number 2
/// @param[in]  epsilon  a small value such that if `a` is < `b` by this amount, `a` is considered
///             to be definitively < `b`
/// @return     true if `a` is definitively < `b`, and false otherwise
bool is_float_lt(float a, float b, float epsilon) {
    return a < b - epsilon;
}
bool is_double_lt(double a, double b, double epsilon) {
    return a < b - epsilon;
}

Größer als oder gleich ( >= ), und kleiner oder gleich ( <= )

/// @brief      Returns true if `a` is definitively >= `b`, and false otherwise
bool is_float_ge(float a, float b, float epsilon) {
    return a > b - epsilon;
}
bool is_double_ge(double a, double b, double epsilon) {
    return a > b - epsilon;
}

/// @brief      Returns true if `a` is definitively <= `b`, and false otherwise
bool is_float_le(float a, float b, float epsilon) {
    return a < b + epsilon;
}
bool is_double_le(double a, double b, double epsilon) {
    return a < b + epsilon;
}

Zusätzliche Verbesserungen:

1. Ein guter Standardwert für epsilon in C++ ist std::numeric_limits<T>::epsilon() , die entweder zu 0 o FLT_EPSILON , DBL_EPSILON o LDBL_EPSILON . Siehe hier: https://en.cppreference.com/w/cpp/types/numeric_limits/epsilon . Sie können auch die float.h Kopfzeile für FLT_EPSILON , DBL_EPSILON y LDBL_EPSILON .
   1. Siehe https://en.cppreference.com/w/cpp/header/cfloat und
   2. https://www.cplusplus.com/reference/cfloat/
2. Sie könnten die Funktionen stattdessen als Vorlage verwenden, um alle Fließkommatypen zu behandeln: float , double y long double , mit Typenprüfungen für diese Typen über eine static_assert() innerhalb der Vorlage.
3. Skalierung der epsilon Wert ist eine gute Idee, um sicherzustellen, dass es für wirklich große und wirklich kleine a y b Werte. Dieser Artikel empfiehlt und erklärt sie: http://realtimecollisiondetection.net/blog/?p=89 . Sie sollten also epsilon mit einem Skalierungswert skalieren, der gleich max(1.0, abs(a), abs(b)) wie in diesem Artikel erläutert. Andernfalls, wie a und/oder b zunehmen, würde das Epsilon im Verhältnis zu diesen Werten schließlich so klein werden, dass es im Fließkommafehler untergeht. Daher skalieren wir es so, dass es größer wird, wie die Werte selbst. Die Verwendung von 1.0 als kleinster zulässiger Skalierungsfaktor für epsilon gewährleistet auch, dass für wirklich kleine Größenordnungen a y b Werten wird epsilon selbst nicht so klein skaliert, dass es ebenfalls im Fließkommafehler verloren geht. Daher begrenzen wir den minimalen Skalierungsfaktor auf 1.0 .
4. Wenn Sie die oben genannten Funktionen in einer Klasse "kapseln" wollen, lassen Sie es. Packen Sie sie stattdessen in einen Namespace ein, wenn Sie das möchten, um sie zu benennen. Beispiel: Wenn Sie alle eigenständigen Funktionen in einen Namespace namens float_comparison dann können Sie auf die is_eq() Funktion, zum Beispiel so: float_comparison::is_eq(1.0, 1.5); .
5. Es wäre auch schön, Vergleiche gegen Null hinzuzufügen, nicht nur Vergleiche zwischen zwei Werten.

6. Hier ist also eine bessere Lösung mit den oben genannten Verbesserungen:

   namespace float_comparison {
   
   /// Scale the epsilon value to become large for large-magnitude a or b, 
   /// but no smaller than 1.0, per the explanation above, to ensure that 
   /// epsilon doesn't ever fall out in floating point error as a and/or b
   /// increase in magnitude.
   template<typename T>
   static constexpr T scale_epsilon(T a, T b, T epsilon = 
       std::numeric_limits<T>::epsilon()) noexcept 
   {
       static_assert(std::is_floating_point_v<T>, "Floating point comparisons "
           "require type float, double, or long double.");
       T scaling_factor;
       // Special case for when a or b is infinity
       if (std::isinf(a) || std::isinf(b)) 
       {
           scaling_factor = 0;
       } 
       else 
       {
           scaling_factor = std::max({(T)1.0, std::abs(a), std::abs(b)});
       }
   
       T epsilon_scaled = scaling_factor * std::abs(epsilon);
       return epsilon_scaled;
   }
   
   // Compare two values
   
   /// Equal: returns true if a is approximately == b, and false otherwise
   template<typename T>
   static constexpr bool is_eq(T a, T b, T epsilon = 
       std::numeric_limits<T>::epsilon()) noexcept 
   {
       static_assert(std::is_floating_point_v<T>, "Floating point comparisons "
           "require type float, double, or long double.");
       // test `a == b` first to see if both a and b are either infinity 
       // or -infinity
       return a == b || std::abs(a - b) <= scale_epsilon(a, b, epsilon);
   }
   
   /* 
   etc. etc.:
   is_eq()
   is_ne()
   is_lt()
   is_le()
   is_gt()
   is_ge()
   */
   
   // Compare against zero
   
   /// Equal: returns true if a is approximately == 0, and false otherwise
   template<typename T>
   static constexpr bool is_eq_zero(T a, T epsilon = 
       std::numeric_limits<T>::epsilon()) noexcept 
   {
       static_assert(std::is_floating_point_v<T>, "Floating point comparisons "
           "require type float, double, or long double.");
       return is_eq(a, (T)0.0, epsilon);
   }
   
   /* 
   etc. etc.:
   is_eq_zero()
   is_ne_zero()
   is_lt_zero()
   is_le_zero()
   is_gt_zero()
   is_ge_zero()
   */
   
   } // namespace float_comparison

Siehe auch:

1. Die Makroformen einiger der oben genannten Funktionen in meinem Repo hier: utilities.h .
   1. UPDATE 29 NOV 2020: Es ist ein Work-in-Progress, und ich werde es eine separate Antwort machen, wenn es fertig ist, aber ich habe eine bessere, skalierte Epsilon-Version aller Funktionen in C in dieser Datei hier erstellt: utilities.c . Werfen Sie einen Blick darauf.
2. WEITERE ABLESUNG I zu tun haben jetzt getan haben: Fließkommatoleranzen neu betrachtet, von Christer Ericson . SEHR NÜTZLICHER ARTIKEL! Es spricht über die Skalierung epsilon, um sicherzustellen, dass es nie fällt in Fließkomma-Fehler, auch für wirklich große-Magnitude a und/oder b Werte!

Answer 4

Hier ist der Beweis, dass die Verwendung von std::numeric_limits::epsilon() ist nicht die Antwort - sie schlägt bei Werten größer als eins fehl:

Ein Beweis für meine obige Bemerkung:

#include <stdio.h>
#include <limits>

double ItoD (__int64 x) {
    // Return double from 64-bit hexadecimal representation.
    return *(reinterpret_cast<double*>(&x));
}

void test (__int64 ai, __int64 bi) {
    double a = ItoD(ai), b = ItoD(bi);
    bool close = std::fabs(a-b) < std::numeric_limits<double>::epsilon();
    printf ("%.16f and %.16f %s close.\n", a, b, close ? "are " : "are not");
}

int main()
{
    test (0x3fe0000000000000L,
          0x3fe0000000000001L);

    test (0x3ff0000000000000L,
          0x3ff0000000000001L);
}

Die Ausführung führt zu dieser Ausgabe:

0.5000000000000000 and 0.5000000000000001 are  close.
1.0000000000000000 and 1.0000000000000002 are not close.

Beachten Sie, dass im zweiten Fall (eins und gerade größer als eins) die beiden Eingabewerte so nahe wie möglich beieinander liegen und trotzdem als nicht nahe beieinander verglichen werden. Für Werte größer als 1,0 können Sie also genauso gut einen Gleichheitstest verwenden. Feste Epsilons helfen Ihnen nicht, wenn Sie Fließkommawerte vergleichen.

Answer 5

Leider ist auch Ihr "verschwenderischer" Code falsch. EPSILON ist der kleinste Wert, den man zu 1.0 und ändern Sie seinen Wert. Der Wert 1.0 ist sehr wichtig - größere Zahlen ändern sich nicht, wenn sie zu EPSILON hinzugefügt werden. Nun können Sie diesen Wert auf die zu vergleichenden Zahlen übertragen, um festzustellen, ob sie unterschiedlich sind oder nicht. Der korrekte Ausdruck für den Vergleich von zwei Doppelzahlen ist:

if (fabs(a - b) <= DBL_EPSILON * fmax(fabs(a), fabs(b)))
{
    // ...
}

Dies ist ein Minimum. Im Allgemeinen sollten Sie jedoch das Rauschen in Ihren Berechnungen berücksichtigen und einige der niederwertigsten Bits ignorieren, so dass ein realistischerer Vergleich wie folgt aussehen würde:

if (fabs(a - b) <= 16 * DBL_EPSILON * fmax(fabs(a), fabs(b)))
{
    // ...
}

Wenn die Vergleichsleistung für Sie sehr wichtig ist und Sie den Bereich Ihrer Werte kennen, sollten Sie stattdessen Festkommazahlen verwenden.