Baker,
Motion 9 deals with an exact dot product.
The functionality
defined there is needed for getting close bounds in
many interval
computations.
The position paper first specifies the
data format complete and
then
requires a number of arithmetic operations. All these
operations are required
with shall.
They all deliver a complete format result.
Section
11.11.11 in Draft 7.1 of the standard IEEE P1788 (as shown
under Rationale of
Motion 44) shows that the requirements of the motion are
pretty well understood.
All operations are required with shall.
Three weak
points A), B) and C), however, need modification (see the
mails of Van Snyder
and myself of Oct. 11, 2012, and of Apr. 14, 2013).
A) The
third line of the first paragraph reads:
[4]
for the parent
format F of at least one such type.
This
requirement can be satisfied by providing complete arithmetic
for the data
format single precision only. This is not enough. The cited
text should be
replaced by:
[4]
for the parent
format F.
An
implementation shall
at least provide complete formats corresponding to
binary64 if it provides
binary floating-point arithmetic and decimal64 if it
provides decimal
floating-point. Complete formats corresponding to other
floating-point formats
may be provided.
B) The end
of the penultimate paragraph reads:
exactly
and rounds it
once to give a result of format F.
This
produces a rounded result of the dot product, while the exact
result is
required. The cited text should be replaced by:
exactly,
giving a
complete format result.
C) The
final paragraph should be replaced by:
The
result of all
operations may be converted if necessary to a specified
result format by
application of the convert-operation.
Best wishes
Ulrich
Am 23.05.2013 15:20, schrieb Ralph Baker Kearfott:
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
--
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
|