Worst cases and lattice reduction

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 integer small value problem - for polynomials with integer coefficients - using lattice reduction (D. Coppersmith, 1996; 2001). 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^-d2/(2d+1) from a machine number in time O(N^((d+1)(2d+1))+ε/). For d=2, this improves on the O(N²(3+ε)/) complexity from Lefevre´s algorithm (V. Lefevre, 2000; V. Lefevre et al., 2001) to O(N³(5+ε)/). 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⁽¹2)+O(1/k)/).