On the Robustness of the 2Sum and Fast2Sum Algorithms

被引：14

作者：

Boldo, Sylvie ^{[1
,2
,3
]}

Graillat, Stef ^{[4
]}

Muller, Jean-Michel ^{[5
,6
]}

机构：

[1] Univ Paris Saclay, INRIA, Orsay, France

[2] CNRS, LRI, INRIA, F-91405 Orsay, France

[3] Univ Paris 11, Univ Paris Saclay, Batiment 650, F-91405 Orsay, France

[4] UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, Sorbonne Univ, 4 Pl Jussieu, F-75252 Paris 05, France

[5] Univ Lyon, CNRS, LIP, Lyon, France

[6] Ecole Normale Super Lyon, CNRS, Lab LIP, 46 Allee Italie, F-69364 Lyon 07, France

来源：

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE | 2017年 / 44卷 / 01期

关键词：

Floating-point; error-free transformation; rounding errors; faithful rounding; 2Sum; Fast2Sum; FLOATING-POINT SUMMATION; FAITHFUL;

D O I：

10.1145/3054947

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页数：14

共 20 条

[1]

[Anonymous], 1974, Floating-Point Computation

[2]

[Anonymous], 1965, BIT, DOI DOI 10.1007/BF01975722

[3] Representable correcting terms for possibly underflowing floating point operations [J].

Boldo, S ;

Daumas, M .

16TH IEEE SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 2003, :79-86

[4] FLOATING-POINT TECHNIQUE FOR EXTENDING AVAILABLE PRECISION [J].

DEKKER, TJ .

NUMERISCHE MATHEMATIK, 1971, 18 (03) :224-+

[5] Fast Reproducible Floating-Point Summation [J].

Demmel, James ;

Nguyen, Hong Diep .

2013 21ST IEEE SYMPOSIUM ON COMPUTER ARITHMETIC (ARITH), 2013, :163-172

[6]

Dorel Martin, 2013, BIT, V53, P897

[7] Numerical Validation of Compensated Summation Algorithms with Stochastic Arithmetic [J].

Graillat, S. ;

Jezequel, F. ;

Picot, R. .

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2015, 317 :55-69

[8]

Graillat S., 2009, JAPAN J IND APPL MAT, V26, P2

[9] Handling floating-point exceptions in numeric programs [J].

Hauser, JR .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1996, 18 (02) :139-174

[10] Algorithms for quad-double precision floating point arithmetic [J].

Hida, Y ;

Li, XS ;

Bailey, DH .

ARITH-15 2001: 15TH SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 2001, :155-162

← 1 2 →