Re: Motion P1788/M0045.02:DotProduct -- YES
On 7/12/2013 1:06 AM, Vincent Lefevre wrote:
My vote is YES on Motion 45.02.
It is an improvement. But I would rather see CA out of the standard...
I would prefer a separate "suggestions for implementation" section.
More specifically for interval arithmetic it seems to me that there are
several technologies
for achieving the same thing as CA, and if the goal is to implement
interval arithmetic most
efficiently or most accurately, then in some languages, there may be
better ways.
For example, languages which provide exact (arbitrary precision)
rational arithmetic or
arbitrary precision floats -- each of which is a superset of
complete arithmetic, may provide better solutions.
Since the arbitrary precision integer or rational number arithmetic is
typically arranged
to grow as needed, short results are better accommodated. Thus to
multiply 0.5 by 0.5
or even 5 by 5 it is hardly efficient to allocate 4288 bits.
What languages already allow for arbitrary integers and rational? There
are the GMP libraries
mpz (integers) and mpq (rationals) that -- although they do not need
special hardware-- come
with special assembler-coded routines for certain architectures or
sub-implementations of
architectures that, in my experience, can provide substantial (10X or
more) speedup from
the same procedures in pure C. Not only do they support the limited
cross-product of double-floats,
but allow multiplication of arbitrary precision rationals directly.
It is also possible to create a similarly limited simulation of CA by
using the mpfr library.
(There is of course mpfi for intervals...)
See
http://gmplib.org/manual/Language-Bindings.html#Language-Bindings
for a list of the more than 18 languages, often with multiple
implementations
that offer access to GMP, though some of these may only be for the
integer (mpz) library.
Also computer "algebra" languages that offer numerical computation too
tend to include
exact rationals, so Mathematica, Maple, Axiom, Fricas, Reduce, Mathics,
Yacas. These all
make available a superset of CA. Also some of these systems already
offer interval
arithmetic directly, though usually with a few features at odds with
requirements currently
in the proposed standard.
Writing an exact dot product of floats in one of these languages can be
quite simple, or
it can be elaborately "optimized" as in other contexts where
floating-point mantissas are split up
to avoid long multiplications, etc.
As an example of a simple and complete (but not "optimal") program,
here's one in lisp:
(defun exactdotproduct(A B)
(reduce #'+ (map 'list #'(lambda(x y)(* (rational x)(rational y))) A B)))
This program allows the input lists or vectors A B to include any real
number types:
single/double/extended floats, rationals, integers. It converts each
number to an exact
rational, multiplies them in pairs and sums the results to produce a
rational number which
can be converted (with rounding) to any float type. This 2 line program
is easy in lisp,
but that is because there already is a fully supported data type of
arbitrary precision
rational with arithmetic, comparisons, conversions, etc.
So I see the argument against requiring EDP and CA:
* It is not actually required to implement interval arithmetic,
* It takes extra space in the standard textually as well as intellectually,
* It requires introduction into the host language of another data type
(not an interval).
* There appears to be nothing that can be done with this data type
except to convert
it (using programs unspecified in the standard....) to one of the
float types rounded
up or down or nearest. Of course more could be done, but the
standard document
would have to be enlarged to incorporate that.
I have no problem with listing CA etc in a section on implementation
suggestions.