Question Quel est le moyen le plus efficace pour le float et la double comparaison?


Quel serait le moyen le plus efficace de comparer deux double ou deux float valeurs?

Faire simplement ceci n'est pas correct:

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

Mais quelque chose comme:

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

Semble au traitement des déchets.

Quelqu'un sait-il un smarter float plus intelligent?


437
2017-08-20 02:09


origine


Réponses:


Soyez extrêmement prudent en utilisant l'une des autres suggestions. Tout dépend du contexte.

J'ai passé beaucoup de temps à localiser un bogue dans un système qui présume a==b si |a-b|<epsilon. Les problèmes sous-jacents étaient:

  1. La présomption implicite dans un algorithme que si a==b et b==c puis a==c.

  2. En utilisant le même epsilon pour les lignes mesurées en pouces et en lignes mesurées en mils (0,001 pouce). C'est a==b mais 1000a!=1000b. (C'est pourquoi AlmostEqual2sComplement demande l'epsilon ou max ULPS).

  3. L'utilisation du même epsilon pour le cosinus des angles et la longueur des lignes!

  4. Utiliser une telle fonction de comparaison pour trier les éléments d'une collection. (Dans ce cas, l'utilisation de l'opérateur C ++ intégré == pour les doubles a produit des résultats corrects.)

Comme je l'ai dit: tout dépend du contexte et de la taille attendue a et b.

BTW, std::numeric_limits<double>::epsilon() est la "machine epsilon". C'est la différence entre 1.0 et la prochaine valeur représentable par un double. Je suppose qu'il pourrait être utilisé dans la fonction de comparaison mais seulement si les valeurs attendues sont inférieures à 1. (Ceci est en réponse à la réponse de @ cdv ...)

Aussi, si vous avez essentiellement int arithmétique dans doubles (ici nous utilisons des doubles pour tenir des valeurs int dans certains cas) votre arithmétique sera correcte. Par exemple 4.0 / 2.0 sera le même que 1.0 + 1.0. C'est tant que vous ne faites pas des choses qui résultent en fractions (4.0 / 3.0) ou ne sortez pas de la taille d'un int.


387
2017-09-16 22:06



La comparaison avec une valeur epsilon est ce que la plupart des gens font (même dans la programmation de jeux).

Vous devriez changer votre implémentation un peu:

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

Edit: Christer a ajouté une pile d'informations sur ce sujet sur un blog récent. Prendre plaisir.


162
2017-08-20 02:14



J'ai trouvé que le Cadre de test Google C ++ contient une belle implémentation de AlmostEqual2sComplement basée sur un modèle multiplateforme qui fonctionne à la fois sur les doubles et les flottants. Étant donné qu'il est publié sous licence BSD, l'utiliser dans votre propre code ne devrait poser aucun problème, tant que vous conservez la licence. J'ai extrait le code ci-dessous de http://code.google.com/p/googletest/source/browse/trunk/include/gtest/internal/gtest-internal.h  https://github.com/google/googletest/blob/master/googletest/include/gtest/internal/gtest-internal.h et ajouté la licence en haut.

Assurez-vous de #define GTEST_OS_WINDOWS à une certaine valeur (ou de changer le code où il est utilisé pour quelque chose qui correspond à votre base de code - c'est une licence BSD après tout).

Exemple d'utilisation:

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

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

Voici le 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: wan@google.com (Zhanyong Wan), eefacm@gmail.com (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: Cet article a 4 ans. C'est probablement encore valide, et le code est sympa, mais certaines personnes ont trouvé des améliorations. Mieux vaut aller chercher la dernière version de AlmostEqualsdirectement depuis le code source de Google Test, et non celui que j'ai collé ici.


101
2017-08-06 11:24



La comparaison des nombres à virgule flottante dépend du contexte. Étant donné que même changer l'ordre des opérations peut produire des résultats différents, il est important de savoir comment vous voulez que les chiffres soient «égaux».

Comparer des nombres à virgule flottante par Bruce Dawson est un bon endroit pour commencer en regardant la comparaison en virgule flottante.

Les définitions suivantes proviennent de L'art de la programmation informatique par 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);
}

Bien sûr, choisir epsilon dépend du contexte, et détermine à quel point vous voulez que les chiffres soient égaux.

Une autre méthode de comparaison des nombres à virgule flottante consiste à regarder les ULP (unités à la dernière place) des nombres. Bien qu'il ne traite pas spécifiquement des comparaisons, le document Ce que tout informaticien devrait savoir sur les nombres à virgule flottante est une bonne ressource pour comprendre comment fonctionnent les virgules flottantes et quels sont les pièges, y compris ce qu'est l'ULP.


83
2017-10-31 15:13



Pour une approche plus approfondie, lisez Comparer des nombres à virgule flottante. Voici l'extrait de code de ce lien:

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

44
2017-08-20 06:31



La méthode portable pour obtenir epsilon en C ++ est

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

Alors la fonction de comparaison devient

#include <cmath>
#include <limits>

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

25
2017-09-01 09:59



Réaliser que c'est un vieux sujet mais cet article est l'un des plus simples que j'ai trouvé sur la comparaison des nombres à virgule flottante et si vous voulez explorer plus il a aussi des références plus détaillées et le site principal couvre une gamme complète de problèmes traitant des nombres à virgule flottante Le guide en virgule flottante: comparaison.

Nous pouvons trouver un article un peu plus pratique dans Tolérances en virgule flottante revisitées et note il y a tolérance absolue test, qui se résume à ceci en C ++:

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

et tolérance relative tester:

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

L'article note que le test absolu échoue lorsque x et y sont grands et échouent dans le cas relatif quand ils sont petits. En supposant que la tolérance absolue et relative est la même, un test combiné ressemblerait à ceci:

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

23
2018-02-21 21:42



Le code que vous avez écrit est buggé:

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

Le code correct serait:

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

(... et oui c'est différent)

Je me demande si les fabs ne vous feraient pas perdre l'évaluation paresseuse dans certains cas. Je dirais que cela dépend du compilateur. Vous voudrez peut-être essayer les deux. Si elles sont équivalentes en moyenne, prenez la mise en œuvre avec des fabs.

Si vous avez des informations sur lequel des deux flotteurs est le plus susceptible d'être plus grand que les autres, vous pouvez jouer sur l'ordre de la comparaison pour mieux profiter de l'évaluation paresseuse.

Enfin, vous pourriez obtenir un meilleur résultat en insérant cette fonction. Il est peu probable que cela s'améliore beaucoup ...

Edit: JO, merci de corriger votre code. J'ai effacé mon commentaire en conséquence


14
2017-08-20 04:32



`retour fabs (a - b) <EPSILON;

C'est bien si:

  • l'ordre de grandeur de vos entrées ne change pas beaucoup
  • de très petits nombres de signes opposés peuvent être traités comme égaux

Mais sinon, cela vous mènera à des problèmes. Les nombres double précision ont une résolution d'environ 16 décimales. Si les deux nombres que vous comparez ont une magnitude supérieure à EPSILON * 1.0E16, vous pourriez aussi bien dire:

return a==b;

J'examinerai une approche différente qui suppose que vous devez vous inquiéter du premier problème et supposer que le second est bon pour votre application. Une solution serait quelque chose comme:

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

C'est coûteux en informatique, mais c'est parfois ce qui est demandé. C'est ce que nous devons faire dans mon entreprise parce que nous traitons avec une bibliothèque d'ingénierie et que les intrants peuvent varier de quelques dizaines d'ordres de grandeur.

Quoi qu'il en soit, le point est le suivant (et s'applique à pratiquement tous les problèmes de programmation): Évaluer vos besoins, puis trouver une solution pour répondre à vos besoins - ne supposez pas que la réponse facile répondra à vos besoins. Si après votre évaluation, vous trouvez que fabs(a-b) < EPSILON suffira, parfait - utilisez-le! Mais soyez conscient de ses lacunes et d’autres solutions possibles.


14
2017-09-01 08:00



Comme d'autres l'ont souligné, l'utilisation d'un epsilon à exposant fixe (tel que 0.0000001) sera inutile pour les valeurs éloignées de la valeur epsilon. Par exemple, si vos deux valeurs sont 10000.000977 et 10000, il y a NON Les valeurs à virgule flottante de 32 bits entre ces deux nombres - 10000 et 10000.000977 sont aussi proches que vous pouvez éventuellement obtenir sans être identiques pour un bit-à-bit. Ici, un epsilon de moins de 0,0009 est dénué de sens; vous pourriez aussi bien utiliser l'opérateur d'égalité direct.

De même, à mesure que les deux valeurs approchent de la taille d'epsilon, l'erreur relative augmente à 100%.

Ainsi, essayer de mélanger un nombre à virgule fixe tel que 0,00001 avec des valeurs à virgule flottante (où l'exposant est arbitraire) est un exercice inutile. Cela ne fonctionnera que si vous pouvez être assuré que les valeurs de l'opérande se trouvent dans un domaine étroit (c'est-à-dire proche d'un exposant spécifique) et si vous sélectionnez correctement une valeur epsilon pour ce test spécifique. Si vous tirez un numéro hors de l'air ("Hey! 0.00001 est petit, donc ça doit être bon!"), Vous êtes voué à des erreurs numériques. J'ai passé beaucoup de temps à déboguer un mauvais code numérique où un pauvre schmuck lance des valeurs epsilon aléatoires pour faire un autre cas de test.

Si vous faites de la programmation numérique de quelque nature que ce soit et que vous pensez avoir besoin de LIRE L'ARTICLE DE BRUCE SUR LA COMPARAISON DES NOMBRES FLOTTANTS.

Comparaison des nombres à virgule flottante


7
2017-09-12 22:48