(Basenote drift) complex arithmetic, was Re: Do I have a second?...
> Date: 03 Aug 2011 22:09:11 +0100
> From: "N.M. Maclaren" <nmm1@xxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> Cc: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Do I have a second? Re: Position: That the Standard for Computing
> with Intervals Have Only One Level 1 Requirement: Containment
>
> On Aug 3 2011, Dan Zuras Intervals wrote:
> >> >
> >> > While I might use less tortured prose, it sound to me like
> >> > the specification he desires is to return the tightest
> >> > interval that the working precision permits.
> >>
> >> > This is a workable & testable specification & is, at least
> >> > for the basic operations, identical to OUR specification.
> >>
> >> I disagree that it is either workable or testable, in general.
> >> See later.
> >
> > Hmm.
> > It served our purpose in 754 well enough.
>
> I am sorry, but that is a matter of opinion, and I think that it
> was one of its more serious mistakes.
>
> Inter alia, it has led to an almost complete lack of communication
> between the "IEEE floating-point always gives precisely the same
> answers" community and many language and library standards, compiler
> vendors and numeric programmers and users of their applications.
Ah, you refer to the Intel-goes-its-own-way-&-damn-the-
rest-of-the-world attitude.
On this we agree completely.
And you are correct that there was a limited amount that
we (754) could do about it after the fact. Clause 10 in
the new standard was about the best that was possible &
even THAT was a poor repair.
>
> >> > (2) Specify that all the operations we require
> >> > return the tightest possible results in the
> >> > precision available.
> >>
> >> That more-or-less forbids optimisation, and begs the question of
> >> what the precision available is, anyway. This is coming back as
> >> an important issue with the reinvention of coprocessors (including
> >> vector units, GPUs etc.) - they don't always behave exactly
> >> identically to the 'main' CPU.
> >
> > Now YOU are confusing me here.
> >
> > It neither forbids optimization nor permits untestably
> > loose implementations.
>
> It forbids any non-trivial expression rearrangement, including many
> cases of common expression elimination, for a start.
It does not.
Read it again.
It says "all operations we require" shall round correctly.
I address the issue of expressions further down.
That was the "blind expression" thing you had trouble with,
remember?
>
> > And there is no question of the precision available.
> > It is decided in the declaration of the interval
> > objects. WhereEVER the CPUs lie.
>
> I am sorry, but that makes little sense in either a language context
> or a hardware one. A declaration is more often associated with
> the storage representation than the arithmetic operations. In
> particular, that is true for many or most coprocessors. Consider
> the common and simple example of whether they use hard or soft
> underflow; that is NOT associated with the type, but whether the
> operation is passed to the coprocessor or not.
I just don't get you here.
As far as I know, ALL languages have some convention
for the type of their expressions. It is either
declared or implied by the expression/language. One
way or another, it is known.
As for the gradual underflow thing, I agree with that
too. Although even THAT is also associated with the
(datatype x implementation) you are dealing with.
Everything you mention is predictable if we write our
standard carefully.
I agree that gradual underflow presents us with a
portability issue. But it has proven to be a small
one over the years & should remain small for 1788.
>
> >> > (3) Specify that all optional operations ALSO
> >> > return tightest possible results should those
> >> > operations be chosen to be part of the
> >> > implementation. (This leaves it possible for
> >> > looser implementations of these operations to
> >> > be hanging around, just not as part of the
> >> > testable standard,)
> >>
> >> That more-or-less means that all serious numeric programs will be
> >> outside the standard, which rather removes the point.
> >
> > Well, I must say I don't understand this either.
>
> I have almost never seen a realistic numeric program that used only
> the basic arithmetic operations (even including square root). Also,
> no (numeric) language since the early 1950s has had no 'problematic'
> operations, such as trigonometric functions.
I have seen many such applications but ignoring that:
So?
If the entire thrust of your argument is that it is
difficult (even under the new 754) to obtain bit-for-bit
compatible floating-point results across platforms,
I wholeheartedly agree.
If it is further your opinion that we, 1788, should
desire such a thing, I agree with this as well.
If you further believe that it will be difficult for us
to specify such behavior, another agreement.
If you believe that it will be impossible &, therefore,
we shouldn't try, THAT is where you leave me behind.
Just because the world has chosen to be sloppy in how
it behaves W.R.T. arithmetic is no reason for us to
condone that behavior in our standard.
The new 754 took a stand & said (in clause 9) that
either a transcendental function rounds correctly all
the time or it is not sanctioned by the standard.
It was a hard line to take & difficult to get past the
committee but we all know it is possible & 2 generations
of researchers have spent their careers making it both
possible & efficient.
We should take such a stand in 1788 as well.
Indeed, for all the reasons you mention & more we are
UNIQUELY motivated to do so. For if the whole purpose
of 1788 is to give the users answers that they trust,
what better way to gain their trust than to give the
SAME answer no matter where it is computed.
It is true that we might fail & permit (even small &
unimportant) differences among platforms. And it is
true that seeing those differences will sow doubt
among our users.
But we will have you (& me) to explain it to them. :-)
>
> >> Er, what IS the blind sequence for anything non-trivial? That
> >> approach was taken by C99 for complex numbers, and it was and is
> >> a disaster. Even with as simple an operation as multiplication
> >> of complex numbers, the 'obvious' code is not the most precise.
> >
> > Well, let's see...
> >
> > Off the top of my head:
> >
> > ff(xx) = sqrt(xx^2) - abs(xx) + 2.
> >
> > As Nate is fond of reminding us, this should return
> > the fairly narrow interval [2,2] for all xx.
> >
> > And yet, implementing the function as written (i.e.
> > blindly) would result in wider intervals which depend
> > on xx.
> >
> > That's what I mean by "no worse than the blind
> > sequence written in the source".
> >
> > Such a result should be permitted without excluding
> > the possibility that a very clever compiler might
> > figure out that [2,2] is the answer in all cases.
>
> Yes, I know. But what IS the "blind sequence" for a complex
> multiplication? If the specification is going to be applicable only
> to programs that use nothing but the basic arithmetic operations,
> then I don't see that it's going to be much use.
>
>
> Regards,
> Nick Maclaren.
Well, you raise many issues with that observation.
First, you are correct that complex multiplication
is a non-trivial operation even for floating-point.
It will be made even more problematic for the
multiplication of complex intervals given the
distortion of the resulting interval by rotation
in the complex plane.
Indeed, the inability of interval arithmetic to
handle the conformal transformation of a bounding
box in the complex plane is a flaw in the arithmetic
itself that some (like Prof Kahan) believe to be
fatal to the very concept of intervals. (We have had
many a discussion over dinner on just this problem.)
And yet, if you look into the problem as I have,
I believe you'll find that the unrotated bounding
box that contains the correctly rounded result may
be computed by using nothing more than the dot
product like operations a*b +/- c*d on (usually)
the endpoints or (rarely) easily computable extrema
in between. (Involving just real numbers as I
recall.)
There is no need to go to an (r x theta) form to
get the answer. Although that issue will come up
again when it comes time to consider the complex
exponential.
So complex multiply goes into the same catagory as
reliable dot product: It is non-trivial to compute
but efficient methods are known.
That addresses your technical issue.
Now let me deal with the standard's issue.
So far, we have no complex arithmetic in 1788. And,
even if we should include it, it will go into the
recommended functions. NOT among the basic add,
subtract, multiply, divide, square root, & convert
that are required of our implementations. We should,
of course, require it to be correct if the implementor
chooses to include it. But that is possible & can be
done with no more effort than a dot product.
But beyond this technical issue of complex multiply,
if it is your concern that we risk all hell breaking
loose as soon as the user takes one step into the
area of transcendental functions, let's not permit
that to happen.
It is within our power to specify the correct behavior
of those functions. It is within the implementor's
power to efficiently provide them.
If we all exercise our power wisely, we can save the
user from the peril you fear.
It will not be easy to do but, to quote a wise man from
the Spiderman movies, "With great power comes great
responsibilities". :-)
Enjoy,
Dan