Inégalité causée par l'inexactitude du flotteur

15

Au moins en Java, si j'écris ce code:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b + b;
float d = b + b + a;
boolean e = c == d;

la valeur de serait . Je crois que cela est dû au fait que les flotteurs sont très limités dans la manière de représenter avec précision les nombres. Mais je ne comprends pas pourquoi le simple fait de changer la position d' pourrait provoquer cette inégalité.eFunelseune

J'ai réduit les s à un dans les lignes 3 et 4 comme ci-dessous, la valeur de devient cependant :betrue

float a = 1000.0F;
float b = 0.00004F;
float c = a + b;
float d = b + a;
boolean e = c == d;

Que s'est-il passé exactement aux lignes 3 et 4? Pourquoi les opérations d'addition avec des flottants ne sont pas associatives?

Merci d'avance.

Connu Zeta
la source
16
Comme le montre votre exemple, l'addition en virgule flottante est commutative. Mais ce n'est pas associatif.
Yuval Filmus
1
Je vous encourage à rechercher les définitions de base. Notez également que le compilateur analyse comme (l'addition est associée à gauche). ( r + s ) + tr+s+t(r+s)+t
Yuval Filmus
2
Pour un moyen facile de voir pourquoi il devrait en être ainsi, considérez Xun très grand nombre et Yun très petit nombre, tels que X + Y = X. Ici, ce X + Y + -Xsera zéro. Mais le X + -X + Ysera Y.
David Schwartz
1
Pour référence, le canonique: ce que tout informaticien devrait savoir sur l'arithmétique
J ...
1
@J ... et ce que chaque programmeur devrait savoir sur l'arithmétique à virgule flottante .
Gilles 'SO- arrête d'être méchant'

Réponses:

20

Dans les implémentations typiques en virgule flottante, le résultat d'une seule opération est produit comme si l'opération avait été effectuée avec une précision infinie, puis arrondie au nombre à virgule flottante le plus proche.

Comparer et : Le résultat de chaque opération effectuée avec une précision infinie est le même, donc ces résultats de précision infinie identiques sont arrondis de manière identique. En d'autres termes, l'addition en virgule flottante est commutative.b + aune+bb+une

Prenez : est un nombre à virgule flottante. Avec les nombres à virgule flottante binaires , est également un nombre à virgule flottante (l'exposant est plus grand de un), donc est ajouté sans aucune erreur d'arrondi. Ensuite, est ajouté à la valeur exacte . Le résultat est la valeur exacte , arrondie au nombre à virgule flottante le plus proche.b 2 b b + b a b + b 2 b + ab+b+uneb2bb+buneb+b2b+une

Prenez : a + b est ajouté, et il y aura une erreur d'arrondi r , donc nous obtenons le résultat a + b + r . Ajoutez b et le résultat est la valeur exacte 2 b + a + r , arrondie au nombre à virgule flottante le plus proche.une+b+bune+brune+b+rb2b+une+r

Donc dans un cas, , arrondis. Dans l'autre cas, 2 b + a + r , arrondis.2b+une2b+une+r

PS. Que pour deux nombres particuliers et b les deux calculs donnent ou non le même résultat dépend des nombres et de l'erreur d'arrondi dans le calcul a + b , et est généralement difficile à prévoir. L'utilisation de la précision simple ou double ne fait aucune différence en principe avec le problème, mais comme les erreurs d'arrondi sont différentes, il y aura des valeurs de a et b où en précision simple les résultats sont égaux et en double précision ils ne le sont pas, ou vice versa. La précision sera beaucoup plus élevée, mais le problème que deux expressions sont mathématiquement identiques mais pas identiques en arithmétique à virgule flottante reste le même.unebune+b

PPS. Dans certaines langues, l'arithmétique à virgule flottante peut être effectuée avec une précision supérieure ou une plage de nombres supérieure à celle donnée par les instructions réelles. Dans ce cas, il serait beaucoup plus probable (mais toujours pas garanti) que les deux sommes donnent le même résultat.

PPPS. Un commentaire a demandé si nous devrions demander si les nombres à virgule flottante sont égaux ou pas du tout. Absolument si vous savez ce que vous faites. Par exemple, si vous triez un tableau ou implémentez un ensemble, vous vous retrouvez dans de terribles ennuis si vous voulez utiliser une notion "approximativement égale". Dans une interface utilisateur graphique, vous devrez peut-être recalculer la taille des objets si la taille d'un objet a changé - vous comparez oldSize == newSize pour éviter ce recalcul, sachant qu'en pratique vous n'avez presque jamais de tailles presque identiques et que votre programme est correct même s'il y a un recalcul inutile.

gnasher729
la source
Dans ce cas particulier, b devient périodique lorsqu'il est converti en binaire, il y a donc partout des erreurs d'arrondi.
André Souza Lemos
1
@ AndréSouzaLemos bdans cette réponse n'est pas 0,00004, c'est ce que vous obtenez après la conversion et l'arrondi.
Alexey Romanov
"Dans les implémentations typiques en virgule flottante, le résultat d'une seule opération est produit comme si l'opération était effectuée avec une précision infinie, puis arrondie au nombre à virgule flottante le plus proche." - qui est en fait mandaté par la spécification, à ma grande consternation quand j'ai essayé de l'implémenter en termes de portes logiques (le simulateur ne pouvait gérer que les bus 64 bits).
John Dvorak
Question naïve: est-ce que tester l'égalité des flottants a toujours un sens? Pourquoi la plupart des langages de programmation permettent-ils de tester aa == b lorsque les deux ou un est un flottant?
curious_cat
Définition pertinente de Wikipedia: " Machine Epsilon donne une limite supérieure sur l'erreur relative due à l'arrondi dans l'arithmétique à virgule flottante."
Blackhawk
5

Le format binaire à virgule flottante pris en charge par les ordinateurs est essentiellement similaire à la notation scientifique décimale utilisée par les humains.

Un nombre à virgule flottante se compose d'un signe, d'une mantisse (largeur fixe) et d'un exposant (largeur fixe), comme ceci:

+/-  1.0101010101 × 2^12345
sign   ^mantissa^     ^exp^

La notation scientifique régulière a un format similaire:

+/- 1.23456 × 10^99

Si nous faisons de l'arithmétique en notation scientifique avec une précision finie, en arrondissant après chaque opération, alors nous obtenons tous les mêmes mauvais effets que la virgule flottante binaire.


Exemple

Pour illustrer, supposons que nous utilisons exactement 3 chiffres après le point décimal.

a = 99990 = 9.999 × 10^4
b =     3 = 3.000 × 10^0

(a + b) + b

Maintenant, nous calculons:

c = a + b
  = 99990 + 3      (exact)
  = 99993          (exact)
  = 9.9993 × 10^4  (exact)
  = 9.999 × 10^4.  (rounded to nearest)

À l'étape suivante, bien sûr:

d = c + b
  = 99990 + 3 = ...
  = 9.999 × 10^4.  (rounded to nearest)

Donc (a + b) + b = 9,999 × 10 4 .

(b + b) + a

Mais si nous faisions les opérations dans un ordre différent:

e = b + b
  = 3 + 3  (exact)
  = 6      (exact)
  = 6.000 × 10^0.  (rounded to nearest)

Ensuite, nous calculons:

f = e + a
  = 6 + 99990      (exact)
  = 99996          (exact)
  = 9.9996 × 10^4  (exact)
  = 1.000 × 10^5.  (rounded to nearest)

Donc (b + b) + a = 1.000 × 10 5 , ce qui est différent de notre autre réponse.

Nayuki
la source
5

Java utilise la représentation en virgule flottante binaire IEEE 754, qui consacre 23 chiffres binaires à la mantisse, qui est normalisée pour commencer par le premier chiffre significatif (omis, pour économiser de l'espace).

0,00004dix=0.00000000000000101001111100010110101100010001110001101101000111 ...2=[1.]01001111100010110101100010001110001101101000111 ...2×2-15

1000dix+0,00004dix=1111101000.00000000000000101001111100010110101100010001110001101101000111 ...2=[1.]11110100000000000000000101001111100010110101100010001110001101101000111 ...2×29

Les parties en rouge sont les mantisses, telles qu'elles sont réellement représentées (avant arrondi).

(1000dix+0,00004dix)+0,00004dix(0,00004dix+0,00004dix)+1000dix

André Souza Lemos
la source
0

Nous avons récemment rencontré un problème d'arrondi similaire. Les réponses mentionnées ci-dessus sont correctes, mais assez techniques.

J'ai trouvé ce qui suit être une bonne explication de la raison pour laquelle les erreurs d'arrondi existent. http://csharpindepth.com/Articles/General/FloatingPoint.aspx

TLDR: les virgules flottantes binaires ne peuvent pas être mappées avec précision en virgule flottante décimale. Cela provoque des inexactitudes qui peuvent s'aggraver lors des opérations mathématiques.

Un exemple utilisant des nombres flottants décimaux: 1/3 + 1/3 + 1/3 serait normalement égal à 1. Cependant, en décimales: 0,333333 + 0,333333 + 0,333333 n'est jamais exactement égal à 1,000000

La même chose se produit lorsque vous effectuez des opérations mathématiques sur des décimales binaires.

Freek Sanders
la source