Re: exact dot product
Ulrich, Dan, P-1788,
OK, now I think I understand what you mean by "complete arithmetic"; let me
paraphrase: If we have a long chain of operations with inputs (base nodes in the
expression tree) in one of the basic floating point formats, then the arithmetic
is done in such a way that the output (leaf of the expression tree) is the
exact result. This exact result can then be rounded into the floating point type.
Personal opinion (not as acting chair): I don't see it as within the scope of
P-1788 to specify the number of bytes needed, or the exact bit pattern of
any data type to effect this result. However, it is possible for us to
specify a data type that will hold the exact result, and we may give (in
non-normative explanatory text) the long accumulator as an example.
(Again as acting chair): The questions I have for the working group are:
* Do we interpret our decision in Motion 9 to mean we just want an exact
dot product, or do we interpret it to mean we want both an exact
dot product and complete arithmetic?
* If we just want an "exact" dot product, and do not intend to define
an "exact" data type, it is possible to use 754-language, which had
registers and memory storage patterns in mind: The rounded-down,
rounded-up, rounded-to-nearest, or rounded-towards-zero result of
the dot product would be "as if" the exact result were first computed,
and the dot product would be a required function with the same requirements
as the other optional functions. However, if we mean by "exact dot product"
that a representation of the exact result be available, we would need to
specify how that is done, and the situation would be more similar to
the situation where we require complete arithmetic.
So: (1) Do we want complete arithmetic or just an exact dot product?
(2) If we just want an exact dot product, do we want access to a
representation of the exact result?
The problem I have is that Motion 9, in the form of a scholarly paper,
did not concisely specify "shall", "may", and "recommend". P-1788 could
clearly answer my questions (1) and (2) with one or two short motions.
However, as acting chair, Roberts' Rules states I cannot make motions.
Does anyone wish to make a motion concerning this issue?
Best regards,
Baker
(acting chair, P-1788)
On 05/22/2013 04:54 AM, Ulrich Kulisch wrote:
Baker,
"Complete arithmetic" may appear as something that is new. The technology, however, is not new at all. It was already available on old calculators. See the right upper corner of the poster. In the XSC-languages the format was called
"dotprecision". You call it the "long accumulator", and in the paper [5] on the poster something very similar is called "staggered prercision" which, if I remember it correctly goes back to Hans Stetter. The wording "complete arithmetic"
was suggested by Neville Holmes (Computers and People, John Wiley, 2006) a very experienced computer science journalist and long term systems engineer at IBM. I mention him in the preface of my book and in the foreword to the second edition.
There are two things that should not be confused:
a) the exact dot product and
b) a correctly or faithfully rounded dot product.
From a) follows b) easily. The opposite is not true. So the number of applications of a) is naturally larger than that of b). The IFIP letters to IEEE 754 and to IEEE P1788 require an exact dot product. It is indeed an essential engredient
of verified computing.
Several partcular applications of the exact dot product are listed in the paper: "Very fast and exact accumulation of products" which was attached to my mail of May 18, 2013. See also the poster and my book.
The process of iterative refinement or defect correction, for instance, is composed of scalar products. If these are computed exactly a verified solution of a linear system can be computed even in extremely ill-conditioned cases, where the
Krawczyk-operator fails to find a verified solution, by Rump's method. Another very powerful application is dynamic precision or long real interval arithmetic. With it the result of practically every arithmetic expression can be guaranteed
to a number of correct digits.
In numerical analysis the dot product is ubiquetous. The simplest and fastest way for computing a dot product is to compute it exactly. By pipelining it can be computed in the time the procesor needs to read the data, i.e., it comes with
utmost speed. Any method like b) that just computes an approximation also has to consider the relative values of the summands. This results in a more complicated method. Complete arithmetic uses a data format "complete". You call it a "long
accumulator". The result of complete arithmetic is always exact; it is complete, not truncated. Not a single bit is lost. A variable of type complete is a fixed-point word wide enough to allow exact accumulation (continued summation) of
floating-point numbers and of simple products of such numbers. If register space for the complete format is available complete arithmetic is very fast. The arithmetic needed to perform complete arithmetic is not much different from that
available in a conventional CPU. In the case of the IEEE double precision format a complete register consists of about 1/2 K bytes. Its length is independent of the number of summands that are to be added. It can be kept in main memory, in
cache memory, or ideally in register memory.
Best wishes
Ulrich
Am 21.05.2013 03:57, schrieb Ralph Baker Kearfott:
Dan (and P-1788),
If I may summarize (and Ulrich can correct me if I am wrong),
"complete arithmetic" Involves using a "long accumulator"
(something like 1000 bits for double precision), doing the
summation (e.g. for the dot product, but also for other operations)
in the long accumulator, then rounding. However, there are
other ways of obtaining a correctly rounded (or the slightly
less stringent faithfully rounded) dot product, and I am
hoping we can clarify exactly what the intent of the position
from motion 29 is in this regard.
Baker
On 05/20/2013 01:19 PM, Dan Zuras Intervals wrote:
Date: Sun, 19 May 2013 16:37:48 -0500
From: Ralph Baker Kearfott<rbk@xxxxxxxxxxxxx>
To: Dan Zuras Intervals<intervals08@xxxxxxxxxxxxxx>
CC: Ulrich Kulisch<ulrich.kulisch@xxxxxxx>,stds-1788@xxxxxxxxxxxxxxxxx
Subject: Re: exact dot product
Dan (and P-1788),
Was complete arithmetic (in addition to exact dot
product) also discussed in 754?
Baker
Baker,
I must confess I am not quite sure what you mean by "complete
arithmetic" in this context. But if it is an exact arithmetic
or an arithmetic with an exact part & a smaller unknown part,
then YES, it was discussed many times & in many different contexts.
Also, exact dot product in the context of exact products together
with correct sums which are exact enough to round correctly all
the time, these were discussed at length. Ulrich needed them for
his work & we were willing to provide them.
(Actually, in the discussion it often came up that someone wanted
NOT to provide them from time to time due to their difficulty.
But eventually a paper was published that put a bound on the extra
precision needed which pretty much killed the objection. Alas,
the paper hit the streets too late for us to change the text of
the 754 standard. It will happen to you too in some context or
another. Don't be in too much of a hurry.)
This notion of "complete arithmetic" was also often discussed in
the context of intervals. The notion was to compare two numbers
by having an exact part & a much smaller interval part such that
the comparison was clear once you subtracted out the exact parts.
That is, either it was away from zero or not by looking at what
amounted to only the interval parts. It was necessary to carry
out such a comparison by having either exact arithmetic or some
sort of arithmetic that accumulated its error in the interval
part. It was the only way to decide the answer.
Does this answer your "complete arithmetic" questions?
Dan
--
Karlsruher Institut für Technologie (KIT)
Institut für Angewandte und Numerische Mathematik
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
--
---------------------------------------------------------------
Ralph Baker Kearfott, rbk@xxxxxxxxxxxxx (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------