Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Fwd: IEEE-SA Daily email notification - You have 1 new notice(s).



On 01.08.2017 14:04, Michel Hack wrote:
> On Tue, 01 Aug 2017 13:09:26 +0200, Oliver Heimlich wrote:
>> Neither IEEE 1788 nor IEEE 754 consider infinities as numbers.
> 
> Actually they do (see entry for "number" in the glossary), but that's
> not the point.  They still distinguish between finite and infinite
> numbers, and only finite numbers can be members of an interval when
> the interval is viewed as a set.
> 
>> In IEEE 754 the values inf and -inf denote the result of an overflow.
> 
> In 754 they *also* denote exact results of operations involving zero or
> infinity.  The flags can be used to tell the difference.  It is in 1788
> that they only denote overflow or unboundedness.
> 
>> In IEEE 1788 these special values are used to denote boundaries of an
>> unbound interval -- not numbers.
> 
> Correction:  not members.
> 
> They are used as numbers when reporting the width of an unbounded interval.
> In that case they don't necessarily denote overflow, as the interval may
> have originally been given as unbounded, as opposed to being the result
> of a bounded operation but with unrepresentable bounds, i.e. oveflow.
> In that case the distinction can be made in the decoration -- but only by
> observing a change from COM to DAC.

Thank you for the clarification.  You may interpret my original post as
the sloppy mental model, which the practical software engineer has when
working with implementations of the standards.  ;-)

> (I wonder if we missed something here, in the 1788 decoration system:
> distinguishing unboundedness due to propagation from that due to overflow.)

We have an exception for this case in the constructors: IntvlOverflow

If the input is COM and the output is DAC and unbounded, you can always
conclude either overflow (Bolzano–Weierstrass theorem) or overestimation
(FTDIA).  I doubt that it is important to distinguish between overflow
and overestimation at all in interval arithmetic.

>> So, I don't understand what you disagree with.
> 
> Now, that is a valid point, made *repeatedly* in this forum, and in 1788.
> 
> Besides, 1788.1 is NOT the place for trying to re-introduce the EDP, as
> 1788.1 is intended to be a *subset* of 1788.  Unfortunately the EDP battle
> was lost in P1788, a few years ago, when its scope was reduced from an
> early "reliable computing" to just one technique for achieving that, namely
> Interval Arithmetic.
> 
> The proper place for proposing standardized "Complete Arithmetic", of
> which the EDP is but one component, is really 754-2028, as the current
> revision (754-2018, in progress) deliberately restricted itself to
> corrections and clarifications, and not new requirements.  There *is*
> actually a partially-open door, as 754-2018 is considering adding new
> *recommended* operations such as two-sum, to lay the foundation for a
> possible new requirement in 2028.  Unfortunately Complete Arithmetic
> is a rather big undertaking to specify completely (pun intended), and
> the 754-2018 WG is nearing the end of its term...  It was this lack
> of completeness that (in my opinion at least) derailed the attempt to
> include EDP as a requirement in 1788.  (It *is* a recommendation there.)

From a practical point of view, when we leave “complete arithmetic”
aside, I wonder where the EDP would be needed. In IEEE Std 1788-2015 we
have the following dot products:

 1. A recommendation to implement EDP, where you have access to the
exact result.  That is, you may reuse the full accumulator in follow-up
computations.

 2. A requirement to implement a correctly rounded dot product (with
respect to your number format).  That is, an EDP may be used internally,
but the user cannot use the exact result.

From my experience (which should be no benchmark at all) with the Octave
interval package, which includes a few interval arithmetic algorithms
that go beyond the standard functions, there is barely a need for the
EDP.  The package, of course, uses an EDP internally, but doesn't make
it available to the user.  Some public functions rely on that EDP:

 - correctly rounded dot product (required by IEEE 1788).

 - correctly rounded result for the square of an interval matrix without
the dependency problem [1].

Any other functions may be based on the correctly rounded dot product:

 - interval vector dot product (correctly rounded)
 - interval matrix multiplication (correctly rounded)
 - interval matrix division (either with Gaussian elimination or “fast”)
 - polynomial evaluation using Horner's scheme and iterative refinement
 - QR decomposition using Gram-Schmidt process

I'd be interested to hear of more useful applications of the EDP outside
the context of complete arithmetic.

Oliver


[1] “Feasible algorithm for computing the square of an interval matrix”
in O. Kosheleva, V. Kreinovich, G. Mayer, and H. T. Nguyen (2005):
Computing the cube of an interval matrix is NP-hard.  In SAC '05: Proc.
of the 2005 ACM Symposium on Applied Computing, pages 1449–1453, 2005