Re: A proposal for the next motion
>> >> Vincent Lefevre wrote:
>> >> > On 2009-05-18 10:59:01 -0400, Nate Hayes wrote:
>> >> >> It does not matter if language defines the scope, since it requires
>> >> >> user to do two things:
>> >> >>
>> >> >> 1. Execute the desired operation
>> >> >> 2. Remember to check a status-flag, after the fact
>> >> >
>> >> > Note that (2) can be done only at the end (if the user wants
>> >> > to, as in many applications, the flag can safely be ignored);
>> >> > the exception could also be handled in an alternative way (see
>> >> > IEEE 754-2008, Section 8), in which case the handler could set
>> >> > the result to NaI, and this is exactly what you want.
>> >>
>> >> No! It's exactly what I wish to avoid. Especially in computer graphics
>> >> applications, where performance is critical and there is no operation
>> >> that
>> >> can generate {empty} as a result, anyways!
>> >
>> > Nate,
>> >
>> > On the one hand I agree that a global invalid state is an
>> > inconvenience that may be avoided by Vincent's suggestion.
>> >
>> > On the other hand I don't see that the graphics application
>> > introduces any new aversion to [empty] that you don't
>> > already have.
>> >
>> > After all, if the object is on the screen & visible to
>> > the 'eye', what homogeneous transformation could possibly
>> > result in [empty] as an answer?
>> >
>> > And, for that matter, if you would rather see NaI as a
>> > result what are you going to paint on the screen then?
>> >
>> > I'll admit that I have not done any graphics in recent
>> > years so there may have been advancements of which I am
>> > unaware that would cause this sort of problem. I am
>> > curious to know what they are.
>>
>> One day I wish to write a book about it. In the meantime, I fear it will
>> be
>> difficult in e-mail disucssions to explain everything (and much of it
>> would
>> be off-topic). Plus many of these ideas as they pertain to computer
>> graphics
>> are still, unfortunately, confidential.
>>
>> What I can say as a summary is this:
>>
>> All of our algorithms use modal interval analysis, so this means {empty}
>> does not exist in any of our software. Period. One of the reasons we
>> specifically switched to modal intervals many years ago is because c-set
>> calculations involving {empty} were giving us problems (see section 8.2
>> of
>> my introductory paper for a related topic and example).
>
> Actually my question is how either [empty] or NaI would arise
> in graphics applications involving the rendering of real scenes.
Dan,
The nice thing about working with intervals is it allows the *real* problems
in fields like computer graphics to be solved, as opposed to some
approximation based on linear, finite elements. Existing methods in computer
graphics are based primarily on rendering of polygons and/or shooting
infinitesimally thin "rays" into the scene, i.e., "ray tracing" or "point
sampling."
We do none of this. Instead, we attack the underlying nonlinear equations
and do a true area-based, analytic solution of each pixel. This not only
includes determining the pixel's visibility, but also the shading or "color"
of the pixel. This process easily includes rather exotic nonlinear
mathematics and functions that have poles, singularities or discontinuities.
Particularly when features like nonlinear motion-blur or displacements
appear in the scene. So issues of {empty} vs. NaI are commonplace.
>> In a few cases where we might need to use a classical algorithm like
>> interval Newton, we just check to see if the Newton step produces an
>> improper (non-standard) modal interval. If it does, this is proof of
>> non-existence of the zeros.
>
> This would seem to be the equivalent of proving the non-existence
> of zeros in an interval that gets contracted to the empty set.
>
> Is it not?
The end result is the same, but it does not require {empty}.
In modal intervals, any non-standard interval [b,a] such that b > a is
"moral equivalence" of {empty} for any classical algorithm.
>> Otherwise, NaI is used constructively, as indicator that a special
>> subroutine or graphics algorithm must be used, for example, or to provide
>> numerical proof that two interval expressions are not equivalent. It is
>> also
>> a mechanism that has consistently allowed us to find otherwise very
>> insiduous bugs in the software during development process.
>
> Now this is different. If you are INTRODUCING NaI's as some
> sort of programming indicator then I guess they cannot be
> avoided. Unless, of course, Vincent's tags included some
> sort of 'programming hack' tag as well. Its possible I
> suppose.
>
> BTW, your programming trick is similar to the two examples of
> practical uses for signalling NaNs that were brought to us at
> 754 when we tried to get rid of sNaNs for performance reasons
> among others. Prof Kahan & I published an article in Computer
> Magazine asking the world for sNaN uses & we got only these two.
>
> Of these two, one was old enough that the sources no longer
> existed & the other was an extensible interpretive language
> that could solve the problem in another way.
>
> Perhaps some reflection will show that you can solve your
> problem in some other way as well.
No!
In the world of intervals, it is misguided to call it a "trick." An example
was already given in discussions in the ER subgroup, but I will re-present
it here for those who have not seen:
Given the conditional equation
(x^2-1)/(x-1) = x+1
over domain [-4,4], what is the mathematical *truth* of the situation?
Clearly the equation is false, because the expressions on left and right
side are not equivalent, i.e., they are not equal when x = 1. However,
c-sets say the two expressions are equivalent, because use of {empty} in the
left side of the equation produces same result as the right side.
So it is a serious mistake, I believe, if 1788 only supports the c-set view
of things, because, in this case, it violates the "thou shall not lie"
commandment.
In our modal interval C++ library at Sunfish, the left side of the equation
over [-4,4] evaluates to NaI and the right side to [-3,5]. So this is
numerical proof the equations are not equivalent.
It was years of "reflection" that drew me to the conclusion {empty} was the
source of my problems, not the solution.
>> In future, we plan to advance to massively parallel, SIMD architectures
>> for
>> modal interval processing of real-time graphics. In that kind of
>> environment, I just don't believe it will be realistic or practical if
>> the
>> only way to obtain NaI (or its moral equivalent) is by global/local flags
>> or
>> traps.
>
> Agreed. Let's just eliminate this notion from the discussion.
Fantastic.
It is progress...
;-)
>> So this is a reason I have some sympathy for Vincent's idea of tagged
>> intervals, on the one hand. But of course on the other hand I ask all the
>> questions you put forward about how it affects hardware design, etc.
>>
>> . . .
>>
>> Nate
>
> There is one other I realized after I posted my list: There is
> the issue of register space for them mirroring the registers
> used to hold the interval bounds. Whether registers otherwise
> holding floating-point values are overloaded for this purpose or
> new register space (& busses) are created specifically for this
> task, the cost is non-trivial.
>
> That's for some sort of full-blown interval implementation
> though. Some more tepid form of interval support through a
> mixture of special floating-point instructions & tag management
> instructions could be had for not much more than the opcode
> space to put them there. In this case the performance would
> be similar to the best floating-point performance but without
> all the case analysis that dogs many of today's implementations.
>
> It is a compromise that might be able to be sold to chip
> manufacturers that are otherwise dubious of their customers'
> need for fast interval support.
>
> Enjoy,
>
> Dan