Machine epsilon

From Wikipedia, the free encyclopedia

In floating point arithmetic, the machine epsilon (also called macheps, machine precision or unit roundoff) is, for a particular floating point unit, the difference between 1 and the smallest exactly representable number greater than one.

Contents

[edit] Example

An IEEE 754 single precision floating point number has 24 bits of mantissa, including the leading unit digit. The number 1 is represented with an unbiased exponent of 0 and a mantissa of 1.00000000000000000000000 in binary. The next largest representable number has an exponent of 0 and a mantissa of 1.00000000000000000000001. The difference between these numbers is 0.00000000000000000000001, or 2−23. This is the machine epsilon of a floating point unit which uses IEEE single-precision floating point arithmetic. In general, for a floating point type with a base b and a mantissa of p digits, the epsilon is εmach = b1-p.

[edit] Other definitions

The machine epsilon is sometimes defined as the smallest positive number which, when added to 1, yields a result other than one. Unlike the definition above, this value depends on the rounding mode. For IEEE single precision in the most common rounding mode (round to even), this value is 2−24 + 2−47, or slightly more than half the value by the definition above. For rounding toward +∞ the value is the smallest representable positive number (2−149, a denormal), while for rounding toward -∞ or toward zero it coincides with the earlier definition.

Some documents mistakenly use this definition when the other is intended. For example, both the GNU libc manual[1] and Microsoft Visual C++ documentation[2] define the constant FLT_EPSILON in this way, in conflict with the ISO C standard[3], which mandates the definition at the head of this article, and with their own implementations, which follow the standard.

[edit] How to determine the macheps

Note that results depend on the particular floating-point format used, such as float, double, long double, or similar as supported by the programming language, the compiler, and the runtime library for the actual platform.

Some formats supported by the processor might be not supported by the chosen compiler and operating system. Other formats might be emulated by the runtime library, including arbitrary-precision arithmetic available in some languages and libraries.

In a strict sense the term machine epsilon means the 1+eps accuracy directly supported by the processor (or coprocessor), not some 1+eps accuracy supported by a specific compiler for a specific operating system, unless it's known to use the best format.

A trivial example is the machine epsilon for integer arithmetic on processors without floating point formats; it is 1, because 1+1=2 is the smallest integer greater than 1.

The following C program does not actually determine the machine epsilon; rather, it determines a number within a factor of two (one order of magnitude) of the true machine epsilon, using a linear search.

#include <stdio.h>
 
 int main( int argc, char **argv )
 {
    float machEps = 1.0f;
 
    printf( "current Epsilon, 1 + current Epsilon\n" );
    do {
       printf( "%G\t%.20f\n", machEps, (1.0f + machEps) );
       machEps /= 2.0f;
       // If next epsilon yields 1, then break, because current
       // epsilon is the machine epsilon.
    }
    while ((float)(1.0 + (machEps/2.0)) != 1.0);
 
    printf( "\nCalculated Machine epsilon: %G\n", machEps );
    return 0;
 }

Abridged Output

$ gcc machine_epsilon.c; ./a.out
 current Epsilon, 1 + current Epsilon
1       2.00000000000000000000
0.5     1.50000000000000000000
...
0.000244141     1.00024414062500000000
0.00012207      1.00012207031250000000
6.10352E-05     1.00006103515625000000
3.05176E-05     1.00003051757812500000
1.52588E-05     1.00001525878906250000
7.62939E-06     1.00000762939453125000
3.8147E-06      1.00000381469726562500
1.90735E-06     1.00000190734863281250
9.53674E-07     1.00000095367431640625
4.76837E-07     1.00000047683715820312
2.38419E-07     1.00000023841857910156

Calculated Machine epsilon: 1.19209E-07

A similar, Java method:

   private void calculateMachineEpsilonFloat() {
       float machEps = 1.0f;

       do {
          machEps /= 2.0f;
       }
       while ((float)(1.0 + (machEps/2.0)) != 1.0);

       System.out.println( "Calculated Machine epsilon: " + machEps );
   }

[edit] References

  1. ^ GNU libc manual, section A.5.3.2, dated August 5, 2007, retrieved September 28, 2007.
  2. ^ Run-Time Library Reference: Data Type Constants, retrieved September 28, 2007.
  3. ^ WG14 N1124, section 5.2.4.2.2, paragraph 11.

[edit] External links

  • MACHAR, a routine (in C and Fortran) to "dynamically compute machine constants" (ACM algorithm 722)
Languages