Re: Circular functions are not as intractable as you may think...
> Date: Sat, 20 Aug 2011 17:28:24 +0200
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> CC: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Circular functions are not as intractable as you may think...
>
> On 08/20/2011 03:52 PM, Dan Zuras Intervals wrote:
>
> > . . .
> >
> > To conclude: There may be problems in which an interval
> > computation is intractable when the corresponding
> > floating-point problem is not.
> >
> > But computing narrow interval results reliably for 754
> > transcendental functions is NOT one of them.
> >
> > Please feel free to consider reproducible versions of
> > these functions as both feasible& efficient.
>
> Interesting.
>
> Please provide references that what you claim for correct rounding is
> also valid for optimal directed rounding, which is what is needed for
> reproducble interval results.
I don't have access to the library resources that most of you
do but a quick google of 'correctly rounded transcendental
functions' gives me:
New Algorithms for Improved Transcendental Functions on IA-64
by Shane Story & Ping Tak Peter Tang
(Peter Tang has done some very good work in this area in
recent years. This paper describes the correct implementation
of all of the functions 2^x - 1, log2(x), log2(1 + x), sin,
cos, sincos (when both are needed), tan, & atan in the context
of the FMA available on the IA-64 architecture.)
Handbook of Floating-Point Arithmetic
By Jean-Michel Muller, Nicolas Brisebarre, Florent de Dinechin,
Claude-Pierre Jeannerod, Vincent Lefevre, Guillaume Melquiond
(Let me recommend chapter 3, in particular 3.4.11, & chapter
12 in which they outline how to do all of the functions listed
in clause 9 of 754. Vincent, would you care to elaborate?)
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.)
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.
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.
In both cases one bounds the infinitely precise result AWAY from
either a representable number or a number half way in between
2 representable numbers. In the round-to-nearest case:
xxx.1000...000xxx
xxx.1000...000000
xxx.0111...111xxx
it is done half way between to representable numbers. (The
decimal point marks the ULP from trailing bits.)
In directed rounding it is either
xx1.000...000xxx
xx1.000...000000
xx0.111...111xxx
or
xx0.000...000xxx
xx0.000...000000
xx1.111...111xxx
which is 1/2 ULP easier to do.
In almost all cases, transcendental functions of representable
arguments ARE bounded away from representable results although
proving by how much is tricky.
An exception that was noted in the later years of 754 was the
case of the x^y function in decimal. (Binary is not a problem.)
It can happen that the 5th root of an exactly representable
decimal number is ALSO an exactly representable decimal number.
A simple example, 32^0.2 = 2 exactly.
At the time that this was noted I thought it was the death
knell to any chance we had to correctly round x^y in a bounded
amount of time. I don't think it made it into his book but
Jean-Michel & his friends proved me wrong.
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.
Prof Kahan & I once opined over dinner that neither of us would
see a correctly rounded x^y in our lifetimes. Velvel is 20
years older than I am but I now think even HE might see it soon.
There is wonderful work going on at a wonderful pace.
Yours,
Dan