Est-il possible d'obtenir 0 en soustrayant deux nombres à virgule flottante inégaux?

Est-il possible d'obtenir une division par 0 (ou l'infini) dans l'exemple suivant?

public double calculation(double a, double b)
{
     if (a == b)
     {
         return 0;
     }
     else
     {
         return 2 / (a - b);
     }
}

Dans des cas normaux, ce ne sera évidemment pas le cas. Mais que se passe-t-il si aet bsont très proches, peuvent (a-b)résulter en une 0précision du calcul?

Notez que cette question concerne Java, mais je pense qu'elle s'appliquera à la plupart des langages de programmation.

En Java, a - bn'est jamais égal à 0if a != b. En effet, Java impose des opérations en virgule flottante IEEE 754 qui prennent en charge les nombres dénormalisés. De la spécification :

En particulier, le langage de programmation Java nécessite la prise en charge des nombres à virgule flottante dénormalisés IEEE 754 et un dépassement progressif, qui facilitent la démonstration des propriétés souhaitables d'algorithmes numériques particuliers. Les opérations à virgule flottante ne «rincent pas à zéro» si le résultat calculé est un nombre dénormalisé.

Si un FPU fonctionne avec des nombres dénormalisés , la soustraction de nombres inégaux ne peut jamais produire zéro (contrairement à la multiplication), voir également cette question .

Pour les autres langues, cela dépend. En C ou C ++, par exemple, la prise en charge IEEE 754 est facultative.

Cela dit, il est possible que l'expression 2 / (a - b)déborde, par exemple avec a = 5e-308et b = 4e-308.

En guise de solution de contournement, qu'en est-il des éléments suivants?

public double calculation(double a, double b) {
     double c = a - b;
     if (c == 0)
     {
         return 0;
     }
     else
     {
         return 2 / c;
     }
}

De cette façon, vous ne dépendez pas du support IEEE dans aucune langue.

Vous n'obtiendrez pas une division par zéro quelle que soit la valeur de a - b , car la division en virgule flottante par 0 ne lève pas d'exception. Il renvoie l'infini.

Maintenant, le seul moyen de a == bretourner vrai est si aetb contient exactement les mêmes bits. S'ils diffèrent uniquement du bit le moins significatif, la différence entre eux ne sera pas de 0.

ÉDITER :

Comme Bathsheba l'a correctement commenté, il y a quelques exceptions:

1. "Pas un nombre ne se compare" false à lui-même mais aura des modèles de bits identiques.

2. -0,0 est défini pour comparer vrai avec +0,0, et leurs modèles de bits sont différents.

Donc, si les deux aet bsont Double.NaN, vous atteindrez la clause else, mais comme NaN - NaNretourne également NaN, vous ne diviserez pas par zéro.

Il n'y a aucun cas où une division par zéro peut se produire ici.

Le SMT Solver Z3 prend en charge l'arithmétique précise à virgule flottante IEEE. Demandons à Z3 de trouver des nombres aet btels que a != b && (a - b) == 0:

(set-info :status unknown)
(set-logic QF_FP)
(declare-fun b () (FloatingPoint 8 24))
(declare-fun a () (FloatingPoint 8 24))
(declare-fun rm () RoundingMode)
(assert
(and (not (fp.eq a b)) (fp.eq (fp.sub rm a b) +zero) true))
(check-sat)

Le résultat est UNSAT. Il n'y a pas de tels chiffres.

La chaîne SMTLIB ci-dessus permet également à Z3 de choisir un mode d'arrondi arbitraire ( rm). Cela signifie que le résultat est valable pour tous les modes d'arrondi possibles (dont il y en a cinq). Le résultat inclut également la possibilité que l'une des variables en jeu soit NaNou l'infini.

a == best mis en œuvre en tant que fp.eqqualité afin que +0fet -0fcomparer égal. La comparaison avec zéro est également implémentée en utilisant fp.eq. Puisque la question vise à éviter une division par zéro, c'est la comparaison appropriée.

Si le test d'égalité avait été implémenté en utilisant l'égalité au niveau du bit, +0fet -0faurait été un moyen de fairea - b zéro. Une version précédente incorrecte de cette réponse contient des détails de mode sur cette affaire pour les curieux.

Z3 Online ne prend pas encore en charge la théorie FPA. Ce résultat a été obtenu en utilisant la dernière branche instable. Il peut être reproduit à l'aide des liaisons .NET comme suit:

var fpSort = context.MkFPSort32();
var aExpr = (FPExpr)context.MkConst("a", fpSort);
var bExpr = (FPExpr)context.MkConst("b", fpSort);
var rmExpr = (FPRMExpr)context.MkConst("rm", context.MkFPRoundingModeSort());
var fpZero = context.MkFP(0f, fpSort);
var subExpr = context.MkFPSub(rmExpr, aExpr, bExpr);
var constraintExpr = context.MkAnd(
        context.MkNot(context.MkFPEq(aExpr, bExpr)),
        context.MkFPEq(subExpr, fpZero),
        context.MkTrue()
    );

var smtlibString = context.BenchmarkToSMTString(null, "QF_FP", null, null, new BoolExpr[0], constraintExpr);

var solver = context.MkSimpleSolver();
solver.Assert(constraintExpr);

var status = solver.Check();
Console.WriteLine(status);

En utilisant Z3 pour répondre aux questions float IEEE est agréable car il est difficile de négliger les cas ( par exemple NaN, -0f, +-inf) et vous pouvez poser des questions arbitraires. Pas besoin d'interpréter et de citer des spécifications. Vous pouvez même poser des questions mixtes flottantes et entières telles que "cet int log2(float)algorithme particulier est-il correct?".

La fonction fournie peut en effet renvoyer l'infini:

public class Test {
    public static double calculation(double a, double b)
    {
         if (a == b)
         {
             return 0;
         }
         else
         {
             return 2 / (a - b);
         }
    }    

    /**
     * @param args
     */
    public static void main(String[] args) {
        double d1 = Double.MIN_VALUE;
        double d2 = 2.0 * Double.MIN_VALUE;
        System.out.println("Result: " + calculation(d1, d2)); 
    }
}

La sortie est Result: -Infinity.

Lorsque le résultat de la division est trop grand pour être stocké dans un double, l'infini est renvoyé même si le dénominateur est différent de zéro.

Dans une implémentation à virgule flottante conforme à IEEE-754, chaque type à virgule flottante peut contenir des nombres dans deux formats. Un ("normalisé") est utilisé pour la plupart des valeurs à virgule flottante, mais le deuxième plus petit nombre qu'il peut représenter n'est qu'un tout petit peu plus grand que le plus petit, et donc la différence entre eux n'est pas représentable dans ce même format. L'autre format («dénormalisé») est utilisé uniquement pour les très petits nombres qui ne sont pas représentables dans le premier format.

Les circuits permettant de gérer efficacement le format à virgule flottante dénormalisé sont coûteux, et tous les processeurs ne l'incluent pas. Certains processeurs offrent un choix entre soit les opérations sur les nombres ayant vraiment petits être beaucoup plus lentes que des opérations sur d'autres valeurs, ou au processeur de considérer simplement les nombres qui sont trop petits pour un format normalisé comme zéro.

Les spécifications Java impliquent que les implémentations devraient prendre en charge le format dénormalisé, même sur les machines où cela ralentirait le code. D'un autre côté, il est possible que certaines implémentations offrent des options pour permettre au code de s'exécuter plus rapidement en échange d'une gestion légèrement bâclée des valeurs qui, dans la plupart des cas, seraient bien trop petites pour avoir de l'importance (dans les cas où les valeurs sont trop petites pour avoir de l'importance, cela peut être ennuyeux d'avoir des calculs avec eux prendre dix fois plus de temps que les calculs qui comptent, donc dans de nombreuses situations pratiques, la mise à zéro est plus utile que l'arithmétique lente mais précise).

Dans les temps anciens avant IEEE 754, il était tout à fait possible que a! = B n'impliquait pas ab! = 0 et vice versa. C'était l'une des raisons pour lesquelles j'ai créé IEEE 754 en premier lieu.

Avec IEEE 754, c'est presque garanti. Les compilateurs C ou C ++ sont autorisés à effectuer une opération avec une précision plus élevée que nécessaire. Donc si a et b ne sont pas des variables mais des expressions, alors (a + b)! = C n'implique pas (a + b) - c! = 0, car a + b pourrait être calculé une fois avec une précision plus élevée, et une fois sans précision supérieure.

De nombreux FPU peuvent être basculés vers un mode où ils ne renvoient pas de nombres dénormalisés mais les remplacent par 0. Dans ce mode, si a et b sont de minuscules nombres normalisés où la différence est inférieure au plus petit nombre normalisé mais supérieure à 0, a ! = b ne garantit pas non plus a == b.

"Ne jamais comparer les nombres à virgule flottante" est une programmation culte du fret. Parmi les personnes qui ont le mantra "vous avez besoin d'un epsilon", la plupart n'ont aucune idée de comment choisir correctement cet epsilon.

Je peux penser à un cas où vous pourriez être en mesure de provoquer cela. Voici un exemple analogue en base 10 - vraiment, cela se produirait en base 2, bien sûr.

Les nombres à virgule flottante sont stockés plus ou moins en notation scientifique - c'est-à-dire qu'au lieu de voir 35,2, le nombre stocké ressemblerait plus à 3,52e2.

Imaginez pour des raisons de commodité que nous ayons une unité à virgule flottante qui fonctionne en base 10 et a 3 chiffres de précision. Que se passe-t-il lorsque vous soustrayez 9,99 de 10,0?

1,00e2-9,99e1

Shift pour donner à chaque valeur le même exposant

1,00e2-0,999e2

Arrondir à 3 chiffres

1,00e2-1,00e2

Oh oh!

La question de savoir si cela peut arriver dépend de la conception du FPU. Comme la plage d'exposants pour un double est très grande, le matériel doit s'arrondir en interne à un moment donné, mais dans le cas ci-dessus, un seul chiffre supplémentaire en interne évitera tout problème.

Vous ne devriez jamais comparer des flottants ou des doubles pour l'égalité; car, vous ne pouvez pas vraiment garantir que le nombre que vous attribuez au float ou au double est exact.

Pour comparer correctement les flottants pour l'égalité, vous devez vérifier si la valeur est "suffisamment proche" de la même valeur:

if ((first >= second - error) || (first <= second + error)

La division par zéro n'est pas définie, puisque la limite des nombres positifs tend vers l'infini, les limites des nombres négatifs tendent vers l'infini négatif.

Je ne sais pas s'il s'agit de C ++ ou de Java car il n'y a pas de balise de langue.

double calculation(double a, double b)
{
     if (a == b)
     {
         return nan(""); // C++

         return Double.NaN; // Java
     }
     else
     {
         return 2 / (a - b);
     }
}

Le problème principal est que la représentation informatique d'un double (aka float, ou nombre réel en langage mathématique) est fausse lorsque vous avez "trop" de décimales, par exemple lorsque vous traitez avec un double qui ne peut pas être écrit sous forme de valeur numérique ( pi ou le résultat de 1/3).

Donc a == b ne peut pas être fait avec une valeur double de a et b, comment gérer a == b quand a = 0,333 et b = 1/3? En fonction de votre système d'exploitation vs FPU vs nombre vs langue par rapport au nombre de 3 après 0, vous aurez vrai ou faux.

Quoi qu'il en soit, si vous faites un "calcul à double valeur" sur un ordinateur, vous devez gérer la précision, donc au lieu de le faire a==b, vous devez le faire absolute_value(a-b)<epsilon, et epsilon est relatif à ce que vous modélisez à ce moment-là dans votre algorithme. Vous ne pouvez pas avoir de valeur epsilon pour l'ensemble de votre double comparaison.

En bref, lorsque vous tapez a == b, vous avez une expression mathématique qui ne peut pas être traduite sur un ordinateur (pour tout nombre à virgule flottante).

PS: hum, tout ce que je réponds ici est encore plus ou moins dans les réponses et commentaires des autres.

Sur la base de la réponse de @malarres et du commentaire de @Taemyr, voici ma petite contribution:

public double calculation(double a, double b)
{
     double c = 2 / (a - b);

     // Should not have a big cost.
     if (isnan(c) || isinf(c))
     {
         return 0; // A 'whatever' value.
     }
     else
     {
         return c;
     }
}

Mon point est de dire: le moyen le plus simple de savoir si le résultat de la division est nan ou inf est en fait d'effectuer la division.