(SC22WG14.1747) Complex bakeoff - example 1

[David Knaak]

Frank,

I think you have made some very good points.  However, I disagree with some
of your conclusions.  I'll be specific below.

At 17:21 10/06/95, Frank Farance wrote:
>> Date: 3 Oct 1995 10:40:19 -0800
>> From: "Jim Thomas" <jim_thomasataligent.com>
>> Subject: (SC22WG14.1732) Complex bakeoff - example 1
>> To: "numeric-interest" <numeric-interestavalidgh.com>,
>>         "x3j11 wg14" <sc22wg14adkuug.dk>
>>
>> Infinities, NaNs, and signed zeros are key to IEEE arithmetic's completeness
>> property:  operations always produce a well-defined result, which in turn
>> behaves predictably in subsequent operations.  For real arithmetic, this
>> property has proven useful for writing simpler more robust codes.
>
> I feel I occassionally need to make the following points
> about exceptional values (infinities, NaNs, signed zeroes,
> etc.) that seems to get lost when we discuss details.  These
> exceptional values aren't really values, but placeholders

This is THE key point.  The exceptional values are placeholders to indicate
that, in most cases, the true value can't be represented by the hardware.
Now if the expression was 1/0, then the true value is infinity.  But most
of the infinities that occur in computations are overflows, that is, very
large finite values but too big for the hardware to represent.  So while
MAX/MIN will
give a predicable result - infinity - it is not the true result.  If you
start treating it like it was the true result, you can end up with a wrong
result.  See Frank's examples below.

> that conveniently help us write expressions that maintain
> their conceptual clarity while handling exceptional cases.
> For example, in
>
>         T1 = R1/S1;
>
> the fact that finite/infinite == zero and finite/zero ==
> infinite is convenient for us *assuming we write code with
> full knowledge of how the exception handling is performed*.
> For example, the following code:
>
>         T2 = R2/S2; /* choice 1 */
>         T2 = R2/(1.0/(1.0/S2)); /* choice 2 */
>
> would produce the same result for varying values of S2
> (including zero and infinity).  Thus, we might believe that
> regardless of how we write the expression, the true
> ``mathematical'' result is returned.  However, this is, in
> general, not the case.  For example, if R2 and S2 are really
> the values:
>
>         R2 = X*X;
>         S2 = X;
>
> the true mathematical result of T2 should always be S2.
> Likewise, if R2 and S2 are the values:
>
>         R2 = X;
>         S2 = X*X;
>
> the true mathematical result of T2 should always be the
> reciprocal of R2.  Clearly, we can't talk about the true
> mathmematical value of T2 unless we know something about the
> nature of the expression that equates to it.  Even if the
> hardware could keep track of various types of infinities
> (e.g., infinity vs. infinity squared, infinity (the number
> of integers) vs. 2^infinity (the number of reals)) it still
> might not be able to get the correct result because the
> knowledge of the nature of R2 and S2 might be outside the
> program: the program receives its data via binary values,
> rather than attribute-loaded symbolic values (e.g., negative
> 2^infinity).

This is another way of stating that the exceptional values are
placeholders, and not the true values.  In math, there are different
infinities (e.g. the number of integers vs. the number of reals) but IEEE
hardware represents both of them the same way.

>
> Another example is:
>
>         T3 = (1.0/P3)*(1.0/Q3)*(1.0/R3)*(1.0/S3);
>
> which might produce the wrong mathematical answer if the
> compiler rewrites the expressions.  Likewise, if we rewrite
> this as:
>
>         T3 = (1.0/P3);
>         T3 *= (1.0/Q3);
>         T3 *= (1.0/R3);
>         T3 *= (1.0/S3);
>
> we can still get wrong mathematical result.  In these cases,
> I've demonstrated that you can get the wrong mathematical
> result even with unattributed infinities.  Adding in NaNs,
> signed zeroes, and signed infinities doesn't resolve the
> problems.

I agree.

>
> As Harry Cheng pointed out, there are other ``infinity
> paradigms'' that have a single infinity in contrast to
> signed infinities.  Each paradigm is useful for a certain
> set of applications, but none are applicable 100% of the
> time (another way of saying ``yes, there are several
> branches of mathemetics'').

Yes.  And for complex in C, we could make things hopelessly complicated
by trying to accomodate all (or even just several) of the possibilities.
But choosing one paradigm, e.g. cartesian representation, covers most cases
with the least difficulty.  But it, as with any other paradigm, has it's
limitations.

>
> So why do we care about this?  Basically, some of the
> hardware features are convenient for some of the paradigms.
> it allows us to write:
>
>         function(param1,param2,param3)
>         {
>                 /*
>                  * ...
>                  * Lots of expressions with no
>                  * testing for exceptions.
>                  * ...
>                  */
>                 if ( isexception(result1) ||
>                         isexception(result2) ||
>                         isexception(result3) )
>                 {
>                         /*
>                          * Figure out what went wrong.
>                          */
>                 }
>         }
>
> When writing code that is expected to be executed in
> parallel on thousands of processors or heavily pipelined, it
> is convenient to have a linear flow control rather many
> branching cases (e.g., "if" statements, checking "errno").

The above programming practice is how I think NaNs and Infinities and even
signed zeros can be very useful.  And the distinction between a NaN and
an infinity or the distinction between a +0 and a -0 can be useful when
your code analyzes "what went wrong".  But again, these exceptional values are
markers, not true results.  And this programming practice is also useful
on sequential machines.  If exceptions are rare in a calculations, then a
loop unencumbered with lots of checks will go fast and then you can have
another loop just to check each value to see if something exceptional
happened.  This will generally out-perform a single loop.

> In addition to performance reasons, it is useful for program
> clarity -- imagine if every subexpression were bracketed by
> "if" statements.
>
> With respect to imaginaries vs. complex, there is no
> *mathmematical* need for a separate type.  When speaking
> about a pure imaginary number, e.g., 1.0I, there is no
> difference between 1.0I and 0+1.0I because the zero, in this
> case, is the value zero rather than a limiting value of zero
> (e.g., X+1.0I as X approaches zero).  Since zero is the
> identity element in addition, 1.0I is required to be
> identical to 0+1.0I.

I agree.

> Of course, as soon as we implement
> this on machines, there is a problem with the implementation
> because the exception handling infinity*(1.0I) is not the
> same as infinity*(0+1.0I) although they are *identical*
> mathematically.  The difference, is that a NaN is produced
> and dragged around, invalidating many subexpressions that,
> in the end, have to be discovered and re-run with the
> exception recognition code.

This is where I start disagreeing with your conclusions.  I think that
any time you have an expression where you multiply infinity times
anything, the result of the expression is suspect and NaN is infact,
a "good" result in that it tells you that you have to take a different
approach to the calculation.  I am still waiting for someone to show me
a reason why infinity*(1.0I) is a meaningful value that must be preserved
in a calculation.  I think the presence of the infinity probably means
you've overflowed so you no longer have the true value.  And if the value
were from x/0, then tell me what the mathematical significance is of
(x/0)(1.0I) in a numerical computation.

>
> The rationale for adding pure imaginaries to the type system
> is that, from a programming perspective, we desire pure
> imaginaries to behave like pure reals.  If your hardware
> doesn't have this exception handling capability for
> infinities and NaNs (e.g., some non-IEEE hardware), you have
> no choice but to write the expressions bracketed by "if"
> statements.  Thus, systems that don't support this exception
> handling have less of a need for a separate imaginary type.

Again, I disagree here.  With or without IEEE hardware, as long as
your calculations stay within the domain of representable, finite values,
there is no need for a pure imaginary type.  It is only the case of
multiplying a pure imaginary times infinity that we get an "undesirable"
result.  But since we have already been claiming that the presence of the
infinity already says something exceptional happened, then it doesn't
really matter whether the exception is represented by an infinity or a
NaN.  In either case, we have to redo the calculation another way.

>
> The rationale for adding imaginary types is not that it
> allows code to get mathematically correct results, but it
> facilitates performance and conceptual clarity improvements
> in the goal of getting mathematically correct results on
> hardware that supports these features.

I would go along with this if I could see a full specification of
imaginary types that does, in fact, avoid the problems it is supposed
to do.  We can look at an isolated expression, infinity * (1.0I), and
see how it helps here.  But as far as I have heard, this is the only
expression (infinity times pure imaginary) that anyone has expressed
concern about.  But in a calculation of any significant size,
any pure imaginary variable would end up in an expression that requires
a promotion to complex, and then we are back to where we started - unless
the language requires that the type of a complex expression change dynamically
to imaginary when the value of the real part becomes zero!!!

>
> I am in favor of the inclusion of an imaginary type in the
> CCE proposal.

I am not in favor of the inclusion of an imaginary type because:
1) there really isn't a problem that needs to be solved by it,
2) it doesn't solve the problem any way,
3) the complexity added by it to the language is too great.

- David Knaak