Correlated floating point errors

[uunet!cwi.nl!Dik.Winter]

Not exactly correlated roundings, but related to non-random roundoff.
[Mind, this is completely from years old memory...]

 > >...This is a key insight of many algorithms that
 > >obtain the benefit of higher precision without the cost, such as 
 > >"doubled double" quad.   This is not a bug in those algorithms, but an
 > >exploitation of an important feature of conventional floating-point 
 > >arithmetic: roundoff is NOT random. 

 >     I'd like to find out more about the use of correlated floating point
 > errors and how they are used in numerical algorithms. Can anyone provide
 > a reference?

There is an article by T.J.Dekker in CACM of around 1965-1966 about
doubling the precision of f-p operations.  As far as I know these
algorithms are basic on the RS/6000 to get quad precision.  The basic
operations are two; one to get the exact sum of two f-p numbers, the
second to get the exact product of two f-p numbers.  A double f-p
number is represented by two normal f-p numbers, the first (the head)
much larger than the second (the tail); they need not have the same
sign.  The exact mathematical sum of the two represents the double
number, the head represents the double number to reduced precision.
I will not bore you with the multiply, but the add goes like this:
    void adddp(double x, double y, double *z, double *zz)
    {
        *z = x + y;
        if(fabs(x) >= fabs(y)) {
            *zz = x - *z + y;
        } else {
            *zz = y - *z + x;
        }
    }

 > 	If the correaltion of floating point errors is due to round off I
 > wonder if these correlations are dependant on the rounding mode that is
 > used.  Is the performance of algorithms that depend upon these correlations
 > affected when the rounding mode is changed?

There is certainly a correlation.  The above routine will not work if
some form of truncation is used.  It works on a "faithful" implementation,
i.e. each operation rounds to nearest (check that ;-)).  (Slightly less
than IEEE but near.)

[Oh sweet memories.  I used this stuff heavily 23 years ago; even implemented
it on a HP65.  So, yes, it is implementable on non-binary machines.  And on
occasion I still do use it.]

dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dikacwi.nl