A probabilistic approach to floating-point arithmetic
File(s)
Accepted version
Author(s)
Dahlqvist, Fredrik
Salvia, Rocco
Constantinides, George
Type
Conference Paper
Abstract
Finite-precision floating point arithmetic unavoidably introduces rounding errors which are traditionally bounded
using a worst-case analysis. However, worst-case analysis might
be overly conservative because worst-case errors can be extremely
rare events in practice. Here we develop a probabilistic model
of rounding errors with which it becomes possible to estimate
the likelihood that the rounding error of an algorithm lies
within a given interval. Given an input distribution, we show
how to compute the distribution of rounding errors. We do
this exactly for low precision arithmetic, for high precision
arithmetic we derive a simple approximation. The model is then
entirely compositional: given a numerical program written in
a simple imperative programming language we can recursively
compute the distribution of rounding errors at each step of the
computation and propagate it through each program instruction.
This is done by applying a formalism originally developed by
Kozen to formalize the semantics of probabilistic programs. We
then discuss an implementation of the model and use it to perform
probabilistic range analyses on some benchmarks.
using a worst-case analysis. However, worst-case analysis might
be overly conservative because worst-case errors can be extremely
rare events in practice. Here we develop a probabilistic model
of rounding errors with which it becomes possible to estimate
the likelihood that the rounding error of an algorithm lies
within a given interval. Given an input distribution, we show
how to compute the distribution of rounding errors. We do
this exactly for low precision arithmetic, for high precision
arithmetic we derive a simple approximation. The model is then
entirely compositional: given a numerical program written in
a simple imperative programming language we can recursively
compute the distribution of rounding errors at each step of the
computation and propagate it through each program instruction.
This is done by applying a formalism originally developed by
Kozen to formalize the semantics of probabilistic programs. We
then discuss an implementation of the model and use it to perform
probabilistic range analyses on some benchmarks.
Date Issued
2020-03-30
Date Acceptance
2019-12-04
Citation
2020, pp.596-602
Publisher
IEEE
Start Page
596
End Page
602
Copyright Statement
© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Identifier
https://ieeexplore.ieee.org/abstract/document/9048893
Grant Number
EP/P010040/1
Source
IEEE Asilomar Conference on Signals, Systems and Computers (ACSSC 2019)
Subjects
Science & Technology
Technology
Computer Science, Information Systems
Engineering, Electrical & Electronic
Telecommunications
Computer Science
Engineering
math.NA
math.NA
cs.NA
cs.PL
Publication Status
Published
Start Date
2019-11-03
Finish Date
2019-11-09
Coverage Spatial
Pacific Grove, CA, USA
Date Publish Online
2020-03-30