Comment puis-je additionner des flotteurs dans des ordres différents, et obtenir toujours le même total ?

Question

Disons que j'ai trois valeurs à virgule flottante de 32 bits, a , b y c de telle sorte que (a + b) + c != a + (b + c) . Existe-t-il un algorithme de sommation, peut-être similaire à Résumé de Kahan qui garantit que ces valeurs peuvent être additionnées dans n'importe quel ordre et que l'on arrive toujours au même total (assez précis) ? Je cherche le cas général (c'est-à-dire pas une solution qui ne traite que 3 nombres).

L'arithmétique de précision arbitraire est-elle la seule voie possible ? Je travaille avec de très grands ensembles de données, et j'aimerais donc éviter si possible les frais généraux liés à l'utilisation de l'arithmétique de précision arbitraire.

Gracias.

Answer 1

Il existe un algorithme intéressant de "sommation de précision complète". ici qui garantit que la somme finale est indépendante de l'ordre des sommets (recette donnée en Python ; mais il ne devrait pas être trop difficile de la traduire dans d'autres langues). Notez que la recette telle qu'elle est donnée dans ce lien n'est pas parfaitement correcte : la boucle d'accumulation principale est correcte, mais dans l'étape finale qui convertit la liste des sommes partielles accumulées en un seul résultat en virgule flottante (la toute dernière ligne de l'instruction msum recette), il faut être un peu plus prudent que de simplement additionner les sommes partielles afin d'obtenir un résultat correctement arrondi. Voir les commentaires sous la recette, et l'implémentation de Python (liée ci-dessous) pour une façon de résoudre ce problème.

Il fait utilise une forme d'arithmétique de précision arbitraire pour tenir les sommes partielles (les sommes intermédiaires sont représentées comme des sommes de doubles "non chevauchantes"), mais peut néanmoins être assez rapide, surtout lorsque toutes les entrées sont à peu près de la même grandeur. Et il donne toujours un résultat correctement arrondi, donc la précision est aussi bonne que vous pouvez l'espérer et la somme finale est indépendante de l'ordre des sommes. Il est basé sur cet article (Arithmétique en virgule flottante à précision adaptative et prédicats géométriques rapides et robustes) par Jonathan Shewchuk.

Python utilise cet algorithme pour son implémentation de math.fsum, qui effectue une sommation indépendante de l'ordre correctement arrondie ; vous pouvez voir l'implémentation C que Python utilise ici --- cherchez la fonction math_fsum.

Answer 2

Avec quelques informations supplémentaires sur les termes que vous devez additionner, vous pouvez éviter la surcharge de l'algorithme de Shewchuk.

Dans l'arithmétique IEEE 754, x-y est exacte chaque fois que y/2 <= x <= 2*y (Théorème de Sterbenz, formellement prouvé ici )

Donc, si vous pouvez arranger tous vos termes dans un ordre tel que chaque somme partielle est de la forme ci-dessus, alors vous obtenez le résultat exact gratuitement.

Je crains qu'en pratique, il y ait peu de chances de se trouver dans des conditions où cela est assuré de se produire. L'alternance de nombres positifs et négatifs de magnitudes croissantes peut être un cas où cela se produit.

Note : la question initiale portait sur un algorithme qui donnerait le même résultat quel que soit l'ordre de la sommation. La réponse de Mark a initié une dérive dans la direction d'un "algorithme exact", mais en relisant votre question, j'ai peur de pousser les choses trop loin en suggérant de réordonner les termes. Vous ne pouvez probablement pas dans ce que vous essayez de faire, et ma réponse est probablement hors-sujet. Eh bien, désolé :)

Answer 3

Je ne suis pas tout à fait sûr que (a + b) + c != a + (b + c) lorsqu'on fait de l'arithmétique dans un programme.

Cependant, la règle empirique pour l'utilisation de l'arithmétique à virgule flottante sur le matériel actuel est de ne jamais tester directement l'égalité.

Quelle que soit l'application que vous avez, vous devez choisir un epsilon suffisamment petit et utiliser

(abs(a - b) < epsilon)

comme test d'égalité.