Article

Propagation of Roundoff Errors in Finite Precision Computations: A Semantics Approach

Author:

Matthieu MartelAuthors Info & Claims

ESOP '02: Proceedings of the 11th European Symposium on Programming Languages and Systems

Pages 194 - 208

Published: 08 April 2002 Publication History

Abstract

We introduce a concrete semantics for floating-point operations which describes the propagation of roundoff errors throughout a computation. This semantics is used to assert the correctness of an abstract interpretation which can be straightforwardly derived from it. In our model, every elementary operation introduces a new first order error term, which is later combined with other error terms, yielding higher order error terms. The semantics is parameterized by the maximal order of error to be examined and verifies whether higher order errors actually are negligible. We consider also coarser semantics computing the contribution, to the final error, of the errors due to some intermediate computations.

References

[1]

F. Chaitin-Chatelin and V. Frayssé. Lectures on Finite Precision Computations . SIAM, 1996.

[2]

F. Chaitin-Chatelin and E. Traviesas. Precise, a toolbox for assessing the quality of numerical methods and software. In IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics , 2000.

[3]

P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximations of fixed points. Principles of Programming Languages 4 , pages 238-252, 1977.

[4]

P. Cousot and R. Cousot. Abstract interpretation frameworks. Journal of Logic and Symbolic Computation , 2(4):511-547, 1992.

[5]

M. Daumas and J. M. Muller, editors. Qualité des Calculs sur Ordinateur . Masson, 1997.

[6]

D. Goldberg. What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys , 23(1), 1991.

[7]

E. Goubault. Static analyses of the precision of floating-point operations. In Static Analysis Symposium, SAS'01 , number 2126 in LNCS. Springer-Verlag, 2001.

[8]

E. Goubault, M. Martel, and S. Putot. Concrete and abstract semantics of fp operations. Technical Report DRT/LIST/DTSI/SLA/LSL/01-058, CEA, 2001.

[9]

E. Goubault, M. Martel, and S. Putot. Asserting the precision of floating-point computations: a simple abstract interpreter. In ESOP'02 , 2002.

[10]

J. R. Hauser. Handling floating-point exceptions in numeric programs. ACM Transactions on Programming Languages and Systems , 18(2), 1996.

[11]

W. Kahan. The improbability of probabilistic error analyses for numerical computations. Technical report, Berkeley University, 1991.

[12]

W. Kahan. Lecture notes on the status of IEEE standard 754 for binary floating-point arithmetic. Technical report, Berkeley University, 1996.

[13]

D. Knuth. The Art of Computer Programming - Seminumerical Algorithms . Addison Wesley, 1973.

[14]

P. Langlois and F. Nativel. Improving automatic reduction of round-off errors. In IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics , volume 2, 1997.

[15]

V. Lefevre, J.M. Muller, and A. Tisserand. Toward correctly rounded transcendentals. IEEE Transactions on Computers , 47(11), 1998.

[16]

M. Pichat and J. Vignes. The numerical study of unstable fixed points in a chaotic dynamical system. In IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics , volume 2, 1997.

[17]

J. Vignes. A survey of the CESTAC method. In Proceedings of Real Numbers and Computer Conference , 1996.

Cited By

Lee WBao TZheng YZhang XVora KGupta R(2015)RAIVE: runtime assessment of floating-point instability by vectorizationACM SIGPLAN Notices10.1145/2858965.281429950:10(623-638)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814299
Lee WBao TZheng YZhang XVora KGupta RAldrich JEugster P(2015)RAIVE: runtime assessment of floating-point instability by vectorizationProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814299(623-638)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814299
Bao TZhang X(2013)On-the-fly detection of instability problems in floating-point program executionACM SIGPLAN Notices10.1145/2544173.250952648:10(817-832)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509526
Show More Cited By

Recommendations

Semantics of roundoff error propagation in finite precision calculations

We introduce a concrete semantics for floating-point operations which describes the propagation of roundoff errors throughout a calculation. This semantics is used to assert the correctness of a static analysis which can be straightforwardly derived ...
A Simulative Study of Correlated Error Propagation in Various Finite-Precision Arithmetics

The accumulated roundoff error incurred in long arithmetic computations involving a randomized mixture of addition, subtraction, multiplication, and division operations applied to an initial randomly generated data base is studied via simulation. ...
Modular Optimization-Based Roundoff Error Analysis of Floating-Point Programs
Static Analysis
Abstract
Modular static program analyses improve over global whole-program analyses in terms of scalability at a tradeoff with analysis accuracy. This tradeoff has to-date not been explored in the context of sound floating-point roundoff error analyses; ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ESOP '02: Proceedings of the 11th European Symposium on Programming Languages and Systems

April 2002

329 pages

ISBN:3540433635

Editor:
Daniel Le Métayer

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 April 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee WBao TZheng YZhang XVora KGupta R(2015)RAIVE: runtime assessment of floating-point instability by vectorizationACM SIGPLAN Notices10.1145/2858965.281429950:10(623-638)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814299
Lee WBao TZheng YZhang XVora KGupta RAldrich JEugster P(2015)RAIVE: runtime assessment of floating-point instability by vectorizationProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814299(623-638)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814299
Bao TZhang X(2013)On-the-fly detection of instability problems in floating-point program executionACM SIGPLAN Notices10.1145/2544173.250952648:10(817-832)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509526
Bao TZhang XHosking AEugster PLopes C(2013)On-the-fly detection of instability problems in floating-point program executionProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509526(817-832)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2509136.2509526
Barr EVo TLe VSu Z(2013)Automatic detection of floating-point exceptionsACM SIGPLAN Notices10.1145/2480359.242913348:1(549-560)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2480359.2429133
Barr EVo TLe VSu ZGiacobazzi RCousot R(2013)Automatic detection of floating-point exceptionsProceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2429069.2429133(549-560)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2429069.2429133
FäHndrich MLogozzo F(2012)Checking Compatibility of Bit Sizes in Floating Point Comparison OperationsElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2012.10.004288(15-23)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1016/j.entcs.2012.10.004
Tang EBarr ELi XSu ZTonella POrso A(2010)Perturbing numerical calculations for statistical analysis of floating-point program (in)stabilityProceedings of the 19th international symposium on Software testing and analysis10.1145/1831708.1831724(131-142)Online publication date: 12-Jul-2010
https://dl.acm.org/doi/10.1145/1831708.1831724
Chaudhuri SGulwani SLublinerman R(2010)Continuity analysis of programsACM SIGPLAN Notices10.1145/1707801.170630845:1(57-70)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1707801.1706308
Chaudhuri SGulwani SLublinerman RHermenegildo MPalsberg J(2010)Continuity analysis of programsProceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1706299.1706308(57-70)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1706299.1706308
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents