TY - JOUR

T1 - A note on Dekker’s FastTwoSum algorithm

AU - Lange, Marko

AU - Oishi, Shin’ichi

N1 - Funding Information:
This research was partially supported by CREST, Japan Science and Technology Agency (JST)
Publisher Copyright:
© 2020, Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2020/6/1

Y1 - 2020/6/1

N2 - More than 45 years ago, Dekker proved that it is possible to evaluate the exact error of a floating-point sum with only two additional floating-point operations, provided certain conditions are met. Today the respective algorithm for transforming a sum into its floating-point approximation and the corresponding error is widely referred to as FastTwoSum. Besides some assumptions on the floating-point system itself—all of which are satisfied by any binary IEEE 754 standard conform arithmetic, the main practical limitation of FastTwoSum is that the summands have to be ordered according to their exponents. In most preceding applications of FastTwoSum, however, a more stringent condition is used, namely that the summands have to be sorted according to their absolute value. In remembrance of Dekker’s work, this note reminds the original assumptions for an error-free transformation viaFastTwoSum. Moreover, we generalize the conditions for arbitrary bases and discuss a possible modification of the FastTwoSum algorithm to extend its applicability even further. Subsequently, a range of programs exploiting the wider applicability is presented. This comprises the OnlineExactSum algorithm by Zhu and Hayes, an error-free transformation from a product of three floating-point numbers to a sum of the same number of addends, and an algorithm for accurate summation proposed by Demmel and Hida.

AB - More than 45 years ago, Dekker proved that it is possible to evaluate the exact error of a floating-point sum with only two additional floating-point operations, provided certain conditions are met. Today the respective algorithm for transforming a sum into its floating-point approximation and the corresponding error is widely referred to as FastTwoSum. Besides some assumptions on the floating-point system itself—all of which are satisfied by any binary IEEE 754 standard conform arithmetic, the main practical limitation of FastTwoSum is that the summands have to be ordered according to their exponents. In most preceding applications of FastTwoSum, however, a more stringent condition is used, namely that the summands have to be sorted according to their absolute value. In remembrance of Dekker’s work, this note reminds the original assumptions for an error-free transformation viaFastTwoSum. Moreover, we generalize the conditions for arbitrary bases and discuss a possible modification of the FastTwoSum algorithm to extend its applicability even further. Subsequently, a range of programs exploiting the wider applicability is presented. This comprises the OnlineExactSum algorithm by Zhu and Hayes, an error-free transformation from a product of three floating-point numbers to a sum of the same number of addends, and an algorithm for accurate summation proposed by Demmel and Hida.

UR - http://www.scopus.com/inward/record.url?scp=85084152379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084152379&partnerID=8YFLogxK

U2 - 10.1007/s00211-020-01114-2

DO - 10.1007/s00211-020-01114-2

M3 - Article

AN - SCOPUS:85084152379

SN - 0029-599X

VL - 145

SP - 383

EP - 403

JO - Numerische Mathematik

JF - Numerische Mathematik

IS - 2

ER -