Proving Tight Bounds on Univariate Expressions in Coq
Résumé
The verification of floating-point mathematical libraries requires computing numerical bounds on approximation errors. Due to the tightness of these bounds and the peculiar structure of approximation errors, such a verification is out of the reach of traditional tools. In fact, the inherent difficulty of computing such bounds often mandate a formal proof of them. In this paper, we present a tactic for the Coq proof assistant that is designed to automatically and formally prove bounds on univariate expressions. It is based on a kernel of floating-point and interval arithmetic, associated with an on-the-fly computation of Taylor expansions. All the computations are performed inside Coq’s logic, in a reflexive setting. This paper also compares our tactic with various existing tools on a large set of examples.