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 coef.cients. Then we show that this second problem can be solved ef.ciently, by extending Coppersmith?s work on the integer small value problem — for polynomials with integer coefficients — using lattice reduction [4, 5, 6]. 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 0(N^{\frac{{d + 1}}{{2d + 1}} + \varepsilon } ). For d = 2, this improves on the 0(N^{{2 \mathord{\left/ {\vphantom {2 {3 + \varepsilon }}} \right. \kern-\nulldelimiterspace} {3 + \varepsilon }}} ) complexity from Lefèvre?s algorithm [15, 16] to 0(N^{{3 \mathord{\left/ {\vphantom {3 {5 + \varepsilon }}} \right. \kern-\nulldelimiterspace} {5 + \varepsilon }}} ). 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 0(N^{\frac{1}{2} + 0(\frac{1}{k})} ).