Finite-precision floating point arithmetic 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 quantify the likelihood that the rounding error of an algorithm lies within a given interval.

Given an input distribution, the model requires the distribution of rounding errors. We show how to exactly compute this distribution for low precision arithmetic. For high precision arithmetic we derive a simple but surprisingly useful approximation. The model is then entirely compositional: given a numerical program written in a simple imperative programing language we can recursively compute the distribution of rounding errors at each step and propagate it through each program instruction. This is done by applying a formalism originaly developed by Kozen to understand the semantics of probabilistic programs, for example how probability distributions gets transformed by assignments or "if then else" statements.

Dr. Fredrik Dahlqvist is from University College London, UK