Pourquoi la modification de l'ordre de somme renvoie-t-elle un résultat différent?

Pourquoi la modification de l'ordre de somme renvoie-t-elle un résultat différent?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

Les deux Java et JavaScript renvoient les mêmes résultats.

Je comprends que, en raison de la façon dont les nombres à virgule flottante sont représentés en binaire, certains nombres rationnels ( comme 1/3 - 0,333333 ... ) ne peuvent pas être représentés avec précision.

Pourquoi le simple changement de l'ordre des éléments affecte-t-il le résultat?

Peut-être que cette question est stupide, mais pourquoi le simple fait de changer l'ordre des éléments affecte-t-il le résultat?

Il changera les points auxquels les valeurs sont arrondies, en fonction de leur ampleur. Comme exemple du genre de chose que nous voyons, supposons qu'au lieu de virgule flottante binaire, nous utilisions un type décimal à virgule flottante avec 4 chiffres significatifs, où chaque ajout est effectué avec une précision "infinie", puis arrondi à le nombre représentable le plus proche. Voici deux sommes:

1/3 + 2/3 + 2/3 = (0.3333 + 0.6667) + 0.6667
                = 1.000 + 0.6667 (no rounding needed!)
                = 1.667 (where 1.6667 is rounded to 1.667)

2/3 + 2/3 + 1/3 = (0.6667 + 0.6667) + 0.3333
                = 1.333 + 0.3333 (where 1.3334 is rounded to 1.333)
                = 1.666 (where 1.6663 is rounded to 1.666)

Nous n'avons même pas besoin de non-entiers pour que ce soit un problème:

10000 + 1 - 10000 = (10000 + 1) - 10000
                  = 10000 - 10000 (where 10001 is rounded to 10000)
                  = 0

10000 - 10000 + 1 = (10000 - 10000) + 1
                  = 0 + 1
                  = 1

Cela démontre peut-être plus clairement que la partie importante est que nous avons un nombre limité de chiffres significatifs - pas un nombre limité de décimales . Si nous pouvions toujours garder le même nombre de décimales, alors avec l'addition et la soustraction au moins, nous irions bien (tant que les valeurs ne débordaient pas). Le problème est que lorsque vous obtenez de plus grands nombres, des informations plus petites sont perdues - le 10001 étant arrondi à 10000 dans ce cas. (Ceci est un exemple du problème que Eric Lippert a noté dans sa réponse .)

Il est important de noter que les valeurs sur la première ligne du côté droit sont les mêmes dans tous les cas - donc bien qu'il soit important de comprendre que vos nombres décimaux (23,53, 5,88, 17,64) ne seront pas représentés exactement comme des doublevaleurs, c'est seulement un problème en raison des problèmes ci-dessus.

Voici ce qui se passe en binaire. Comme nous le savons, certaines valeurs à virgule flottante ne peuvent pas être représentées exactement en binaire, même si elles peuvent être représentées exactement en décimal. Ces 3 chiffres ne sont que des exemples de ce fait.

Avec ce programme, je produis les représentations hexadécimales de chaque nombre et les résultats de chaque addition.

public class Main{
   public static void main(String args[]) {
      double x = 23.53;   // Inexact representation
      double y = 5.88;    // Inexact representation
      double z = 17.64;   // Inexact representation
      double s = 47.05;   // What math tells us the sum should be; still inexact

      printValueAndInHex(x);
      printValueAndInHex(y);
      printValueAndInHex(z);
      printValueAndInHex(s);

      System.out.println("--------");

      double t1 = x + y;
      printValueAndInHex(t1);
      t1 = t1 + z;
      printValueAndInHex(t1);

      System.out.println("--------");

      double t2 = x + z;
      printValueAndInHex(t2);
      t2 = t2 + y;
      printValueAndInHex(t2);
   }

   private static void printValueAndInHex(double d)
   {
      System.out.println(Long.toHexString(Double.doubleToLongBits(d)) + ": " + d);
   }
}

le printValueAndInHex méthode est juste une aide d'imprimante hexadécimale.

La sortie est la suivante:

403787ae147ae148: 23.53
4017851eb851eb85: 5.88
4031a3d70a3d70a4: 17.64
4047866666666666: 47.05
--------
403d68f5c28f5c29: 29.41
4047866666666666: 47.05
--------
404495c28f5c28f6: 41.17
4047866666666667: 47.050000000000004

Les 4 premiers chiffres sont x, y, zet sde » représentations hexadécimaux. Dans la représentation en virgule flottante IEEE, les bits 2 à 12 représentent l' exposant binaire , c'est-à-dire l'échelle du nombre. (Le premier bit est le bit de signe, et les bits restants pour la mantisse .) L'exposant représenté est en fait le nombre binaire moins 1023.

Les exposants des 4 premiers nombres sont extraits:

    sign|exponent
403 => 0|100 0000 0011| => 1027 - 1023 = 4
401 => 0|100 0000 0001| => 1025 - 1023 = 2
403 => 0|100 0000 0011| => 1027 - 1023 = 4
404 => 0|100 0000 0100| => 1028 - 1023 = 5

Première série d'ajouts

Le deuxième nombre ( y) est de plus petite ampleur. Lors de l'ajout de ces deux nombres à obtenir x + y, les 2 derniers bits du deuxième nombre ( 01) sont décalés hors de la plage et ne figurent pas dans le calcul.

Le deuxième ajout ajoute x + yet zajoute deux nombres de la même échelle.

Deuxième série d'ajouts

Ici, x + zse produit en premier. Ils sont de la même échelle, mais ils donnent un nombre plus élevé dans l'échelle:

404 => 0|100 0000 0100| => 1028 - 1023 = 5

Le deuxième ajout ajoute x + zet y, et maintenant 3 bits sont supprimés ypour ajouter les nombres ( 101). Ici, il doit y avoir un arrondi vers le haut, car le résultat est le prochain nombre à virgule flottante vers le haut: 4047866666666666pour le premier ensemble d'additions par rapport à4047866666666667 au deuxième ensemble d'additions. Cette erreur est suffisamment importante pour apparaître dans l'impression du total.

En conclusion, soyez prudent lorsque vous effectuez des opérations mathématiques sur des nombres IEEE. Certaines représentations sont inexactes, et elles deviennent encore plus inexactes lorsque les échelles sont différentes. Ajoutez et soustrayez des nombres d'échelle similaire si vous le pouvez.

La réponse de Jon est bien sûr correcte. Dans votre cas, l'erreur n'est pas plus grande que l'erreur que vous accumulez en effectuant une simple opération à virgule flottante. Vous avez un scénario où, dans un cas, vous obtenez zéro erreur et dans un autre, vous obtenez une petite erreur; ce n'est pas vraiment un scénario intéressant. Une bonne question est: y a-t-il des scénarios où le changement de l'ordre des calculs passe d'une petite erreur à une erreur (relativement) énorme? La réponse est sans ambiguïté oui.

Considérez par exemple:

x1 = (a - b) + (c - d) + (e - f) + (g - h);

contre

x2 = (a + c + e + g) - (b + d + f + h);

contre

x3 = a - b + c - d + e - f + g - h;

De toute évidence, en arithmétique exacte, ils seraient les mêmes. Il est amusant d'essayer de trouver des valeurs pour a, b, c, d, e, f, g, h telles que les valeurs de x1 et x2 et x3 diffèrent considérablement. Voyez si vous pouvez le faire!

Cela couvre en réalité bien plus que Java et Javascript, et affecterait probablement tout langage de programmation utilisant des flottants ou des doubles.

En mémoire, les virgules flottantes utilisent un format spécial du type IEEE 754 (le convertisseur fournit une bien meilleure explication que moi).

Quoi qu'il en soit, voici le convertisseur flottant.

http://www.h-schmidt.net/FloatConverter/

La chose à propos de l'ordre des opérations est la «finesse» de l'opération.

Votre première ligne donne 29,41 à partir des deux premières valeurs, ce qui nous donne 2 ^ 4 comme exposant.

Votre deuxième ligne donne 41,17, ce qui nous donne 2 ^ 5 comme exposant.

Nous perdons un chiffre significatif en augmentant l'exposant, ce qui est susceptible de changer le résultat.

Essayez de cocher et de désactiver le dernier bit à l'extrême droite pour 41.17 et vous pouvez voir que quelque chose d'aussi "insignifiant" que 1/2/23 de l'exposant serait suffisant pour provoquer cette différence de virgule flottante.

Edit: Pour ceux d'entre vous qui se souviennent de chiffres importants, cela tomberait dans cette catégorie. 10 ^ 4 + 4999 avec un chiffre significatif de 1 va être 10 ^ 4. Dans ce cas, le chiffre significatif est beaucoup plus petit, mais nous pouvons voir les résultats avec le .00000000004 attaché.

Les nombres à virgule flottante sont représentés au format IEEE 754, qui fournit une taille spécifique de bits pour la mantisse (significande). Malheureusement, cela vous donne un nombre spécifique de «blocs de construction fractionnaires» avec lesquels jouer, et certaines valeurs fractionnaires ne peuvent pas être représentées avec précision.

Ce qui se passe dans votre cas, c'est que dans le second cas, l'ajout rencontre probablement un problème de précision en raison de l'ordre dans lequel les ajouts sont évalués. Je n'ai pas calculé les valeurs, mais il se pourrait par exemple que 23,53 + 17,64 ne puissent pas être représentés avec précision, tandis que 23,53 + 5,88 le peuvent.

Malheureusement, c'est un problème connu que vous n'avez qu'à régler.

Je crois que cela a à voir avec l'ordre de l'évaluation. Alors que la somme est naturellement la même dans un monde mathématique, dans le monde binaire au lieu de A + B + C = D, c'est

A + B = E
E + C = D(1)

Il y a donc cette étape secondaire où les nombres à virgule flottante peuvent descendre.

Lorsque vous modifiez la commande,

A + C = F
F + B = D(2)