Browse Prior Art Database

Correctly Rounded Elementary Functions

IP.com Disclosure Number: IPCOM000100887D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 3 page(s) / 130K

Publishing Venue

IBM

Related People

Markstein, P: AUTHOR

Abstract

This article describes how to compute the common elementary functions (such as log, exp, sin, cos, atan) so that they can be rounded correctly. It is inspired by the work of Tuckerman, Gal, Gustafson, Agarwal, etc., who have led the way to 1 ulp accuracy. The implication of 1/2 ulp accuracy is that the IEEE standard could now be extended to include these elementary functions, and to specify exactly what they should produce, to the last bit. The resultant standard would vastly increase the range of computations over which identical results would be obtained by IEEE conforming hardware.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Correctly Rounded Elementary Functions

       This article describes how to compute the common
elementary functions (such as log, exp, sin, cos, atan) so that they
can be rounded correctly.  It is inspired by the work of Tuckerman,
Gal, Gustafson, Agarwal, etc., who have led the way to 1 ulp
accuracy.  The implication of 1/2 ulp accuracy is that the IEEE
standard could now be extended to include these elementary functions,
and to specify exactly what they should produce, to the last bit.
The resultant standard would vastly increase the range of
computations over which identical results would be obtained by IEEE
conforming hardware.

      The time to compute the elementary functions correctly rounded
is only modestly longer than the conventional computation.  The
conventional computation which we use as a springboard is the
Accurate Table Method of S. Gal and B. Bachelis (*).  The Accurate
Table Method is not only already very accurate, but it is also very
fast.  On the average, only 20% additional time is required to
guarantee precision to the last bit.

      In the Accurate Table Method, after range reduction, a function
evaluation f(x) is performed as:
   f(x) = f(a) + g(x-a)
where  a-x  is chosen to be suitably small (usually no larger than
2**-9 x), and a has been chosen such that f(a) is close to a number
that can be represented in the machine. In fact, f(a) is such that
the next n bits beyond those represented in the machine are all zero.
Thus, f(a) is precise to n bits more than the machine architecture
ostensibly allows. g(x-a) is then computed via a minimax polynomial
to about the same precision as the true precision of f(a).  The
addition of f(a) and g(x-a) is achieved easily since the low-order n
bits of f(a) are zero.

                            (Image Omitted)

 f(a)      Machine representation    0000000000
 g (x-a)                  Machine Representation
      discriminant bits                 xxxxxxxxxx

      The first n bits of f(a) + g(x-a) that do not fit into a
machine- representable word are called the discriminant bits of the
result.  These bits occur exactly in g(x-a), because the
corresponding bits of f(a) are all zeros.  Thus, unless the leading
n-1 bits of the discriminant are 100...0 or 011...1 (these two bit
patterns are called the "critical patterns"), the errors in f(a) and
g(x-a) together cannot affect whether the high-order bit of the
discriminant is zero or one, and the IEEE hardware itself will yield
the correctly rounded result when adding f(a) and g(x-a).

      Thus, if n is 9, for example, only two out of 512 possible
discriminants leaves any doubt about the final rounding.  Thus, in
99.4% of all cases, it would suffice to check that the discriminant
is not a critical pattern. Such a check can be made in a few cycles
of existing machines, or even built into the floating add instruction
of newer...