Searching worst cases of a one-variable function using lattice reduction
Damien Stehlé, Vincent Lefèvre, Paul A. Zimmermann · IEEE Transactions on Computers · 2005
We propose a new algorithm to find worst cases for the correct rounding of a mathematical function of one variable. 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. 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 less than N/sup -d2//2d+1 from a machine number in time O(N/sup (d+1/2d+1)+/spl epsiv//). For d=2, a detailed study improves on the O(N/sup 2/(3+/spl epsiv/)/) complexity from Lefevre's algorithm to O(N/sup 4/(7+/spl epsiv/)/). For larger d, our algorithm can be used to check that there exist no worst cases at distance less than N/sup -k/ in time O(N/sup 1/(2+/spl epsiv/)/).