Re: Meeting the Scope and Purpose of P754

[Guillaume Melquiond <guillaume.melquiond@xxxxxxxxxxx>]

Le samedi 14 juillet 2007 à 09:18 -0400, Michel Hack a écrit :
> Florent de Dinechin addressed two separate reproducibility requirements.
>
> > Background: we are designing portable, correctly-rounded elementary
> > functions, for which reproducibility is simply a must.
>
> Not at all!  This is precisely the situation where the final result will
> be exactly reproducible regardless of how intermediate computations are
> done, provided of course that the algorithm takes floating-point behaviour
> into account, as a professional-quality program like Arnaire would.

You are right, it is possible to write an algorithm that takes into
account bugs of the low-level floating-point architecture. For example,
there is a mathematical library (written by Sun I believe) that produces
correct results whatever intermediate results are rounded. Downside of
the approach, the library is slow, really. So this is the point you seem
to have missed: Arenaire could indeed write libraries that do not rely
on bit-to-bit reproducibility, but they would be a lot slower. So, as
strange as it may seem, bit-to-bit reproducibility makes these numerical
algorithms _faster_. You don't have to read any further if you are
already convinced.

To explain my point, I will expand a bit on the topic of igher-precision
arithmetic, as it is a good example for showing what the performance
costs of not having reproducible intermediate results are. In order to
compute its correctly-rounded results in double precision, CRlibm needs
to compute the intermediate results with a higher precision.
Intermediate results are stored as three floating-point numbers. So it
amounts to about 150 bits of precision (quadruple precision is not even
enough for correctly rounding mathematical functions in double
precision).

It is true that the library could probably afford to have
non-reproducible results for the last few bits of the least significant
of the three numbers encoding an intermediate result. But you can't
afford to change one single bit on the most significant two
floating-point numbers. An additional difficulty is that the middle
number and the lower number are no different with respect to their usage
patterns. So without knowing what the algorithm does, a compiler has no
way to detect that it can produce less accurate code for the lower
number, and an indiscriminate optimization would break the middle
number.

Now, how do we obtain these floating-point numbers? (These tuples of
numbers are close to pseudo-expansions, so people can refer to Priest's
work in 1991 for early details.) You need to perform error-free
transformations, e.g. two-sums as mentioned. But local reproducibility
is not enough. Indeed, a two-sum takes two numbers as inputs and returns
two numbers as outputs, while a triple-double sum has to support six
numbers as inputs and three as outputs.  So the reproducibility
requirement extends to relatively large blocks of code.

What are the costs of these error-free transformations? If you have
ideal IEEE-754 semantic, then you can use Knuth's version of the two-sum
operator. It is straight-line code with only a few arithmetic
operations. But if you have some doubts on the intermediate results, you
have to use a more robust algorithm, e.g. Priest's one. Priest's
algorithm performs twice as many operations and it contains some
conditional branches. Needless to say, Knuth's algorithm is several
times faster on any usual architecture.

What about the two-mul operator? If the architecture has a slow fma (or
none), then you will choose Dekker's operator to implement it, which in
turn relies on Veltkamp's algorithm. Let's suppose that an
infinitely-precise intermediate value is exactly the midpoint between
two consecutive floating-point numbers. If you don't choose the
754-mandated value, you do not cause a bigger error on the intermediate
value (it's half an ulp in both cases), but the final result of the
two-mul operator is plain wrong. So for this algorithm, it is not just a
matter of bounding the intermediate error, it is about getting the
bit-to-bit correct result. Once again, if you are not sure how the
intermediate computations are performed, you have to use more
complicated algorithms.

In conclusion, bit-to-bit reproducibility makes it possible to write
fast mathematical libraries. Without it, the algorithms are several
times slower, because they have to take into account the discrepancies
that may occur in the course of the computations.

Best regards,

Guillaume

PS: Higher-precision arithmetic is not used just by elementary function
libraries. For example, double-double and quad-double arithmetic are
also used by some linear algebra packages, when performing computations
on floating-point matrices.