|
Richard,
Sorry if I am late agreeing with you. You are absolutely
correct. Rational arithmetic is the perfect way to do what Ulrich
says he wants to do with exact (rational) inputs to any given
computation.
Cheers,
Bill
On 9/17/13 8:21 AM, Richard Fateman wrote:
On 9/17/2013 6:24 AM, Ulrich Kulisch
wrote:
Am 15.09.2013 18:25, schrieb
Richard Fateman:
This is motion 50 in the
http://grouper.ieee.org/groups/1788/private/Motions/AllMotions.html
As I understand it ..
A motion (47) to require both EDP and CA failed. 6 Yes, 30
No.
This motion (50) requires EDP but recommends CA.
I think that many of the arguments already presented in
motion 47 are relevant
even if CA is merely recommended. I repeat just one of them.
Regardless of the possible arguments for or against EDP as a
computational tool,
adding a functionality which has neither interval inputs nor
interval outputs and appears to require
a data object (extended accumulator) not otherwise present
in the standard, seems gratuitous in the
context of an interval standard.
So I vote No.
You are right, CA requires an extended accumulator. The EDP,
however, does not require it. In our first Pascal-XSC (1980) we
provided a function scalp(a,b,n) where a and b are real
vectors and n is an integer parameter which specifies the
roudning mode (to nearest, downwards, or upwards) and the
precision of the result after rounding (single, double,
quadruple, ..., or full precision). The method with which scalp
is implemented remains hidden allowing different ways of
realization.
Experience showed that the method which uses the long
accumulator is superior
I think that what you are providing is the logical fallacy known
as "argument from authority"
http://en.wikipedia.org/wiki/Argument_from_authority
You do not cite a comparison or even refer to other methods.
As a single point of comparison, it seems to
me EDP is inferior to the method I use in my implementation, which
is exact rational arithmetic. My method
does not suffer from the possibility of overflow or underflow, and
the method can be used for exact evaluation of
polynomials. It uses allocation of memory as necessary to store
large integers, and for small problems uses
very little memory or time.
It seems to me that one can construct polynomials p and values x
such that p(x)=0 and yet
the evaluation using Rump's method overflows.
There are other methods based on non-unique representation of
high-precision numbers by vectors of floats.
and
it allows realization by very fast hardware.
We have been over this before. No reference implementation can
rely on special hardware. If you
are proposing a method which is inferior to others unless it has
special hardware, then the method is
simply inferior.
Please see my mail of May 15, 2013 together with its
attachments! You really should not be shocked by the size of the
long accumulator. Including a very fast carry resolution
technique it requires less hardware resources than an adder tree
for fast multiplication which now is standard technology in
every modern processor. The EDP is the additive equivalent to
the adder tree for fast multiplication. It brings a similar
speed up and eliminates many unnecessary errors (cancellations)
in floating-point arithmetic.
If you consider the EDP as an isolated object it may look
gratuitous in the context of interval arithmetic. But the
reality is different. In earlier mails I mentioned many
applications of the EDP in interval analysis.
I
repeat a few of them:
-- guaranteed evaluation of polynomials or arithmetic
expressions. To see what you get without and with the EDP just
have a look at the explicit examples given in my book.
See my argument above.
--
Rump's method for inverting arbitrarily ill conditions matrices.
The method computes an enclosure of the solution.
Are you saying that the only way to invert ill-conditioned
matrices is by the method of Rump and the only way to implement
this method is by EDP?
--
the implmentation and applications of multiprecision interval
arithmetic, like accurate evaluation of polynomials in several
variables
If one is to support multiprecision arithmetic (arbitrary
precision?) then one automatically has a superset
of EDP, as in the MPFR library, or any implementation of ANSI
Common Lisp.
, or
-- computer assisted proof of the existence of a solution of a
partial differential equation.
In these and many other problems the EDP is an essntial
engredient.
Do you have a proof that one could not achieve the same result
without EDP? Only then would EDP be " essential."
Let me just discuss an explicit example more closely, computing
the dot product of two vectors with interval components. What
you would like to have is the least enclosure of the set of all
dot products of real vectors out of the two interval vectors.
Computing the interval dot product in conventional interval
arithmetic (what we are going to standardize in P1788) for each
interval product of two vector components you round the minimum
of all products of the interval bounds downwards and the maximum
upwards. During the following addition of the product to the
intermediate sum you again round the lower bound downwards and
the upper bound upwards. What you get is always different and
frequently a large superset of what you would like to have. With
the EDP you get the desired answer. The interval
multiplications deliver the minima and the maxima of the
products and these are now exactly accumulated by the EDP. The
sum of the minima would then be rounded downwards and the sum of
the maxima rounded upwards only once at the very end of the
accumulation. This process deliver the desired answer.
Aren't there alternatives to the EDP method that provide less
expensive solutions to the task which you have specified of
correctly rounded dot product?
Interval analysis has developed a wide variety of applications.
The standard P1788 should clearly state what the basic
engredients are. It is out of question that the EDP is one of
them. We shall never get it if we don't require it.
My concern is that if you require EDP you won't get a standard at
all.
On
the other side I am convinced that we shall get it if we require
it. Restricting P1788 to the four basic operations for intervals
would be a big mistake.
The standard has many more operations than 4, already!
Summary:
Motion 50 just requires an EDP. Its implementation is left open.
By not requiring its implementation via CA any risk that it
might damage the success of P1788 disappears.
So please vote YES on Motion 50.
With best regards
Ulrich
--
Karlsruher Institut für Technologie (KIT)
Institut für Angewandte und Numerische Mathematikg
D-76128 Karlsruhe, Germany
Prof. Ulrich Kulisch
Telefon: +49 721 608-42680
Fax: +49 721 608-46679
E-Mail: ulrich.kulisch@xxxxxxx
www.kit.edu
www.math.kit.edu/ianm2/~kulisch/
KIT - Universität des Landes Baden-Württemberg
und nationales Großforschungszentrum in der
Helmholtz-Gesellschaft
|