Comparez le double à zéro avec epsilon

214

Aujourd'hui, je regardais du code C ++ (écrit par quelqu'un d'autre) et j'ai trouvé cette section:

double someValue = ...
if (someValue <  std::numeric_limits<double>::epsilon() && 
    someValue > -std::numeric_limits<double>::epsilon()) {
  someValue = 0.0;
}

J'essaie de comprendre si cela a du sens.

La documentation de epsilon()dit:

La fonction renvoie la différence entre 1 et la plus petite valeur supérieure à 1 qui est représentable [par un double].

Cela s'applique-t-il également à 0, c'est epsilon()-à- dire que la plus petite valeur est supérieure à 0? Ou y a-t-il des nombres entre 0et 0 + epsilonqui peuvent être représentés par un double?

Sinon, la comparaison n'est-elle pas équivalente someValue == 0.0?

Sebastian Krysmanski
la source
3
Le epsilon autour de 1 sera probablement beaucoup plus élevé que celui autour de 0, donc il y aura probablement des valeurs entre 0 et 0 + epsilon_at_1. Je suppose que l'auteur de cette section voulait utiliser quelque chose de petit, mais il ne voulait pas utiliser une constante magique, alors il a juste utilisé cette valeur essentiellement arbitraire.
enobayram
2
La comparaison des nombres à virgule flottante est difficile, et l'utilisation d'Epsilon ou d'une valeur de seuil est même encouragée. Veuillez consulter: cs.princeton.edu/introcs/91float et cygnus-software.com/papers/comparingfloats/comparingfloats.htm
Aditya Kumar Pandey
40
Le premier lien est le 403.99999999
graham.reeds
6
OMI, dans ce cas, l'utilisation de numeric_limits<>::epsilonest trompeuse et non pertinente. Ce que nous voulons, c'est supposer 0 si la valeur réelle ne diffère pas de plus de quelques ε de 0. Et ε doit être choisi en fonction de la spécification du problème, et non en fonction d'une valeur dépendante de la machine. Je soupçonne que l'epsilon actuel est inutile, car même quelques opérations de FP peuvent accumuler une erreur supérieure à cela.
Andrey Vihrov
1
+1. epsilon n'est pas le plus petit possible mais peut servir l'objectif donné dans la plupart des tâches d'ingénierie pratiques si vous savez de quelle précision vous avez besoin et ce que vous faites.
SChepurin

Réponses:

192

En supposant un double IEEE 64 bits, il y a une mantisse 52 bits et un exposant 11 bits. Brisons-le en morceaux:

1.0000 00000000 00000000 00000000 00000000 00000000 00000000 × 2^0 = 1

Le plus petit nombre représentable supérieur à 1:

1.0000 00000000 00000000 00000000 00000000 00000000 00000001 × 2^0 = 1 + 2^-52

Par conséquent:

epsilon = (1 + 2^-52) - 1 = 2^-52

Y a-t-il des nombres entre 0 et epsilon? Beaucoup ... Par exemple, le nombre minimal représentable positif (normal) est:

1.0000 00000000 00000000 00000000 00000000 00000000 00000000 × 2^-1022 = 2^-1022

En fait, il y a des (1022 - 52 + 1)×2^52 = 4372995238176751616nombres entre 0 et epsilon, ce qui représente 47% de tous les nombres positifs représentables ...

Yakov Galka
la source
27
Tellement bizarre que vous pouvez dire "47% des nombres positifs" :)
configurateur
13
@configurator: Non, vous ne pouvez pas dire cela (aucune mesure finie "naturelle" n'existe). Mais vous pouvez dire "47% des nombres représentables positifs ".
Yakov Galka
1
@ybungalobill Je ne peux pas le comprendre. L'exposant a 11 bits: 1 bit de signe et 10 bits de valeur. Pourquoi 2 ^ -1022 et non 2 ^ -1024 est le plus petit nombre positif?
Pavlo Dyban
3
@PavloDyban: tout simplement parce que les exposants n'ont pas de bit de signe. Ils sont codés comme des décalages: si l'exposant codé est 0 <= e < 2048alors la mantisse est multipliée par 2 à la puissance de e - 1023. Par exemple, l'exposant de 2^0est codé comme e=1023, 2^1comme e=1024et 2^-1022comme e=1. La valeur de e=0est réservée aux sous-normales et au zéro réel.
Yakov Galka
2
@PavloDyban: 2^-1022est également le plus petit nombre normal . Le plus petit nombre est en fait 0.0000 00000000 00000000 00000000 00000000 00000000 00000001 × 2^-1022 = 2^-1074. Ceci est subnormal, ce qui signifie que la partie mantisse est inférieure à 1, elle est donc codée avec l'exposant e=0.
Yakov Galka
17

Le test n'est certainement pas le même que someValue == 0. L'idée globale des nombres à virgule flottante est qu'ils stockent un exposant et une signification. Ils représentent donc une valeur avec un certain nombre de chiffres binaires significatifs de précision (53 dans le cas d'un double IEEE). Les valeurs représentables sont beaucoup plus densément emballées près de 0 que près de 1.

Pour utiliser un système décimal plus familier, supposons que vous stockiez une valeur décimale "à 4 chiffres significatifs" avec exposant. Ensuite , la valeur suivante représentable supérieure 1est 1.001 * 10^0et epsilonest 1.000 * 10^-3. Mais 1.000 * 10^-4est également représentable, en supposant que l'exposant peut stocker -4. Vous pouvez me croire sur parole qu'un double IEEE peut stocker moins d'exposants que l'exposant de epsilon.

Vous ne pouvez pas dire à partir de ce code seul s'il est logique ou non d'utiliser epsilonspécifiquement comme limite, vous devez regarder le contexte. Il se peut que ce epsilonsoit une estimation raisonnable de l'erreur dans le calcul qui a produit someValue, et il se peut que ce ne soit pas le cas.

Steve Jessop
la source
2
Bon point, mais même si c'est le cas, une meilleure pratique serait de conserver l'erreur liée dans une variable raisonnablement nommée et de l'utiliser dans la comparaison. En l'état, elle n'est pas différente d'une constante magique.
enobayram
J'aurais peut-être dû être plus clair dans ma question: je ne me suis pas demandé si epsilon était un «seuil» suffisamment grand pour couvrir l'erreur de calcul, mais si cette comparaison est égale someValue == 0.0ou non.
Sebastian Krysmanski
13

Il existe des nombres qui existent entre 0 et epsilon car epsilon est la différence entre 1 et le nombre le plus élevé suivant qui peut être représenté au-dessus de 1 et non la différence entre 0 et le nombre le plus élevé suivant qui peut être représenté au-dessus de 0 (si c'était le cas, cela le code ferait très peu): -

#include <limits>

int main ()
{
  struct Doubles
  {
      double one;
      double epsilon;
      double half_epsilon;
  } values;

  values.one = 1.0;
  values.epsilon = std::numeric_limits<double>::epsilon();
  values.half_epsilon = values.epsilon / 2.0;
}

À l'aide d'un débogueur, arrêtez le programme à la fin de main et regardez les résultats et vous verrez que epsilon / 2 est différent de epsilon, zéro et un.

Cette fonction prend donc des valeurs entre +/- epsilon et les met à zéro.

Skizz
la source
5

Une approximation d'epsilon (plus petite différence possible) autour d'un nombre (1.0, 0.0, ...) peut être imprimée avec le programme suivant. Il imprime la sortie suivante:
epsilon for 0.0 is 4.940656e-324
epsilon for 1.0 is 2.220446e-16
Un peu de réflexion montre clairement que l'epsilon devient plus petit plus le nombre est petit que nous utilisons pour regarder sa valeur epsilon, parce que l'exposant peut s'ajuster à la taille de ce nombre.

#include <stdio.h>
#include <assert.h>
double getEps (double m) {
  double approx=1.0;
  double lastApprox=0.0;
  while (m+approx!=m) {
    lastApprox=approx;
    approx/=2.0;
  }
  assert (lastApprox!=0);
  return lastApprox;
}
int main () {
  printf ("epsilon for 0.0 is %e\n", getEps (0.0));
  printf ("epsilon for 1.0 is %e\n", getEps (1.0));
  return 0;
}
pbhd
la source
2
Quelles implémentations avez-vous vérifiées? Ce n'est certainement pas le cas pour GCC 4.7.
Anton Golov
3

Supposons que nous travaillons avec des nombres à virgule flottante jouets qui tiennent dans un registre de 16 bits. Il y a un bit de signe, un exposant de 5 bits et une mantisse de 10 bits.

La valeur de ce nombre à virgule flottante est la mantisse, interprétée comme une valeur décimale binaire, multipliée par deux à la puissance de l'exposant.

Autour de 1, l'exposant est égal à zéro. Donc, le plus petit chiffre de la mantisse est une partie en 1024.

Près de la moitié de l'exposant est moins un, donc la plus petite partie de la mantisse est deux fois moins grande. Avec un exposant de cinq bits, il peut atteindre un négatif de 16, auquel cas la plus petite partie de la mantisse vaut une partie sur 32 m. Et à un exposant négatif de 16, la valeur est d'environ une partie en 32k, beaucoup plus proche de zéro que l'epsilon autour de celui que nous avons calculé ci-dessus!

Il s'agit maintenant d'un modèle en virgule flottante jouet qui ne reflète pas toutes les bizarreries d'un véritable système à virgule flottante, mais la capacité de refléter des valeurs plus petites que epsilon est raisonnablement similaire avec des valeurs en virgule flottante réelles.

Yakk - Adam Nevraumont
la source
3

La différence entre Xet la valeur suivante de Xvarie selon X.
epsilon()n'est que la différence entre 1et la valeur suivante de 1.
La différence entre 0et la valeur suivante de 0n'est pas epsilon().

Au lieu de cela, vous pouvez utiliser std::nextafterpour comparer une valeur double avec 0comme suit:

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

double someValue = ...
if (same (someValue, 0.0)) {
  someValue = 0.0;
}
Daniel Laügt
la source
2

Je pense que cela dépend de la précision de votre ordinateur. Jetez un oeil sur ce tableau : vous pouvez voir que si votre epsilon est représenté par un double, mais que votre précision est plus élevée, la comparaison n'est pas équivalente à

someValue == 0.0

Bonne question quand même!

Luca Davanzo
la source
2

Vous ne pouvez pas appliquer cela à 0, à cause de la mantisse et des parties exposantes. En raison de l'exposant, vous pouvez stocker de très petits nombres, qui sont plus petits que epsilon, mais lorsque vous essayez de faire quelque chose comme (1.0 - "très petit nombre"), vous obtenez 1.0. Epsilon est un indicateur non pas de valeur, mais de précision de valeur, qui est en mantisse. Il montre combien de chiffres décimaux conséquents corrects de nombre nous pouvons stocker.

Arsenii Fomin
la source
2

Avec la virgule flottante IEEE, entre la plus petite valeur positive non nulle et la plus petite valeur négative non nulle, il existe deux valeurs: zéro positif et zéro négatif. Tester si une valeur se situe entre les plus petites valeurs non nulles équivaut à tester l'égalité avec zéro; l'affectation, cependant, peut avoir un effet, car elle changerait un zéro négatif en un zéro positif.

Il serait concevable qu'un format à virgule flottante puisse avoir trois valeurs entre les plus petites valeurs positives et négatives finies: infinitésimal positif, zéro non signé et infinitésimal négatif. Je ne connais aucun format à virgule flottante qui fonctionne en fait de cette façon, mais un tel comportement serait parfaitement raisonnable et sans doute meilleur que celui de l'IEEE (peut-être pas assez mieux pour valoir la peine d'ajouter du matériel supplémentaire pour le prendre en charge, mais mathématiquement 1 / (1 / INF), 1 / (- 1 / INF) et 1 / (1-1) devraient représenter trois cas distincts illustrant trois zéros différents). Je ne sais pas si une norme C exigerait que les infinitésimaux signés, s'ils existent, devraient se comparer à zéro. Si ce n'est pas le cas, un code comme celui ci-dessus pourrait utilement garantir que, par exemple,

supercat
la source
N'est-ce pas "1 / (1-1)" (d'après votre exemple) l'infini plutôt que zéro?
Sebastian Krysmanski
Les quantités (1-1), (1 / INF) et (-1 / INF) représentent toutes zéro, mais diviser un nombre positif par chacune d'elles devrait en théorie donner trois résultats différents (les calculs IEEE considèrent les deux premiers comme identiques ).
supercat
1

Supposons donc que le système ne puisse pas distinguer 1.000000000000000000000 et 1.000000000000000000001. c'est-à-dire 1.0 et 1.0 + 1e-20. Pensez-vous qu'il existe encore des valeurs pouvant être représentées entre -1e-20 et + 1e-20?

cababunga
la source
Sauf pour zéro, je ne pense pas qu'il y ait des valeurs entre -1e-20 et + 1e-20. Mais juste parce que je pense que cela ne le rend pas vrai.
Sebastian Krysmanski
@SebastianKrysmanski: ce n'est pas vrai, il y a beaucoup de valeurs à virgule flottante entre 0 et epsilon. Parce que c'est une virgule flottante , pas une virgule fixe.
Steve Jessop
La plus petite valeur représentable distincte de zéro est limitée par le nombre de bits alloués pour représenter l'exposant. Donc, si double a un exposant de 11 bits, le plus petit nombre serait 1e-1023.
cababunga
0

De plus, une bonne raison d'avoir une telle fonction est de supprimer les "dénormals" (ces très petits nombres qui ne peuvent plus utiliser le "1" implicite et qui ont une représentation FP spéciale). Pourquoi voudriez-vous faire ça? Parce que certaines machines (en particulier certains Pentium 4 plus anciens) deviennent vraiment, vraiment lentes lors du traitement des dénormals. D'autres deviennent un peu plus lents. Si votre application n'a pas vraiment besoin de ces très petits nombres, les vider à zéro est une bonne solution. Les bons endroits à considérer sont les dernières étapes de tout filtre IIR ou fonction de désintégration.

Voir aussi: Pourquoi le passage de 0,1f à 0 ralentit-il 10 fois les performances?

et http://en.wikipedia.org/wiki/Denormal_number

Dithermaster
la source
1
Cela supprime beaucoup plus de numéros que les seuls numéros dénormalisés. Il change la constante de Planck ou la masse d'un électron à zéro, ce qui vous donnera des résultats très, très mauvais si vous utilisez ces nombres.
gnasher729