Quel est le moyen le plus efficace pour le flottement et la double comparaison? [c++]


Answers

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 de super informations sur ce sujet sur un blog récent . Prendre plaisir.

Question

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

Simplement faire 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?




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

Comparer les nombres à virgule flottante par Bruce Dawson est un bon point de départ pour la comparaison à virgule flottante.

Les définitions suivantes proviennent de L'art de la programmation informatique de 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, l'article Ce que tout informaticien devrait savoir sur les nombres à virgule flottante est une bonne ressource pour comprendre comment fonctionne le calcul à virgule flottante et quels sont les pièges, y compris ce qu'est l'ULP.




La manière portable d'obtenir epsilon en C ++ est

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

Ensuite, 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();
}



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 pourriez vouloir 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. Peu susceptible d'améliorer beaucoup si ...

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




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 n'y a pas de valeurs à virgule flottante NO 32 bits entre ces deux nombres - 10000 et 10000.000977 sont aussi proches que possible 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, lorsque les deux valeurs s'approchent 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 jamais que si vous pouvez être assuré que les valeurs d'opérande se trouvent dans un domaine étroit (c'est-à-dire près 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 croyez avoir besoin d'atteindre des epsilons à virgule fixe, LIRE L'ARTICLE DE BRUCE SUR LA COMPARAISON DES NUMÉROS DE POINTS FLOTTANTS .

Comparaison des nombres à virgule flottante




J'ai passé beaucoup de temps à passer en revue ce sujet. Je doute que tout le monde veuille passer autant de temps, alors je voudrais souligner le résumé de ce que j'ai appris et la solution que j'ai mise en place.

Résumé rapide

  1. Il y a deux problèmes avec float compare: vous avez une précision limitée et la signification de "approximativement zéro" dépend du contexte (voir point suivant).
  2. Est-ce que 1E-8 est à peu près le même que 1E-16? Si vous regardez des données de capteur bruyantes, alors oui, mais si vous faites de la simulation moléculaire, alors peut-être pas! Bottom line: Vous avez toujours besoin de penser à la valeur de la tolérance dans le contexte de l'appel de fonction spécifique et ne pas faire que la constante codée en dur de l'application générique.
  3. Pour les fonctions générales de la bibliothèque, il est toujours agréable d'avoir un paramètre avec tolérance par défaut . Un choix typique est numeric_limits::epsilon() qui est le même que FLT_EPSILON dans float.h. Ceci est cependant problématique car epsilon pour comparer des valeurs comme 1.0 sinon même comme epsilon pour des valeurs comme 1E9. Le FLT_EPSILON est défini pour 1.0.
  4. L'implémentation évidente pour vérifier si le nombre est dans la tolérance est fabs(ab) <= epsilon cependant ceci ne fonctionne pas parce que epsilon par défaut est défini pour 1.0. Nous devons augmenter ou diminuer epsilon en termes de a et b.
  5. Il existe deux solutions à ce problème: soit vous définissez epsilon proportionnellement à max(a,b) soit vous pouvez obtenir les nombres représentables suivants autour de a et ensuite voir si b tombe dans cette plage. Le premier est appelé méthode "relative" et est appelé plus tard la méthode ULP.
  6. Les deux méthodes échouent quand même en comparaison avec 0. Dans ce cas, l'application doit fournir une tolérance correcte.

Implémentation des fonctions utilitaires (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;
}



Ma classe en fonction des réponses précédemment affiché. Très similaire au code de Google mais j'utilise un biais qui pousse toutes les valeurs NaN ci-dessus 0xFF000000. Cela permet un contrôle plus rapide pour NaN.

Ce code vise à démontrer le concept, pas une solution générale. Le code de Google montre déjà comment calculer toutes les valeurs spécifiques de la plate-forme et je ne voulais pas reproduire tout cela. Je l'ai fait des essais limités sur ce code.

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



Il y a effectivement des cas dans le logiciel numérique où vous voulez vérifier si deux nombres à virgule flottante sont exactement égales. Je posté sur une question similaire

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

Donc, vous ne pouvez pas dire que « CompareDoubles1 » est mal en général.




En ce qui concerne l'échelle des quantités:

Si epsilonest la petite fraction de la grandeur de la quantité (ie valeur relative) dans une certain sens physique et Aet Btypes est comparable dans le même sens, que je pense que ce qui suit est tout à fait correct:

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



J'utilise ce code:

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



Vous ne pouvez pas comparer deux doubleavec un fixe EPSILON. En fonction de la valeur double, EPSILONvarie.

Une meilleure double comparaison serait:

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



Pourquoi ne pas effectuer XOR au niveau du bit? Deux nombres à virgule flottante sont égaux si leurs bits correspondants sont égaux. Je pense que la décision de placer les bits d'exposant avant mantisse a été fait pour accélérer la comparaison des deux flotteurs. Je pense, beaucoup de réponses ici manquent le point de comparaison epsilon. Epsilon valeur ne dépend que de ce nombre à virgule flottante de précision sont comparés. Par exemple, après avoir fait un peu d'arithmétique avec des flotteurs vous obtenez deux numéros: 2,5642943554342 et 2,5642943554345. Ils ne sont pas égaux, mais pour la solution seulement 3 chiffres décimaux d'importance si elles sont égales: 2,564 et 2,564. Dans ce cas, vous choisissez epsilon égal à 0,001. comparaison de Epsilon est également possible avec XOR au niveau du bit. Corrigez-moi si je me trompe.