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).
Homepage