Accurate calculation of Euclidean Norms using Double-word arithmetic

We consider the computation of the Euclidean (or L2) norm of an n-dimensional vector in floating-point arithmetic. We review the classical solutions used to avoid spurious overflow or underflow and/or to obtain very accurate results. We modify a recently published algorithm (that uses double-word arithmetic) to allow for a very accurate solution, free of spurious overflows and underflows. To that purpose, we use a double-word square-root algorithm of which we provide a tight error analysis. The returned L2 norm will be within very slightly more than 0.5 ulp from the exact result, which means that we will almost always provide correct rounding.

Mots clés

Overflow Underflow Square-root Formalization Proof assistant Coq Floating-Point arithmetic Euclidean norms Double-word arithmetic Double-double arithmetic

Domaines

Autre [cs.OH] Arithmétique des ordinateurs Logiciel mathématique [cs.MS]

Fichier principal

NormsandDW HaLV2.pdf (771.99 Ko)

C_and_Julia.zip (126.7 Ko)

en_sqrt_dw_coq.tar.gz (145.81 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

Jean-Michel Muller : Connectez-vous pour contacter le contributeur

https://hal.science/hal-03482567

Soumis le : vendredi 7 octobre 2022-13:46:42

Dernière modification le : mercredi 9 août 2023-20:17:36

Dates et versions

hal-03482567 , version 1 (16-12-2021)

hal-03482567 , version 2 (07-10-2022)

Licence

Paternité

Identifiants

HAL Id : hal-03482567 , version 2
DOI : 10.1145/3568672

Citer

Vincent Lefèvre, Nicolas Louvet, Jean-Michel Muller, Joris Picot, Laurence Rideau. Accurate calculation of Euclidean Norms using Double-word arithmetic. ACM Transactions on Mathematical Software, 2023, 49 (1), pp.1-34. ⟨10.1145/3568672⟩. ⟨hal-03482567v2⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

ENS-LYON CNRS INRIA UNIV-LYON1 INRIA2 UNIV-COTEDAZUR UDL ANR

446 Consultations

496 Téléchargements