On the robustness of the 2Sum and Fast2Sum algorithms

Sylvie Boldo 1 Stef Graillat 2 Jean-Michel Muller 3, 4
1 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
2 PEQUAN - Performance et Qualité des Algorithmes Numériques
LIP6 - Laboratoire d'Informatique de Paris 6
4 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : The 2Sum and Fast2Sum algorithms are important building blocks in numerical computing. They are used (implicitely or explicitely) in many compensated algorithms (such as compensated summation or compensated polynomial evaluation). They are also used for manipulating floating-point expansions. We show that these algorithms are much more robust than it is usually believed: the returned result makes sense even when the rounding function is not round-to-nearest, and they are almost immune to overflow.
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01310023
Contributor : Jean-Michel Muller <>
Submitted on : Wednesday, February 22, 2017 - 9:38:07 AM
Last modification on : Tuesday, May 14, 2019 - 10:06:17 AM
Long-term archiving on : Tuesday, May 23, 2017 - 1:04:40 PM

File

FaithfulTwoSum-Final-Fev2017.p...
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-01310023, version 2

Citation

Sylvie Boldo, Stef Graillat, Jean-Michel Muller. On the robustness of the 2Sum and Fast2Sum algorithms. ACM Transactions on Mathematical Software, Association for Computing Machinery, 2017, 44 (1), ⟨http://dl.acm.org/citation.cfm?id=3054947⟩. ⟨ensl-01310023v2⟩

Share

Metrics

Record views

777

Files downloads

524