Circular functions are not as intractable as you may think...
> /home/ben/Mail/inbox/3244 :Return-Path: owner-stds-1788@xxxxxxxxxxxxxxxxx
> Date: Thu, 18 Aug 2011 12:04:22 +0200
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> To: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: fwd from Jim Demmel: More on repeatability
>
> On 2011-08-17 18:02:56 +0100, N.M. Maclaren wrote:
> > On Aug 17 2011, Vincent Lefevre wrote:
> > >>>IMHO, this should be done only by specifying the full behavior, possibly
> > >>>depending on well-identified platform-dependent parameters. Otherwise it
> > >>>may be tricky to define "repeatable mode" and "same machine" (e.g. what
> > >>>if the machine is upgraded[*], some environment variables are changed,
> > >>>and so on?)
> > >>
> > >>Once you do that for any non-trivial operation, you are forbidding any
> > >>improvements in the future. State of the art today may be one result,
> > >>but someone may develop an improvement.
> > >
> > >With forbidden contraction and in tightest mode, there would be
> > >no possible improvements.
> >
> > Precisely. As has been pointed out, it is computationally infeasible
> > to specify mathematically optimal bounds for most non-trivial operations,
>
> This is not unfeasible. Correct rounding is what IEEE-754 recommends
> and is implemented in some libraries. For some functions, the
> termination cannot be proved, but this isn't much a problem in
> practice (it is not proven that the hardware works correctly anyway,
> so that this shouldn't prevent from implementing correct rounding).
Well, most clause 9 functions are implemented in software.
But for that, this is quite correct.
>
> The main problem can be the performance on some functions, e.g. for
> sin/cos/tan on large arguments. One solution would be to return [-1,1]
Domain reduction for circular functions hasn't been a
performance problem for 3 decades now. With O(emax)
memory for tables, the operation can be performed in
O(1) time.
> for sin and cos when the argument is large enough. The threshold could
> be specified by the user, so that reproducibility would be guaranteed.
More on this below.
>
> > so such a specification has to be for the best achievable bounds with
> > the technology at the time the specification is developed. Then someone
> > develops a better algorithm, and the standard forbids an implementor
> > to adopt it ....
>
> No, the standard won't forbid it. It will just forbid to return an
> *incorrect* result (w.r.t. reproducibility).
>
> If you want very fast algorithms, you can still drop reproducibility
> (which should only be optional).
While I grant that reproducibility should be optional
(if, IMHO, not default), it is not necessary to drop it
for performance reasons.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
>
> ...................
>
> /home/ben/Mail/inbox/3250 :Return-Path: owner-stds-1788@xxxxxxxxxxxxxxxxx
> Date: Thu, 18 Aug 2011 08:21:11 -0400
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> From: Michel Hack <hack@xxxxxxxxxxxxxx>
> Subject: Re: fwd from Jim Demmel: More on repeatability
>
> With regard to correctly-rounding sin/cos/tan, Vincent Lef1vre wrote:
> > I know, but there isn't much choice if for instance, realmax ~ 2^64.
>
> Well, realmax is much bigger than that: 2¬127 for float, 2¬1023 for double,
> and an alarming 2¬16383 for long double. (Or did I misinterpret?)
>
> A user-definable threshold for backing off to max range seems appropriate
> if we go in this direction.
More on all this below as well.
>
> Michel.
>
> ...................
>
> /home/ben/Mail/inbox/3251 :Return-Path: owner-stds-1788@xxxxxxxxxxxxxxxxx
> Date: Thu, 18 Aug 2011 14:28:36 +0200
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> To: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: fwd from Jim Demmel: More on repeatability
>
> On 2011-08-18 14:01:38 +0200, Vincent Lefevre wrote:
> > On 2011-08-18 13:30:31 +0200, Arnold Neumaier wrote:
> > > On 08/18/2011 12:04 PM, Vincent Lefevre wrote:
> > > >The main problem can be the performance on some functions, e.g. for
> > > >sin/cos/tan on large arguments. One solution would be to return [-1,1]
> > > >for sin and cos when the argument is large enough.
> > >
> > > This wouldn't be an optimal rounding if the argument is [realmax,realmax].
> >
> > I know, but there isn't much choice if for instance, realmax ~ 2^64.
>
> Oops, I meant Exponent(realmax) ~ 2^64, i.e. realmax ~ 2^(2^64).
Yes, even this.
>
> > However, for the IEEE 754 basic formats, correct rounding should
> > be OK if reproducibility is a must.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
I was reluctant to comment on this thread especially now
that the discussion has moved on to other things.
But I feel that the assumptions underlying this thread
may be shared by many.
I want to dispel that.
Consider the following.
In single precision we have:
maxpos1 = 2^128*(1-2^-24)
sin(maxpos1) = -0.521877
sin(maxpos1) contained in [-2188909/4194304,-8755635/16777216]
In double precision:
maxpos2 = 2^1024*(1-2^-53)
sin(maxpos2) = 0.00496195478918406
sin(maxpos2) contained in
[2860372190668619/576460752303423488,
5720744381337239/1152921504606846976]
In quad:
maxpos3 = 2^16384*(1-2^-113)
sin(maxpos3) = 0.951914854078820481136324892937573
sin(maxpos3) contained in
[4942624506426098432520117030049803/5192296858534827628530496329220096,
9885249012852196865040234060099607/10384593717069655257060992658440192]
These things are just not that difficult to compute any more.
And haven't been for decades. To continue to assume that
they are & deprecate the specifications of 1788 accordingly
does a disservice to all.
(Indeed, I discovered a fast & efficient method of what was
called 'range reduction' around 1980 or 1981. It turns out
I had rediscovered a result of Mary Payne's. Which, in turn,
was a variation of an earlier result by Gosper, I believe.
And this result has been rediscovered & improved upon many
times since. BTW, I won $3 from an MIT professor who bet me
I couldn't do it at the time. Best bet I ever made. :-)
But, while 754 requires these functions to round correctly
throughout their entire domain, the situation is somewhat
easier for 1788. And while it may be necessary, from time
to time, to use the specifications of 754 to correctly
contain a result within a narrow interval for an unreasonably
huge argument, it is only needed in the case of zero width
intervals.
For, indeed, if zero width intervals for unreasonably large
arguments are themselves unreasonable, then one need only
consider efficient domain reduction for the domain of a
circular function for which an ULP is less than 2*pi. And
that only happens for much MUCH smaller arguments.
For single: ulp1 ~ 2^27 ~ 10^8
For double: ulp2 ~ 2^56 ~ 10^17
For quad: ulp3 ~ 2^116 ~ 10^35
As for numbers as large as 2^2^64, except for unreasonable
zero width arguments, one need only consider them when the
PRECISION of the result is ALSO around 2^2^64. Something
that's not going to happen until memory gets much cheaper.
For if the precision required is a small as 10,000 bits, we
have that ulp10kb ~ 2^10003 ~ 10^3011. Which is STILL well
within the range of quad precision numbers.
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.
They are, you know.
Yours,
Dan