Re: Circular functions are not as intractable as you may think...
Dan asked me to comment on the paper below:
> Gal's Accurate Tables Method Revisited
> Damien Stehle' & Paul Zimmermann
>
> (From ARITH-17 in 2005. Gal was one of the first guys to
> demonstrate back in the late 70s & early 80s that correctly
> rounded transcendental functions were both possible &
> efficient to compute. I'll let Paul describe his own paper
> but, as it was published before 754 was published in 2008, it
> contains some statements about 754 which we later changed.)
to approximate f(x) around a point x0, one usually uses a Taylor approximation
f(x) = f(x0) + (x-x0)*f'(x0) + O((x-x0)^2), where x0 is near from x, and taken
in a table. Assume all values are evaluated in double precision (53 bits),
and x-x0 is about 2^(-10). Then f(x0) will be accurate to 53 bits only,
although (x-x0)*f'(x0) is accurate to about 63 bits.
Gal's idea is to choose x0 so that f(x0) is accurate to about 63 bits, instead
of choosing x0 in a regularly-spaced fashion. We thus want
f(x0) = yyy...yyy.000...000zzz, where the dot separates the first 53 bits,
and we have 10 successive zeros. Then f(x) will be accurate to about 63 bits
(before the final rounding). This means that about 99.9% of the cases will be
correctly rounded (for directed rounding). Moreover there is an efficient test
to detect the remaining 0.1% cases that might be incorrectly rounded.
The contribution of the paper with Damien Stehlé is to show this approach is
essentially optimal, and to give a faster method to find the "good" table
points x0. Still assume that x-x0 is about 2^(-10), but now we want f(x) to
be accurate to 73 bits, thus f(x0) accurate to 73 bits, and f'(x0) to 63 bits.
Using the LLL algorithm, we exhibit a method to find points x0 such that
*simultaneously* f(x0) and f'(x0) are accurate. An example implementation for
the exp2 function can be found at http://www.loria.fr/~zimmerma/free/exp2-7.c.
> There are many more. Find your favorites. I should point
> out that the collective wisdom of these folks has already
> found its way into the GNU MPFR library providing portable &
> efficient correctly (& directed) rounded library functions
> for all at the cost of a download.
>
> It is part of MPFR because there are still calls to high
> precision functions contained within the code. Although, in
> many cases, there are no known examples where those functions
> are actually called. The function calls are there because the
> proofs that they are not needed are not.
I should point out that MPFR only implements arbitrary precision algorithms,
and no table-based methods such as Gal's algorithm. For those interested in
fast and correct rounding in double precision, look at the CRlibm library
(http://lipforge.ens-lyon.fr/www/crlibm/). Since it focuses on double
precision only, CRlibm is much faster than MPFR for this target.
> It turns out that, while the proofs are no easier for directed
> rounding, the algorithms are slightly easier than the equivalent
> for round-to-nearest. That is, the latter implies the ability
> to do the former. It is because in round-to-nearest one must
> take an infinitely precise result & move it no more than 1/2 ULP
> to a representable number. Whereas in directed rounding one is
> permitted to move as much as a full ULP.
Round-to-nearest to n bits reduces to directed rounding to n+1 bits,
thus we can focus on directed rounding only.
> I think Paul can describe the situation more clearly than can I
> but it turns out there are only finitely many examples of this
> bad behavior. The rest are (likely) bounded away from
> representable numbers as are most other transcendental functions.
> And thus should be able to be approximated as efficiently as
> other transcendental functions.
yes (lower) bounds are known between values of transcendental functions and
machine numbers, but they are usually too small to be usable in practice.
Currently the only known way to find "worst cases" is by exhaustive search,
which was initiated in Jean-Michel Muller's group, mainly by Vincent Lefèvre,
and then improved by other people. This is now doable for double precision,
we have even performed a complete search for 2^x in double-extended precision
(http://www.loria.fr/equipes/spaces/slz.en.html) but quad-precision remains
out of reach.
Paul