Machine epsilon

From HandWiki
Short description: Upper bound on the relative error due to rounding in floating-point arithmetic

Machine epsilon or machine precision is an upper bound on the relative approximation error due to rounding in floating point arithmetic. This value characterizes computer arithmetic in the field of numerical analysis, and by extension in the subject of computational science. The quantity is also called macheps and it has the symbols Greek epsilon [math]\displaystyle{ \varepsilon }[/math].

There are two prevailing definitions. In numerical analysis, machine epsilon is dependent on the type of rounding used and is also called unit roundoff, which has the symbol bold Roman u. However, by a less formal, but more widely used definition, machine epsilon is independent of rounding method and may be equivalent to u or 2u.

Values for standard hardware arithmetics

The following table lists machine epsilon values for standard floating-point formats. Each format uses round-to-nearest.

IEEE 754 - 2008 Common name C++ data type Base [math]\displaystyle{ b }[/math] Precision [math]\displaystyle{ p }[/math] Machine epsilon[lower-alpha 1] [math]\displaystyle{ b^{-(p-1)}/2 }[/math] Machine epsilon[lower-alpha 2] [math]\displaystyle{ b^{-(p-1)} }[/math]
binary16 half precision N/A 2 11 (one bit is implicit) 2−11 ≈ 4.88e-04 2−10 ≈ 9.77e-04
binary32 single precision float 2 24 (one bit is implicit) 2−24 ≈ 5.96e-08 2−23 ≈ 1.19e-07
binary64 double precision double 2 53 (one bit is implicit) 2−53 ≈ 1.11e-16 2−52 ≈ 2.22e-16
extended precision, long double _float80[1] 2 64 2−64 ≈ 5.42e-20 2−63 ≈ 1.08e-19
binary128 quad(ruple) precision _float128[1] 2 113 (one bit is implicit) 2−113 ≈ 9.63e-35 2−112 ≈ 1.93e-34
decimal32 single precision decimal _Decimal32[2] 10 7 5 × 10−7 10−6
decimal64 double precision decimal _Decimal64[2] 10 16 5 × 10−16 10−15
decimal128 quad(ruple) precision decimal _Decimal128[2] 10 34 5 × 10−34 10−33
  1. According to formal definition—used by Prof. Demmel, LAPACK and Scilab
  2. According to widespread variant definition—used by per Prof. Higham; ISO C standard; Ada, C, C++, Python and Rust language constants; Mathematica, MATLAB and Octave; and various textbooks

Formal definition

Rounding is a procedure for choosing the representation of a real number in a floating point number system. For a number system and a rounding procedure, machine epsilon is the maximum relative error of the chosen rounding procedure.

Some background is needed to determine a value from this definition. A floating point number system is characterized by a radix which is also called the base, [math]\displaystyle{ b }[/math], and by the precision [math]\displaystyle{ p }[/math], i.e. the number of radix [math]\displaystyle{ b }[/math] digits of the significand (including any leading implicit bit). All the numbers with the same exponent, [math]\displaystyle{ e }[/math], have the spacing, [math]\displaystyle{ b^{e-(p-1)} }[/math]. The spacing changes at the numbers that are perfect powers of [math]\displaystyle{ b }[/math]; the spacing on the side of larger magnitude is [math]\displaystyle{ b }[/math] times larger than the spacing on the side of smaller magnitude.

Since machine epsilon is a bound for relative error, it suffices to consider numbers with exponent [math]\displaystyle{ e=0 }[/math]. It also suffices to consider positive numbers. For the usual round-to-nearest kind of rounding, the absolute rounding error is at most half the spacing, or [math]\displaystyle{ b^{-(p-1)}/2 }[/math]. This value is the biggest possible numerator for the relative error. The denominator in the relative error is the number being rounded, which should be as small as possible to make the relative error large. The worst relative error therefore happens when rounding is applied to numbers of the form [math]\displaystyle{ 1+a }[/math] where [math]\displaystyle{ a }[/math] is between [math]\displaystyle{ 0 }[/math] and [math]\displaystyle{ b^{-(p-1)}/2 }[/math]. All these numbers round to [math]\displaystyle{ 1 }[/math] with relative error [math]\displaystyle{ a/(1+a) }[/math]. The maximum occurs when [math]\displaystyle{ a }[/math] is at the upper end of its range. The [math]\displaystyle{ 1+a }[/math] in the denominator is negligible compared to the numerator, so it is left off for expediency, and just [math]\displaystyle{ b^{-(p-1)}/2 }[/math] is taken as machine epsilon. As has been shown here, the relative error is worst for numbers that round to [math]\displaystyle{ 1 }[/math], so machine epsilon also is called unit roundoff meaning roughly "the maximum error that can occur when rounding to the unit value".

Thus, the maximum spacing between a normalised floating point number, [math]\displaystyle{ x }[/math], and an adjacent normalised number is [math]\displaystyle{ 2 \varepsilon |x| }[/math].[3]

Arithmetic model

Numerical analysis uses machine epsilon to study the effects of rounding error. The actual errors of machine arithmetic are far too complicated to be studied directly, so instead, the following simple model is used. The IEEE arithmetic standard says all floating-point operations are done as if it were possible to perform the infinite-precision operation, and then, the result is rounded to a floating-point number. Suppose (1) [math]\displaystyle{ x }[/math], [math]\displaystyle{ y }[/math] are floating-point numbers, (2) [math]\displaystyle{ \bullet }[/math] is an arithmetic operation on floating-point numbers such as addition or multiplication, and (3) [math]\displaystyle{ \circ }[/math] is the infinite precision operation. According to the standard, the computer calculates:

[math]\displaystyle{ x \bullet y = \mbox {round} (x \circ y) }[/math]

By the meaning of machine epsilon, the relative error of the rounding is at most machine epsilon in magnitude, so:

[math]\displaystyle{ x \bullet y = (x \circ y)(1 + z) }[/math]

where [math]\displaystyle{ z }[/math] in absolute magnitude is at most [math]\displaystyle{ \varepsilon }[/math] or u. The books by Demmel and Higham in the references can be consulted to see how this model is used to analyze the errors of, say, Gaussian elimination.

Variant definitions

The IEEE standard does not define the terms machine epsilon and unit roundoff, so differing definitions of these terms are in use, which can cause some confusion.

The formal definition for machine epsilon is the one used by Prof. James Demmel in lecture scripts,[4] the LAPACK linear algebra package,[5] numerics research papers[6] and some scientific computing software.[7] Most numerical analysts use the words machine epsilon and unit roundoff interchangeably with this meaning.

This alternative definition is much more widespread outside academia: machine epsilon is the difference between 1 and the next larger floating point number.

By this definition, [math]\displaystyle{ \varepsilon }[/math] equals the value of the unit in the last place relative to 1, i.e. [math]\displaystyle{ b^{-(p-1)} }[/math] (where [math]\displaystyle{ b }[/math] is the base of the floating point system and [math]\displaystyle{ p }[/math] is the precision) and the unit roundoff is u[math]\displaystyle{ \, = \varepsilon/2 }[/math], assuming round-to-nearest mode, and u[math]\displaystyle{ \, = \varepsilon }[/math], assuming round-by-chop.

The prevalence of this definition is rooted in its use in the ISO C Standard for constants relating to floating-point types[8][9] and corresponding constants in other programming languages.[10][11][12] It is also widely used in scientific computing software,[13][14][15] and in the numerics and computing literature.[16][17][18][19]

How to determine machine epsilon

Where standard libraries do not provide precomputed values (as <float.h> does with FLT_EPSILON, DBL_EPSILON and LDBL_EPSILON for C and <limits> does with std::numeric_limits<T>::epsilon() in C++), the best way to determine machine epsilon is to refer to the table, above, and use the appropriate power formula. Computing machine epsilon is often given as a textbook exercise. The following examples compute machine epsilon in the sense of the spacing of the floating point numbers at 1 rather than in the sense of the unit roundoff.

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 not be 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 [math]\displaystyle{ 1 + \varepsilon }[/math] accuracy directly supported by the processor (or coprocessor), not some [math]\displaystyle{ 1 + \varepsilon }[/math] accuracy supported by a specific compiler for a specific operating system, unless it's known to use the best format.

IEEE 754 floating-point formats have the property that, when reinterpreted as a two's complement integer of the same width, they monotonically increase over positive values and monotonically decrease over negative values (see the binary representation of 32 bit floats). They also have the property that [math]\displaystyle{ 0 \lt |f(x)| \lt \infty }[/math], and [math]\displaystyle{ |f(x+1) - f(x)| \ge |f(x) - f(x-1)| }[/math] (where [math]\displaystyle{ f(x) }[/math] is the aforementioned integer reinterpretation of [math]\displaystyle{ x }[/math]). In languages that allow type punning and always use IEEE 754–1985, we can exploit this to compute a machine epsilon in constant time. For example, in C:

typedef union {
  long long i64;
  double d64;
} dbl_64;

double machine_eps (double value)
{
    dbl_64 s;
    s.d64 = value;
    s.i64++;
    return s.d64 - value;
}

This will give a result of the same sign as value. If a positive result is always desired, the return statement of machine_eps can be replaced with:

return (s.i64 < 0 ? value - s.d64 : s.d64 - value);

Example in Python:

def machineEpsilon(func=float):
    machine_epsilon = func(1)
    while func(1)+machine_epsilon != func(1):
        machine_epsilon_last = machine_epsilon
        machine_epsilon = func(machine_epsilon) / func(2)
    return machine_epsilon_last


64-bit doubles give 2.220446e-16, which is 2−52 as expected.

Approximation

The following simple algorithm can be used to approximate[clarification needed] the machine epsilon, to within a factor of two (one order of magnitude) of its true value, using a linear search.

epsilon = 1.0;

while (1.0 + 0.5 * epsilon) ≠ 1.0:
    epsilon = 0.5 * epsilon

The machine epsilon, [math]\displaystyle{ \varepsilon_\text{mach} }[/math] can also simply be calculated as two to the negative power of the number of bits used for the mantissa.

[math]\displaystyle{ \varepsilon_\text{mach}\ =\ 2^{-\text{bits used for magnitude of mantissa}} }[/math]

Relationship to absolute relative error

If [math]\displaystyle{ y }[/math] is the machine representation of a number [math]\displaystyle{ x }[/math] then the absolute relative error in the representation is [math]\displaystyle{ \left| \dfrac{x - y}{x} \right| \leq \varepsilon_\text{mach}. }[/math][20]

Proof

The following proof is limited to positive numbers and machine representations using round-by-chop.

If [math]\displaystyle{ x }[/math] is a positive number we want to represent, it will be between a machine number [math]\displaystyle{ x_{b} }[/math] below [math]\displaystyle{ x }[/math] and a machine number [math]\displaystyle{ x_{u} }[/math] above [math]\displaystyle{ x }[/math].

If [math]\displaystyle{ x_{b} = \left( 1.b_{1}b_{2} \ldots b_{m} \right)_{2} \times 2^{k} }[/math], where [math]\displaystyle{ m }[/math] is the number of bits used for the magnitude of the significand, then:

[math]\displaystyle{ \begin{align} x_{u} &= \left[ (1.b_{1}b_{2}\ldots b_{m})_{2} + (0.00 \ldots 1)_{2} \right] \times 2^{k}\\ &= \left[ (1.b_{1}b_{2} \ldots b_{m})_{2} + 2^{- m} \right] \times 2^{k}\\ &= (1.b_{1}b_{2} \ldots b_{m})_{2} \times 2^{k} + 2^{- m} \times 2^{k}\\ &= (1.b_{1}b_{2} \ldots b_{m})_{2} \times 2^{k} + 2^{- m + k}. \end{align} }[/math]

Since the representation of [math]\displaystyle{ x }[/math] will be either [math]\displaystyle{ x_b }[/math] or [math]\displaystyle{ x_u }[/math],

[math]\displaystyle{ \begin{align} \left| x - y \right| &\leq \left| x_{b} - x_{u} \right|\\ &= 2^{- m + k} \end{align} }[/math] [math]\displaystyle{ \begin{align} \left| \frac{x - y}{x} \right| &\leq \frac{2^{- m + k}}{x}\\ &\leq \frac{2^{- m + k}}{x_{b}}\\ &= \frac{2^{- m + k}}{(1 \cdot b_{1}b_{2} \ldots b_{m})_{2}2^{k}}\\ &= \frac{2^{- m}}{(1 \cdot b_{1}b_{2} \ldots b_{m})_{2}}\\ &\leq 2^{- m} = \varepsilon_\text{mach}. \end{align} }[/math]

Although this proof is limited to positive numbers and round-by-chop, the same method can be used to prove the inequality in relation to negative numbers and round-to-nearest machine representations.

See also

  • Floating point, general discussion of accuracy issues in floating point arithmetic
  • Unit in the last place (ULP)

Notes and references

  1. 1.0 1.1 Floating Types - Using the GNU Compiler Collection (GCC)
  2. 2.0 2.1 2.2 Decimal Float - Using the GNU Compiler Collection (GCC)
  3. "Basic Issues in Floating Point Arithmetic and Error Analysis". University of California, Berkeley. 21 October 1999. http://www.cs.berkeley.edu/~demmel/cs267/lecture21/lecture21.html. "The distance between 1 and the next larger floating point number is 2*macheps." 
  4. "Basic Issues in Floating Point Arithmetic and Error Analysis". 21 Oct 1999. http://www.cs.berkeley.edu/~demmel/cs267/lecture21/lecture21.html. 
  5. "LAPACK Users' Guide Third Edition". 22 August 1999. http://www.netlib.org/lapack/lug/node74.html. 
  6. "David Goldberg: What Every Computer Scientist Should Know About Floating-Point Arithmetic, ACM Computing Surveys, Vol 23, No 1, March 1991". https://www.ualberta.ca/~kbeach/phys420_580_2010/docs/ACM-Goldberg.pdf. 
  7. "Scilab documentation - number_properties - determine floating-point parameters". http://help.scilab.org/docs/5.3.3/en_US/number_properties.html. 
  8. Jones, Derek M. (2009). The New C Standard - An Economic and Cultural Commentary. p. 377. http://www.coding-guidelines.com/cbook/cbook1_2.pdf. 
  9. "float.h reference at cplusplus.com". http://www.cplusplus.com/reference/cfloat/. 
  10. "std::numeric_limits reference at cplusplus.com". http://www.cplusplus.com/reference/limits/numeric_limits/. 
  11. "Python documentation - System-specific parameters and functions". https://docs.python.org/3/library/sys.html. 
  12. Template:Cite tech report
  13. "Mathematica documentation: $MachineEpsilon". http://reference.wolfram.com/mathematica/ref/$MachineEpsilon.html. 
  14. "Matlab documentation - eps - Floating-point relative accuracy". Archived from the original on 2013-08-07. https://web.archive.org/web/20130807071540/http://www.mathworks.de/de/help/matlab/ref/eps.html. 
  15. "Octave documentation - eps function". http://octave.sourceforge.net/octave/function/eps.html. 
  16. Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 27–28. 
  17. Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2000). Numerical Mathematics. Springer. p. 49. ISBN 0-387-98959-5. http://www.techmat.vgtu.lt/~inga/Files/Quarteroni-SkaitMetod.pdf. Retrieved 2013-04-11. 
  18. Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P.. Numerical Recipes. p. 890. 
  19. Engeln-Müllges, Gisela; Reutter, Fritz (1996). Numerik-Algorithmen. p. 6. ISBN 3-18-401539-4. 
  20. "Machine Epsilon Value for IEEE Double Precision Standard Alternative Proof Using Relative Error". 12 October 2020. https://math.stackexchange.com/questions/3861976/machine-epsilon-value-for-ieee-double-precision-standard-alternative-proof-using. Retrieved 5 May 2022. 
  • Anderson, E.; LAPACK Users' Guide, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, third edition, 1999.
  • Cody, William J.; MACHAR: A Soubroutine to Dynamically Determine Machine Parameters, ACM Transactions on Mathematical Software, Vol. 14(4), 1988, 303–311.
  • Besset, Didier H.; Object-Oriented Implementation of Numerical Methods, Morgan & Kaufmann, San Francisco, CA, 2000.
  • Demmel, James W., Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
  • Higham, Nicholas J.; Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, second edition, 2002.
  • Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; and Flannery, Brian P.; Numerical Recipes in Fortran 77, 2nd ed., Chap. 20.2, pp. 881–886
  • Forsythe, George E.; Malcolm, Michael A.; Moler, Cleve B.; "Computer Methods for Mathematical Computations", Prentice-Hall, ISBN:0-13-165332-6, 1977

External links

it:Epsilon di macchina