Dan Zuras Intervals wrote:
I assumed that a transformation for the purpose of making
> things
fast might be in conflict with one that makes it
> narrow.
Skip to the last line if you don't want
the details of the free education.
In unoptimized "literal interpretation"
mode, the generated code must construct two separate Intervals (containing
the same values) then multiply them and return that. The internal
representation will be equivalent to:
Interval square
(double x) {
Interval __temp1 = Interval (-x, +x);
Interval __temp2 = Interval (-x, +x);
Interval __temp3 = __temp1 * __temp2;
return __temp3; } In this case the resulting range is
symmetrical about zero. The cost is two double negations, two Interval
from double constructions, one Interval multiply (ie two double multiplies),
and possibly one Interval copy.
In speed optimization mode, most compilers
can trivially recognize that the two factors are identical and have no
side effects, so only one needs to be constructed. The result is
equivalent to:
Interval square
(double x) {
Interval __temp1 = Interval (-x, +x);
Interval __temp3 = __temp1 * __temp1;
return __temp3; } The resulting range is still symmetrical.
The cost is one double negation, one Interval from double construction,
one Interval multiply (ie two double multiplies), and possibly one Interval
copy. So this way is faster with no precision change.
In precision (width) optimization mode,
a compiler could be taught not just to recognize the "Interval times
itself" mode, but also to understand the semantics in a way that's
normally pointless for floating point but meaningful for intervals - the
result cannot be negative. You could do that in ways that would be
slower, but you can also realize that now the individual floating point
operations only need to calculate the upper bound, not the lower. The
result is equivalent to:
Interval square
(double x) {
double __temp4 = x.sup;
double __temp5 = __temp4 * __temp4;
Interval __temp6 = Interval (0, __temp5);
return __temp6; } The resulting range is nonnegative -
only half the more obvious approaches. The double negations are gone,
and the multiply is of a double not an Interval so likely faster. The
cost is one double from Interval extraction (likely free), one double multiply,
one Interval from zero and double construction, and possibly one Interval
copy.
I've ignored important issues like the
cost of changing the rounding mode, which can vary from free to expensive
depending on the architecture.
This last approach may be around
twice as fast, and halves the range. So yes, sometimes you can win
both ways.
- Ian Toronto
IBM Lab 8200 Warden D2-445 905-413-3411
Ralph Baker Kearfott <rbk@xxxxxxxxxxxxx> Sent by: owner-stds-1788-er@xxxxxxxxxxxxxxxxxxxxx
18/03/2009 07:00 AM
Please respond to
rbk@xxxxxxxxxxxxx
To
cc
stds-1788-er@xxxxxxxxxxxxxxxxxxxxx
Subject
Re: [IEEE P1788 er subgroup]: Wait a
minute now...
Dan and 1788-er,
See my inserted comments.
Baker
On 3/18/2009 2:16 AM, Dan Zuras Intervals wrote:
> I
was just reading what I sent out& I realized I made
> a
couple of assumptions that may not be true.
>
> I
assumed that a transformation for the purpose of making
> things
fast might be in conflict with one that makes it
> narrow.
>
> Is
that the case? Are there transformations that make
> things
faster but widen the intervals? Can you show me
> one?
Or do transformations that reduce the total number
> of
operations also reduce the width of the interval?
> (Such
things are common WRT accuracy in floating-point.)
>
A very rough heuristic is, the less operations, the narrower
the interval. More precisely, the less number of times the
same subexpression appears in an overall _expression_, the
narrower the interval, but there are exceptions. I do not
have a compendium of examples in my "fast memory," but I'm
hoping others will tender them.
Another heuristic is that lower floating-point accuracy
corresponds to wider intervals.
> The
other assumption I made was that a transformation
> intended
to narrow an intervals narrows all applicable
> intervals
everywhere.
>
That definitely is not true. One _expression_ might give the
narrowest bounds in one part of the domain, whereas another
(equivalent in the field of real numbers) would give narrower
bounds in another part of the domain. Again, I'm also hoping
someone will tender examples.
> Is
that true? Or are there transformations that narrow
> some
expressions they apply to& not others? Are there
> transformations
that narrow expressions in part of their
> domain
but widen it in others? Can you give me examples?
>
> All
part of my nefarious plan to get a free education out
> of
you guys.
>
> Muha
ha ha...
>
>
Dan
>
>
--
---------------------------------------------------------------
R. Baker Kearfott, rbk@xxxxxxxxxxxxx (337) 482-5346
(fax)
(337) 482-5270 (work)
(337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------