Gal's Accurate Tables Method Revisited
Damien Stehlé and Paul Zimmermann
Abstract:
Gal's accurate tables algorithm aims at providing an efficient
implementation of elementary functions with correct rounding as often as
possible.
This method requires an expensive pre-computation of a table made
of the values taken by the function -- or by several related functions -- at
some distinguished points. Our improvements of Gal's method are two-fold:
on the one hand we describe what is the arguably best set of distinguished
values and how it improves the efficiency and correctness of the
implementation of the function, and on the other hand we give an algorithm
which drastically decreases the cost of the pre-computation.
These improvements are related to the worst cases for the correct rounding of
mathematical functions and to the algorithms for finding them. We show that
the whole method can be turned into practice by giving complete
tables for 2^x and sin x for x in [1/2,1[, in double precision.
Here are the two tables mentioned in the article:
the sin x table and
the 2^x table.
Erratum in the final version of the paper: in Section 4, the
simultaneous worst case for sin and cos is t0=1f09c0c6cde5e3 and
not t0=31a93fddd45e3.
Homepage