On the robustness of the 2Sum and Fast2Sum algorithms

Sylvie Boldo 1 Stef Graillat 2 Jean-Michel Muller 3, 4
1 TOCCATA - Formally Verified Programs, Certified Tools and Numerical Computations
LRI - Laboratoire de Recherche en Informatique, Inria Saclay - Ile de France
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 : Thursday, October 3, 2019 - 2:04:03 PM
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). ⟨ensl-01310023v2⟩

Share

Metrics

Record views

826

Files downloads

617