Error-Free Transformations

Error-Free Transformations

An Error-Free Transformation (EFT) for a given operation $\circ \in \{+, -, \times\}$ is a transformation allowing to express

\[(x, \delta) = \bigcirc_{\text{eft}}(a, b)\]

such that

\[\begin{align*} &x + \delta = a\circ b,\\ &x = \lozenge(a\circ b), \end{align*}\]

where $\lozenge(x)$ denotes rounding $x\in\mathbb{R}$ to the nearest representable FP value, and all equalities written above are exactly valid (i.e. in the sense of real, infinite-precision computations).

EFTs are defined in the StochasticArithmetic.EFT module. They are used by other parts of StochasticArithmetic.jl, but can also be used standalone, for example to implement compensated algorithms.

Reference

using StochasticArithmetic.EFT
twoSum(a, b)

Error-Free Transformation for the sum of two numbers:

(x,y) = twoSum(a,b)

$\Leftrightarrow$

$x = fl(a+b)$ and $x+y = a+b$

source
twoProd(a, b)

Error-Free Transformation for the product of two numbers:

(x,y) = twoProd(a, b)

$\Leftrightarrow$

$x = fl(a\,b)$ and $x+y = a\,b$

source
twoDiv(a, b)

Approximate transformation for the division. The transformation is not exact (the error is not representable) but at least the sign of y should be correct:

(x, y) = twoDiv(a, b)

$\Leftrightarrow$

$x = fl(a/b)$ and $y ≈ a/b - x$

source