Was ist der effektivste Weg für Float und Doppelvergleich?

Was wäre der effizienteste Weg, um zwei doubleoder zwei floatWerte zu vergleichen ?

Einfach das zu tun ist nicht richtig:

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);
}

Scheint Abfallverarbeitung.

Kennt jemand einen intelligenteren Float-Vergleicher?

Seien Sie äußerst vorsichtig mit den anderen Vorschlägen. Es hängt alles vom Kontext ab.

Ich habe lange Zeit damit verbracht, Fehler in einem System aufzuspüren, a==bbei dem davon ausgegangen wurde, dass |a-b|<epsilon. Die zugrunde liegenden Probleme waren:

1. Die implizite Annahme in einem Algorithmus, dass wenn a==bund b==cdann a==c.

2. Verwenden des gleichen Epsilons für Linien in Zoll und Linien in Mil (0,001 Zoll). Das ist a==baber 1000a!=1000b. (Aus diesem Grund fragt AlmostEqual2sComplement nach dem epsilon oder max ULPS.)

3. Die Verwendung des gleichen Epsilons sowohl für den Kosinus der Winkel als auch für die Länge der Linien!

4. Verwenden einer solchen Vergleichsfunktion zum Sortieren von Elementen in einer Sammlung. (In diesem Fall führte die Verwendung des integrierten C ++ - Operators == für Doppel zu korrekten Ergebnissen.)

Wie ich schon sagte: Es hängt alles vom Kontext und der erwarteten Größe von aund ab b.

Übrigens std::numeric_limits<double>::epsilon()ist das "Maschinen-Epsilon". Dies ist die Differenz zwischen 1,0 und dem nächsten Wert, der durch ein Doppel dargestellt werden kann. Ich denke, dass es in der Vergleichsfunktion verwendet werden könnte, aber nur, wenn die erwarteten Werte kleiner als 1 sind. (Dies ist eine Antwort auf die Antwort von @ cdv ...)

Wenn Sie im Grunde genommen intArithmetik haben doubles(hier verwenden wir in bestimmten Fällen Doubles, um int-Werte zu halten), ist Ihre Arithmetik korrekt. Zum Beispiel ist 4.0 / 2.0 dasselbe wie 1.0 + 1.0. Dies gilt, solange Sie keine Aktionen ausführen, die zu Brüchen (4.0 / 3.0) führen, oder die Größe eines Int nicht überschreiten.

Der Vergleich mit einem Epsilon-Wert ist das, was die meisten Leute tun (sogar in der Spielprogrammierung).

Sie sollten Ihre Implementierung jedoch ein wenig ändern:

bool AreSame(double a, double b)
{
    return fabs(a - b) < EPSILON;
}

Bearbeiten: Christer hat in einem kürzlich veröffentlichten Blog-Beitrag einen Stapel großartiger Informationen zu diesem Thema hinzugefügt . Genießen.

Ich fand heraus, dass das Google C ++ Testing Framework eine nette plattformübergreifende vorlagenbasierte Implementierung von AlmostEqual2sComplement enthält, die sowohl auf Doubles als auch auf Floats funktioniert. Da es unter der BSD-Lizenz veröffentlicht wird, sollte die Verwendung in Ihrem eigenen Code kein Problem sein, solange Sie die Lizenz behalten. Ich habe den folgenden Code aus http://code.google.com/p/googletest/source/browse/trunk/include/gtest/internal/gtest-internal.h https://github.com/google/googletest/blob extrahiert /master/googletest/include/gtest/internal/gtest-internal.h und fügte die Lizenz oben hinzu.

Stellen Sie sicher, dass Sie #EST GTEST_OS_WINDOWS auf einen bestimmten Wert definieren (oder den Code, in dem er verwendet wird, in einen Wert ändern, der zu Ihrer Codebasis passt - schließlich ist er BSD-lizenziert).

Anwendungsbeispiel:

double left  = // something
double right = // something
const FloatingPoint<double> lhs(left), rhs(right);

if (lhs.AlmostEquals(rhs)) {
  //they're equal!
}

Hier ist der Code:

// Copyright 2005, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Authors: [email protected] (Zhanyong Wan), [email protected] (Sean Mcafee)
//
// The Google C++ Testing Framework (Google Test)


// This template class serves as a compile-time function from size to
// type.  It maps a size in bytes to a primitive type with that
// size. e.g.
//
//   TypeWithSize<4>::UInt
//
// is typedef-ed to be unsigned int (unsigned integer made up of 4
// bytes).
//
// Such functionality should belong to STL, but I cannot find it
// there.
//
// Google Test uses this class in the implementation of floating-point
// comparison.
//
// For now it only handles UInt (unsigned int) as that's all Google Test
// needs.  Other types can be easily added in the future if need
// arises.
template <size_t size>
class TypeWithSize {
 public:
  // This prevents the user from using TypeWithSize<N> with incorrect
  // values of N.
  typedef void UInt;
};

// The specialization for size 4.
template <>
class TypeWithSize<4> {
 public:
  // unsigned int has size 4 in both gcc and MSVC.
  //
  // As base/basictypes.h doesn't compile on Windows, we cannot use
  // uint32, uint64, and etc here.
  typedef int Int;
  typedef unsigned int UInt;
};

// The specialization for size 8.
template <>
class TypeWithSize<8> {
 public:
#if GTEST_OS_WINDOWS
  typedef __int64 Int;
  typedef unsigned __int64 UInt;
#else
  typedef long long Int;  // NOLINT
  typedef unsigned long long UInt;  // NOLINT
#endif  // GTEST_OS_WINDOWS
};


// This template class represents an IEEE floating-point number
// (either single-precision or double-precision, depending on the
// template parameters).
//
// The purpose of this class is to do more sophisticated number
// comparison.  (Due to round-off error, etc, it's very unlikely that
// two floating-points will be equal exactly.  Hence a naive
// comparison by the == operation often doesn't work.)
//
// Format of IEEE floating-point:
//
//   The most-significant bit being the leftmost, an IEEE
//   floating-point looks like
//
//     sign_bit exponent_bits fraction_bits
//
//   Here, sign_bit is a single bit that designates the sign of the
//   number.
//
//   For float, there are 8 exponent bits and 23 fraction bits.
//
//   For double, there are 11 exponent bits and 52 fraction bits.
//
//   More details can be found at
//   http://en.wikipedia.org/wiki/IEEE_floating-point_standard.
//
// Template parameter:
//
//   RawType: the raw floating-point type (either float or double)
template <typename RawType>
class FloatingPoint {
 public:
  // Defines the unsigned integer type that has the same size as the
  // floating point number.
  typedef typename TypeWithSize<sizeof(RawType)>::UInt Bits;

  // Constants.

  // # of bits in a number.
  static const size_t kBitCount = 8*sizeof(RawType);

  // # of fraction bits in a number.
  static const size_t kFractionBitCount =
    std::numeric_limits<RawType>::digits - 1;

  // # of exponent bits in a number.
  static const size_t kExponentBitCount = kBitCount - 1 - kFractionBitCount;

  // The mask for the sign bit.
  static const Bits kSignBitMask = static_cast<Bits>(1) << (kBitCount - 1);

  // The mask for the fraction bits.
  static const Bits kFractionBitMask =
    ~static_cast<Bits>(0) >> (kExponentBitCount + 1);

  // The mask for the exponent bits.
  static const Bits kExponentBitMask = ~(kSignBitMask | kFractionBitMask);

  // How many ULP's (Units in the Last Place) we want to tolerate when
  // comparing two numbers.  The larger the value, the more error we
  // allow.  A 0 value means that two numbers must be exactly the same
  // to be considered equal.
  //
  // The maximum error of a single floating-point operation is 0.5
  // units in the last place.  On Intel CPU's, all floating-point
  // calculations are done with 80-bit precision, while double has 64
  // bits.  Therefore, 4 should be enough for ordinary use.
  //
  // See the following article for more details on ULP:
  // http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm.
  static const size_t kMaxUlps = 4;

  // Constructs a FloatingPoint from a raw floating-point number.
  //
  // On an Intel CPU, passing a non-normalized NAN (Not a Number)
  // around may change its bits, although the new value is guaranteed
  // to be also a NAN.  Therefore, don't expect this constructor to
  // preserve the bits in x when x is a NAN.
  explicit FloatingPoint(const RawType& x) { u_.value_ = x; }

  // Static methods

  // Reinterprets a bit pattern as a floating-point number.
  //
  // This function is needed to test the AlmostEquals() method.
  static RawType ReinterpretBits(const Bits bits) {
    FloatingPoint fp(0);
    fp.u_.bits_ = bits;
    return fp.u_.value_;
  }

  // Returns the floating-point number that represent positive infinity.
  static RawType Infinity() {
    return ReinterpretBits(kExponentBitMask);
  }

  // Non-static methods

  // Returns the bits that represents this number.
  const Bits &bits() const { return u_.bits_; }

  // Returns the exponent bits of this number.
  Bits exponent_bits() const { return kExponentBitMask & u_.bits_; }

  // Returns the fraction bits of this number.
  Bits fraction_bits() const { return kFractionBitMask & u_.bits_; }

  // Returns the sign bit of this number.
  Bits sign_bit() const { return kSignBitMask & u_.bits_; }

  // Returns true iff this is NAN (not a number).
  bool is_nan() const {
    // It's a NAN if the exponent bits are all ones and the fraction
    // bits are not entirely zeros.
    return (exponent_bits() == kExponentBitMask) && (fraction_bits() != 0);
  }

  // Returns true iff this number is at most kMaxUlps ULP's away from
  // rhs.  In particular, this function:
  //
  //   - returns false if either number is (or both are) NAN.
  //   - treats really large numbers as almost equal to infinity.
  //   - thinks +0.0 and -0.0 are 0 DLP's apart.
  bool AlmostEquals(const FloatingPoint& rhs) const {
    // The IEEE standard says that any comparison operation involving
    // a NAN must return false.
    if (is_nan() || rhs.is_nan()) return false;

    return DistanceBetweenSignAndMagnitudeNumbers(u_.bits_, rhs.u_.bits_)
        <= kMaxUlps;
  }

 private:
  // The data type used to store the actual floating-point number.
  union FloatingPointUnion {
    RawType value_;  // The raw floating-point number.
    Bits bits_;      // The bits that represent the number.
  };

  // Converts an integer from the sign-and-magnitude representation to
  // the biased representation.  More precisely, let N be 2 to the
  // power of (kBitCount - 1), an integer x is represented by the
  // unsigned number x + N.
  //
  // For instance,
  //
  //   -N + 1 (the most negative number representable using
  //          sign-and-magnitude) is represented by 1;
  //   0      is represented by N; and
  //   N - 1  (the biggest number representable using
  //          sign-and-magnitude) is represented by 2N - 1.
  //
  // Read http://en.wikipedia.org/wiki/Signed_number_representations
  // for more details on signed number representations.
  static Bits SignAndMagnitudeToBiased(const Bits &sam) {
    if (kSignBitMask & sam) {
      // sam represents a negative number.
      return ~sam + 1;
    } else {
      // sam represents a positive number.
      return kSignBitMask | sam;
    }
  }

  // Given two numbers in the sign-and-magnitude representation,
  // returns the distance between them as an unsigned number.
  static Bits DistanceBetweenSignAndMagnitudeNumbers(const Bits &sam1,
                                                     const Bits &sam2) {
    const Bits biased1 = SignAndMagnitudeToBiased(sam1);
    const Bits biased2 = SignAndMagnitudeToBiased(sam2);
    return (biased1 >= biased2) ? (biased1 - biased2) : (biased2 - biased1);
  }

  FloatingPointUnion u_;
};

EDIT: Dieser Beitrag ist 4 Jahre alt. Es ist wahrscheinlich immer noch gültig und der Code ist nett, aber einige Leute haben Verbesserungen gefunden. Am besten holen Sie sich die neueste Version von AlmostEqualsdirekt aus dem Google Test-Quellcode und nicht die, die ich hier eingefügt habe.

Der Vergleich von Gleitkommazahlen für hängt vom Kontext ab. Da selbst das Ändern der Reihenfolge der Operationen zu unterschiedlichen Ergebnissen führen kann, ist es wichtig zu wissen, wie "gleich" die Zahlen sein sollen.

Der Vergleich von Gleitkommazahlen von Bruce Dawson ist ein guter Ausgangspunkt für den Gleitkommavergleich.

Die folgenden Definitionen stammen aus der Kunst der Computerprogrammierung von Knuth :

bool approximatelyEqual(float a, float b, float epsilon)
{
    return fabs(a - b) <= ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool essentiallyEqual(float a, float b, float epsilon)
{
    return fabs(a - b) <= ( (fabs(a) > fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyGreaterThan(float a, float b, float epsilon)
{
    return (a - b) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyLessThan(float a, float b, float epsilon)
{
    return (b - a) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

Die Auswahl von epsilon hängt natürlich vom Kontext ab und bestimmt, wie gleich die Zahlen sein sollen.

Eine andere Methode zum Vergleichen von Gleitkommazahlen besteht darin, den ULP (Einheiten an letzter Stelle) der Zahlen zu betrachten. Das Papier Was jeder Informatiker über Gleitkommazahlen wissen sollte, ist eine gute Quelle, um zu verstehen, wie Gleitkommazahlen funktionieren und welche Fallstricke es gibt, einschließlich der Frage, was ULP ist.

Weitere Informationen finden Sie unter Vergleichen von Gleitkommazahlen . Hier ist das Code-Snippet von diesem Link:

// Usable AlmostEqual function    
bool AlmostEqual2sComplement(float A, float B, int maxUlps)    
{    
    // Make sure maxUlps is non-negative and small enough that the    
    // default NAN won't compare as equal to anything.    
    assert(maxUlps > 0 && maxUlps < 4 * 1024 * 1024);    
    int aInt = *(int*)&A;    
    // Make aInt lexicographically ordered as a twos-complement int    
    if (aInt < 0)    
        aInt = 0x80000000 - aInt;    
    // Make bInt lexicographically ordered as a twos-complement int    
    int bInt = *(int*)&B;    
    if (bInt < 0)    
        bInt = 0x80000000 - bInt;    
    int intDiff = abs(aInt - bInt);    
    if (intDiff <= maxUlps)    
        return true;    
    return false;    
}

Die Erkenntnis, dass dies ein alter Thread ist, aber dieser Artikel ist einer der einfachsten, den ich beim Vergleichen von Gleitkommazahlen gefunden habe. Wenn Sie mehr darüber erfahren möchten, enthält er auch detailliertere Referenzen und die Hauptseite deckt eine ganze Reihe von Themen ab Umgang mit Gleitkommazahlen Der Gleitkomma-Leitfaden: Vergleich .

Wir finden einen etwas praktischeren Artikel in Gleitkommatoleranzen überarbeitet und stellen fest, dass es einen absoluten Toleranztest gibt , der in C ++ darauf hinausläuft:

bool absoluteToleranceCompare(double x, double y)
{
    return std::fabs(x - y) <= std::numeric_limits<double>::epsilon() ;
}

und relativer Toleranztest :

bool relativeToleranceCompare(double x, double y)
{
    double maxXY = std::max( std::fabs(x) , std::fabs(y) ) ;
    return std::fabs(x - y) <= std::numeric_limits<double>::epsilon()*maxXY ;
}

Der Artikel stellt fest , dass der absolute Test schlägt fehl , wenn xund yist groß und nicht in dem relativen Fall , wenn sie klein sind. Unter der Annahme, dass die absolute und relative Toleranz gleich sind, würde ein kombinierter Test folgendermaßen aussehen:

bool combinedToleranceCompare(double x, double y)
{
    double maxXYOne = std::max( { 1.0, std::fabs(x) , std::fabs(y) } ) ;

    return std::fabs(x - y) <= std::numeric_limits<double>::epsilon()*maxXYOne ;
}

Der tragbare Weg, um epsilon in C ++ zu bekommen, ist

#include <limits>
std::numeric_limits<double>::epsilon()

Dann wird die Vergleichsfunktion

#include <cmath>
#include <limits>

bool AreSame(double a, double b) {
    return std::fabs(a - b) < std::numeric_limits<double>::epsilon();
}

Am Ende habe ich einige Zeit damit verbracht, Material in diesem großartigen Thread durchzugehen. Ich bezweifle, dass jeder so viel Zeit verbringen möchte, um die Zusammenfassung meiner Erkenntnisse und die von mir implementierte Lösung hervorzuheben.

Kurze Zusammenfassung

1. Ist 1e-8 ungefähr gleich 1e-16? Wenn Sie verrauschte Sensordaten betrachten, dann wahrscheinlich ja, aber wenn Sie eine molekulare Simulation durchführen, ist dies möglicherweise nicht der Fall! Fazit: Sie müssen immer an den Toleranzwert im Kontext eines bestimmten Funktionsaufrufs denken und ihn nicht nur als generische app-weite fest codierte Konstante festlegen.
2. Für allgemeine Bibliotheksfunktionen ist es immer noch schön, Parameter mit Standardtoleranz zu haben . Eine typische Auswahl ist numeric_limits::epsilon()die gleiche wie FLT_EPSILON in float.h. Dies ist jedoch problematisch, da epsilon zum Vergleichen von Werten wie 1.0 nicht mit epsilon zum Vergleichen von Werten wie 1E9 identisch ist. Das FLT_EPSILON ist für 1.0 definiert.
3. Die offensichtliche Implementierung, um zu überprüfen, ob die Anzahl innerhalb der Toleranz liegt, fabs(a-b) <= epsilonfunktioniert jedoch nicht, da das Standard-Epsilon für 1.0 definiert ist. Wir müssen Epsilon in Bezug auf a und b nach oben oder unten skalieren.
4. Für dieses Problem gibt es zwei Lösungen: Entweder setzen Sie epsilon proportional zu max(a,b)oder Sie können die nächsten darstellbaren Zahlen um a erhalten und dann prüfen, ob b in diesen Bereich fällt. Ersteres wird als "relative" Methode und später als ULP-Methode bezeichnet.
5. Beide Methoden schlagen beim Vergleich mit 0 ohnehin fehl. In diesem Fall muss die Anwendung die richtige Toleranz liefern.

Implementierung von Dienstprogrammfunktionen (C ++ 11)

//implements relative method - do not use for comparing with zero
//use this most of the time, tolerance needs to be meaningful in your context
template<typename TReal>
static bool isApproximatelyEqual(TReal a, TReal b, TReal tolerance = std::numeric_limits<TReal>::epsilon())
{
    TReal diff = std::fabs(a - b);
    if (diff <= tolerance)
        return true;

    if (diff < std::fmax(std::fabs(a), std::fabs(b)) * tolerance)
        return true;

    return false;
}

//supply tolerance that is meaningful in your context
//for example, default tolerance may not work if you are comparing double with float
template<typename TReal>
static bool isApproximatelyZero(TReal a, TReal tolerance = std::numeric_limits<TReal>::epsilon())
{
    if (std::fabs(a) <= tolerance)
        return true;
    return false;
}


//use this when you want to be on safe side
//for example, don't start rover unless signal is above 1
template<typename TReal>
static bool isDefinitelyLessThan(TReal a, TReal b, TReal tolerance = std::numeric_limits<TReal>::epsilon())
{
    TReal diff = a - b;
    if (diff < tolerance)
        return true;

    if (diff < std::fmax(std::fabs(a), std::fabs(b)) * tolerance)
        return true;

    return false;
}
template<typename TReal>
static bool isDefinitelyGreaterThan(TReal a, TReal b, TReal tolerance = std::numeric_limits<TReal>::epsilon())
{
    TReal diff = a - b;
    if (diff > tolerance)
        return true;

    if (diff > std::fmax(std::fabs(a), std::fabs(b)) * tolerance)
        return true;

    return false;
}

//implements ULP method
//use this when you are only concerned about floating point precision issue
//for example, if you want to see if a is 1.0 by checking if its within
//10 closest representable floating point numbers around 1.0.
template<typename TReal>
static bool isWithinPrecisionInterval(TReal a, TReal b, unsigned int interval_size = 1)
{
    TReal min_a = a - (a - std::nextafter(a, std::numeric_limits<TReal>::lowest())) * interval_size;
    TReal max_a = a + (std::nextafter(a, std::numeric_limits<TReal>::max()) - a) * interval_size;

    return min_a <= b && max_a >= b;
}

Der Code, den Sie geschrieben haben, ist fehlerhaft:

return (diff < EPSILON) && (-diff > EPSILON);

Der richtige Code wäre:

return (diff < EPSILON) && (diff > -EPSILON);

(... und ja das ist anders)

Ich frage mich, ob Fabs Sie in einigen Fällen nicht dazu bringen würden, die faule Bewertung zu verlieren. Ich würde sagen, es hängt vom Compiler ab. Vielleicht möchten Sie beide ausprobieren. Wenn sie im Durchschnitt gleichwertig sind, nehmen Sie die Implementierung mit fabs.

Wenn Sie Informationen darüber haben, welcher der beiden Floats mit größerer Wahrscheinlichkeit größer ist als der andere, können Sie in der Reihenfolge des Vergleichs spielen, um die verzögerte Bewertung besser nutzen zu können.

Schließlich können Sie ein besseres Ergebnis erzielen, wenn Sie diese Funktion einbinden. Es ist jedoch unwahrscheinlich, dass sich viel verbessert ...

Edit: OJ, danke für die Korrektur deines Codes. Ich habe meinen Kommentar entsprechend gelöscht

`return fabs (a - b) <EPSILON;

Dies ist in Ordnung, wenn:

• Die Größenordnung Ihrer Eingaben ändert sich nicht wesentlich
• Eine sehr kleine Anzahl entgegengesetzter Vorzeichen kann als gleich behandelt werden

Aber sonst bringt es dich in Schwierigkeiten. Zahlen mit doppelter Genauigkeit haben eine Auflösung von etwa 16 Dezimalstellen. Wenn die beiden Zahlen, die Sie vergleichen, größer sind als EPSILON * 1.0E16, können Sie genauso gut sagen:

return a==b;

Ich werde einen anderen Ansatz untersuchen, bei dem davon ausgegangen wird, dass Sie sich um das erste Problem kümmern müssen, und davon, dass das zweite Problem für Ihre Anwendung in Ordnung ist. Eine Lösung wäre so etwas wie:

#define VERYSMALL  (1.0E-150)
#define EPSILON    (1.0E-8)
bool AreSame(double a, double b)
{
    double absDiff = fabs(a - b);
    if (absDiff < VERYSMALL)
    {
        return true;
    }

    double maxAbs  = max(fabs(a) - fabs(b));
    return (absDiff/maxAbs) < EPSILON;
}

Dies ist rechenintensiv, aber manchmal erforderlich. Dies müssen wir in meinem Unternehmen tun, da es sich um eine technische Bibliothek handelt und die Eingaben um einige Dutzend Größenordnungen variieren können.

Auf jeden Fall geht es darum (und gilt für praktisch jedes Programmierproblem): Bewerten Sie Ihre Anforderungen und finden Sie dann eine Lösung, um Ihre Anforderungen zu erfüllen. Gehen Sie nicht davon aus, dass die einfache Antwort Ihren Anforderungen entspricht. Wenn Sie nach Ihrer Bewertung feststellen, dass dies fabs(a-b) < EPSILONausreicht, perfekt - verwenden Sie es! Beachten Sie jedoch auch die Mängel und andere mögliche Lösungen.

Wie andere bereits betont haben, ist die Verwendung eines Epsilons mit festem Exponenten (z. B. 0,0000001) für Werte außerhalb des Epsilon-Werts unbrauchbar . Wenn Ihre beiden Werte beispielsweise 10000.000977 und 10000 sind, gibt es zwischen diesen beiden Zahlen KEINE 32-Bit-Gleitkommawerte - 10000 und 10000.000977 liegen so nahe wie möglich, ohne bitweise identisch zu sein. Hier ist ein Epsilon von weniger als 0,0009 bedeutungslos; Sie können auch den geraden Gleichheitsoperator verwenden.

Wenn sich die beiden Werte einer Größe von epsilon nähern, wächst der relative Fehler ebenfalls auf 100%.

Der Versuch, eine Festkommazahl wie 0,00001 mit Gleitkommawerten (wobei der Exponent beliebig ist) zu mischen, ist daher sinnlos. Dies funktioniert immer nur, wenn Sie sicher sein können, dass die Operandenwerte in einem engen Bereich liegen (dh in der Nähe eines bestimmten Exponenten), und wenn Sie einen Epsilon-Wert für diesen bestimmten Test richtig auswählen. Wenn Sie eine Zahl aus der Luft ziehen ("Hey! 0.00001 ist klein, das muss also gut sein!"), Sind Sie zu numerischen Fehlern verurteilt. Ich habe viel Zeit damit verbracht, schlechten numerischen Code zu debuggen, bei dem ein armer Trottel zufällige Epsilon-Werte einwirft, damit ein weiterer Testfall funktioniert.

Wenn Sie numerische Programmierungen jeglicher Art durchführen und glauben, dass Sie nach Festpunkt-Epsilons greifen müssen, LESEN SIE BRUCES ARTIKEL ZUM VERGLEICH VON SCHWIMMUNGSPUNKTNUMMERN .

Gleitkommazahlen vergleichen

Qt implementiert zwei Funktionen, vielleicht können Sie daraus 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 möglicherweise benötigen Sie die folgenden Funktionen, da

Beachten Sie, dass das Vergleichen von Werten, bei denen entweder p1 oder p2 0,0 ist, nicht funktioniert, und das Vergleichen von Werten, bei denen einer der Werte NaN oder unendlich ist, nicht funktioniert. Wenn einer der Werte immer 0.0 ist, verwenden Sie stattdessen qFuzzyIsNull. Wenn einer der Werte wahrscheinlich 0,0 ist, besteht eine Lösung darin, beiden Werten 1,0 hinzuzufügen.

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

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

Der allgemeine Vergleich von Gleitkommazahlen ist im Allgemeinen bedeutungslos. Wie man vergleicht, hängt wirklich von einem Problem ab. Bei vielen Problemen sind Zahlen ausreichend diskretisiert, um sie innerhalb einer bestimmten Toleranz vergleichen zu können. Leider gibt es genauso viele Probleme, bei denen ein solcher Trick nicht wirklich funktioniert. Betrachten Sie zum Beispiel die Arbeit mit einer Heaviside- (Schritt-) Funktion einer fraglichen Zahl (digitale Aktienoptionen kommen in den Sinn), wenn Ihre Beobachtungen sehr nahe an der Barriere liegen. Ein toleranzbasierter Vergleich würde nicht viel nützen, da das Problem effektiv von der ursprünglichen Barriere auf zwei neue verschoben würde. Auch hier gibt es keine universelle Lösung für solche Probleme, und die spezielle Lösung erfordert möglicherweise eine Änderung der numerischen Methode, um Stabilität zu erreichen.

Leider ist sogar Ihr "verschwenderischer" Code falsch. EPSILON ist der kleinste Wert, der zu 1.0 addiert und sein Wert geändert werden kann. Der Wert 1.0 ist sehr wichtig - größere Zahlen ändern sich nicht, wenn sie zu EPSILON hinzugefügt werden. Jetzt können Sie diesen Wert auf die Zahlen skalieren, die Sie vergleichen, um festzustellen, ob sie unterschiedlich sind oder nicht. Der richtige Ausdruck für den Vergleich zweier Doppel 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 niedrigstwertigen Bits ignorieren, sodass ein realistischerer Vergleich folgendermaßen aussehen würde:

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

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

Meine Klasse basiert auf zuvor veröffentlichten Antworten. Sehr ähnlich zu Googles Code, aber ich verwende einen Bias, der alle NaN-Werte über 0xFF000000 verschiebt. Dies ermöglicht eine schnellere Überprüfung auf NaN.

Dieser Code soll das Konzept demonstrieren und keine allgemeine Lösung sein. Der Code von Google zeigt bereits, wie alle plattformspezifischen Werte berechnet werden, und ich wollte das alles nicht duplizieren. Ich habe diesen Code nur begrenzt getestet.

typedef unsigned int   U32;
//  Float           Memory          Bias (unsigned)
//  -----           ------          ---------------
//   NaN            0xFFFFFFFF      0xFF800001
//   NaN            0xFF800001      0xFFFFFFFF
//  -Infinity       0xFF800000      0x00000000 ---
//  -3.40282e+038   0xFF7FFFFF      0x00000001    |
//  -1.40130e-045   0x80000001      0x7F7FFFFF    |
//  -0.0            0x80000000      0x7F800000    |--- Valid <= 0xFF000000.
//   0.0            0x00000000      0x7F800000    |    NaN > 0xFF000000
//   1.40130e-045   0x00000001      0x7F800001    |
//   3.40282e+038   0x7F7FFFFF      0xFEFFFFFF    |
//   Infinity       0x7F800000      0xFF000000 ---
//   NaN            0x7F800001      0xFF000001
//   NaN            0x7FFFFFFF      0xFF7FFFFF
//
//   Either value of NaN returns false.
//   -Infinity and +Infinity are not "close".
//   -0 and +0 are equal.
//
class CompareFloat{
public:
    union{
        float     m_f32;
        U32       m_u32;
    };
    static bool   CompareFloat::IsClose( float A, float B, U32 unitsDelta = 4 )
                  {
                      U32    a = CompareFloat::GetBiased( A );
                      U32    b = CompareFloat::GetBiased( B );

                      if ( (a > 0xFF000000) || (b > 0xFF000000) )
                      {
                          return( false );
                      }
                      return( (static_cast<U32>(abs( a - b ))) < unitsDelta );
                  }
    protected:
    static U32    CompareFloat::GetBiased( float f )
                  {
                      U32    r = ((CompareFloat*)&f)->m_u32;

                      if ( r & 0x80000000 )
                      {
                          return( ~r - 0x007FFFFF );
                      }
                      return( r + 0x7F800000 );
                  }
};

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

Beweis meines obigen Kommentars:

#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);
}

Laufen ergibt diese Ausgabe:

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

Beachten Sie, dass im zweiten Fall (eins und nur größer als eins) die beiden Eingabewerte so nahe wie möglich sind und dennoch als nicht nahe verglichen werden. Für Werte größer als 1,0 können Sie daher auch einfach einen Gleichheitstest verwenden. Feste Epsilons sparen Sie beim Vergleich von Gleitkommawerten nicht.

Eine weitere interessante Implementierung wurde gefunden unter: https://en.cppreference.com/w/cpp/types/numeric_limits/epsilon

#include <cmath>
#include <limits>
#include <iomanip>
#include <iostream>
#include <type_traits>
#include <algorithm>



template<class T>
typename std::enable_if<!std::numeric_limits<T>::is_integer, bool>::type
    almost_equal(T x, T y, int ulp)
{
    // the machine epsilon has to be scaled to the magnitude of the values used
    // and multiplied by the desired precision in ULPs (units in the last place)
    return std::fabs(x-y) <= std::numeric_limits<T>::epsilon() * std::fabs(x+y) * ulp
        // unless the result is subnormal
        || std::fabs(x-y) < std::numeric_limits<T>::min();
}

int main()
{
    double d1 = 0.2;
    double d2 = 1 / std::sqrt(5) / std::sqrt(5);
    std::cout << std::fixed << std::setprecision(20) 
        << "d1=" << d1 << "\nd2=" << d2 << '\n';

    if(d1 == d2)
        std::cout << "d1 == d2\n";
    else
        std::cout << "d1 != d2\n";

    if(almost_equal(d1, d2, 2))
        std::cout << "d1 almost equals d2\n";
    else
        std::cout << "d1 does not almost equal d2\n";
}

Ich wäre sehr vorsichtig mit diesen Antworten, die eine Gleitkommasubtraktion beinhalten (z. B. fabs (ab) <epsilon). Erstens werden die Gleitkommazahlen bei größeren Größen und bei ausreichend großen Größen, bei denen der Abstand größer als epsilon ist, spärlicher. Sie können auch einfach a == b ausführen. Zweitens erhalten Sie durch das Subtrahieren von zwei sehr engen Gleitkommazahlen (wie dies normalerweise der Fall ist, wenn Sie nach nahezu Gleichheit suchen) eine katastrophale Stornierung .

Obwohl nicht tragbar, denke ich, dass die Antwort von grom diese Probleme am besten vermeidet.

Es gibt tatsächlich Fälle in numerischer Software, in denen Sie überprüfen möchten, ob zwei Gleitkommazahlen genau gleich sind. Ich habe dies auf eine ähnliche Frage gestellt

https://stackoverflow.com/a/10973098/1447411

Man kann also nicht sagen, dass "CompareDoubles1" im Allgemeinen falsch ist.

Dies hängt davon ab, wie genau der Vergleich sein soll. Wenn Sie für genau die gleiche Zahl vergleichen möchten, gehen Sie einfach mit ==. (Sie möchten dies fast nie tun, es sei denn, Sie möchten tatsächlich genau dieselbe Nummer.) Auf jeder anständigen Plattform können Sie auch Folgendes tun:

diff= a - b; return fabs(diff)<EPSILON;

da fabsneigt dazu, ziemlich schnell zu sein. Mit ziemlich schnell meine ich, dass es im Grunde ein bitweises UND ist, also ist es besser, schnell zu sein.

Ganzzahlige Tricks zum Vergleichen von Double und Floats sind nett, erschweren jedoch die effektive Handhabung der verschiedenen CPU-Pipelines. Und es ist heutzutage definitiv nicht schneller auf bestimmten in-order-Architekturen, da der Stack als temporärer Speicherbereich für Werte verwendet wird, die häufig verwendet werden. (Load-Hit-Store für diejenigen, die sich interessieren.)

In Bezug auf den Mengenumfang:

Wenn epsilonder kleine Bruchteil der Größe der Menge (dh der relative Wert) in einem bestimmten physikalischen Sinne und Aund BTypen in demselben Sinne vergleichbar ist, denke ich, dass das Folgende ganz richtig ist:

#include <limits>
#include <iomanip>
#include <iostream>

#include <cmath>
#include <cstdlib>
#include <cassert>

template< typename A, typename B >
inline
bool close_enough(A const & a, B const & b,
                  typename std::common_type< A, B >::type const & epsilon)
{
    using std::isless;
    assert(isless(0, epsilon)); // epsilon is a part of the whole quantity
    assert(isless(epsilon, 1));
    using std::abs;
    auto const delta = abs(a - b);
    auto const x = abs(a);
    auto const y = abs(b);
    // comparable generally and |a - b| < eps * (|a| + |b|) / 2
    return isless(epsilon * y, x) && isless(epsilon * x, y) && isless((delta + delta) / (x + y), epsilon);
}

int main()
{
    std::cout << std::boolalpha << close_enough(0.9, 1.0, 0.1) << std::endl;
    std::cout << std::boolalpha << close_enough(1.0, 1.1, 0.1) << std::endl;
    std::cout << std::boolalpha << close_enough(1.1,    1.2,    0.01) << std::endl;
    std::cout << std::boolalpha << close_enough(1.0001, 1.0002, 0.01) << std::endl;
    std::cout << std::boolalpha << close_enough(1.0, 0.01, 0.1) << std::endl;
    return EXIT_SUCCESS;
}

Ich benutze diesen Code:

bool AlmostEqual(double v1, double v2)
    {
        return (std::fabs(v1 - v2) < std::fabs(std::min(v1, v2)) * std::numeric_limits<double>::epsilon());
    }

Ich schreibe das für Java, aber vielleicht findest du es nützlich. Es verwendet Longs anstelle von Doubles, kümmert sich jedoch um NaNs, Subnormen usw.

public static boolean equal(double a, double b) {
    final long fm = 0xFFFFFFFFFFFFFL;       // fraction mask
    final long sm = 0x8000000000000000L;    // sign mask
    final long cm = 0x8000000000000L;       // most significant decimal bit mask
    long c = Double.doubleToLongBits(a), d = Double.doubleToLongBits(b);        
    int ea = (int) (c >> 52 & 2047), eb = (int) (d >> 52 & 2047);
    if (ea == 2047 && (c & fm) != 0 || eb == 2047 && (d & fm) != 0) return false;   // NaN 
    if (c == d) return true;                            // identical - fast check
    if (ea == 0 && eb == 0) return true;                // ±0 or subnormals
    if ((c & sm) != (d & sm)) return false;             // different signs
    if (abs(ea - eb) > 1) return false;                 // b > 2*a or a > 2*b
    d <<= 12; c <<= 12;
    if (ea < eb) c = c >> 1 | sm;
    else if (ea > eb) d = d >> 1 | sm;
    c -= d;
    return c < 65536 && c > -65536;     // don't use abs(), because:
    // There is a posibility c=0x8000000000000000 which cannot be converted to positive
}
public static boolean zero(double a) { return (Double.doubleToLongBits(a) >> 52 & 2047) < 3; }

Beachten Sie, dass sich die Anzahl nach einer Reihe von Gleitkommaoperationen stark von unseren Erwartungen unterscheiden kann. Es gibt keinen Code, um das zu beheben.

Wie wäre es damit?

template<typename T>
bool FloatingPointEqual( T a, T b ) { return !(a < b) && !(b < a); }

Ich habe verschiedene Ansätze gesehen - aber noch nie gesehen, deshalb bin ich auch neugierig auf Kommentare!

/// testing whether two doubles are almost equal. We consider two doubles
/// equal if the difference is within the range [0, epsilon).
///
/// epsilon: a positive number (supposed to be small)
///
/// if either x or y is 0, then we are comparing the absolute difference to
/// epsilon.
/// if both x and y are non-zero, then we are comparing the relative difference
/// to epsilon.
bool almost_equal(double x, double y, double epsilon)
{
    double diff = x - y;
    if (x != 0 && y != 0){
        diff = diff/y; 
    }

    if (diff < epsilon && -1.0*diff < epsilon){
        return true;
    }
    return false;
}

Ich habe diese Funktion für mein kleines Projekt verwendet und sie funktioniert, aber beachten Sie Folgendes:

Fehler mit doppelter Genauigkeit können eine Überraschung für Sie sein. Angenommen, epsilon = 1.0e-6, dann sollten 1.0 und 1.000001 gemäß dem obigen Code NICHT als gleich angesehen werden. Auf meinem Computer werden sie jedoch von der Funktion als gleich angesehen. Dies liegt daran, dass 1.000001 nicht präzise in ein Binärformat übersetzt werden kann. es ist wahrscheinlich 1.0000009xxx. Ich teste es mit 1.0 und 1.0000011 und diesmal erhalte ich das erwartete Ergebnis.

Dies ist eine weitere Lösung mit Lambda:

#include <cmath>
#include <limits>

auto Compare = [](float a, float b, float epsilon = std::numeric_limits<float>::epsilon()){ return (std::fabs(a - b) <= epsilon); };

Mein Weg ist vielleicht nicht richtig, aber nützlich

Konvertieren Sie beide float in Strings und vergleichen Sie dann die Strings

bool IsFlaotEqual(float a, float b, int decimal)
{
    TCHAR form[50] = _T("");
    _stprintf(form, _T("%%.%df"), decimal);


    TCHAR a1[30] = _T(""), a2[30] = _T("");
    _stprintf(a1, form, a);
    _stprintf(a2, form, b);

    if( _tcscmp(a1, a2) == 0 )
        return true;

    return false;

}

Eine Überlappung des Operators kann ebenfalls durchgeführt werden

Sie können nicht zwei doublemit einem festen vergleichen EPSILON. Abhängig vom Wert von double, EPSILONvariiert.

Ein besserer Doppelvergleich wäre:

bool same(double a, double b)
{
  return std::nextafter(a, std::numeric_limits<double>::lowest()) <= b
    && std::nextafter(a, std::numeric_limits<double>::max()) >= b;
}

Allgemeiner ausgedrückt:

template <typename T>
bool compareNumber(const T& a, const T& b) {
    return std::abs(a - b) < std::numeric_limits<T>::epsilon();
}

Warum nicht bitweises XOR durchführen? Zwei Gleitkommazahlen sind gleich, wenn ihre entsprechenden Bits gleich sind. Ich denke, die Entscheidung, die Exponentenbits vor der Mantisse zu platzieren, wurde getroffen, um den Vergleich zweier Floats zu beschleunigen. Ich denke, vielen Antworten hier fehlt der Punkt des Epsilon-Vergleichs. Der Epsilon-Wert hängt nur davon ab, mit welcher Genauigkeit Gleitkommazahlen verglichen werden. Wenn Sie beispielsweise mit Floats rechnen, erhalten Sie zwei Zahlen: 2.5642943554342 und 2.5642943554345. Sie sind nicht gleich, aber für die Lösung sind nur 3 Dezimalstellen von Bedeutung. Dann sind sie gleich: 2,564 und 2,564. In diesem Fall wählen Sie epsilon gleich 0,001. Ein Epsilon-Vergleich ist auch mit bitweisem XOR möglich. Korrigieren Sie mich, wenn ich falsch liege.