|
Published Articles >> Table of Contents >> Abstract
16th IEEE Symposium on Computer Arithmetic (ARITH-16 '03)
p. 142
Worst Cases and Lattice Reduction
Damien Stehle, ENS Paris
Vincent Lefevre, Technopôle de Nancy-Brabois
Paul Zimmermann, Technopôle de Nancy-Brabois
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.2003.1207672
Send link to a friend
| 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})} ).
|
 Additional Information
|
Citation:
Damien Stehle, Vincent Lefevre, Paul Zimmermann,
"Worst Cases and Lattice Reduction,"
arith,
p. 142,
16th IEEE Symposium on Computer Arithmetic (ARITH-16 '03),
2003
|
|
