Worst Cases and Lattice Reduction

Damien Stehlé and Vincent Lefèvre and Paul Zimmermann

Abstract: We propose a new algorithm to find worst cases for correct rounding of an analytic function. We first reduce this problem to the real small value problem --- i.e. for polynomials with real coefficients. Then we show that this second problem can be solved efficiently, by extending Coppersmith's work on the roots of modular multivariate polynomials using lattice reduction. For floating-point numbers with a mantissa less than N, and a polynomial approximation of degree d, our algorithm finds all worst cases at distance $< N^{\frac{-d^2}{2d+1}}$ from a machine number in time $O(N^{\frac{d+1}{2d+1}+\epsilon})$. For d=2, this improves on the $O(N^{2/3+\epsilon})$ complexity from Lefèvre's algorithm to $O(N^{3/5+\epsilon})$. We exhibit some new worst cases found using our algorithm, for double-extended and quadruple precision. For larger d, our algorithm can be used to check that there exist no worst cases at distance $< N^{-k}$ in time $O(N^{\frac{1}{2}+O(\frac{1}{k})})$.

Download: pdf (Slightly outdated version).