Improving the numerical accuracy of programs by automatic transformation
Abstract
The dangers of programs performing floatingpoint
computations are well known. This is due to the
sensitivity of the results to the way formulæ are written.
These last years, several techniques have been proposed
concerning the transformation of arithmetic expressions in
order to improve their numerical accuracy and, in this article,
we go one step further by automatically transforming
larger pieces of code containing assignments and control
structures. We define a set of transformation rules allowing
the generation, under certain conditions and in polynomial
time, of larger expressions by performing limited formal
computations, possibly among several iterations of a loop.
These larger expressions are better suited to improve, by reparsing,
the numerical accuracy of the program results. We
use abstract interpretation-based static analysis techniques
to over-approximate the round-off errors in programs and
during the transformation of expressions. A tool has been
implemented and experimental results are presented concerning
classical numerical algorithms and algorithms for
embedded systems.
Origin : Files produced by the author(s)