Floating-point arithmetic

Uses your system voice; voice and rate in settings.

Snapshot

≈ 30 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

, included floating-point arithmetic (replica on display at Deutsches Museum in Munich). In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a significand (a signed sequence of a fixed number of digits in some base) multiplied by an integer power of that base. Numbers of this form are called floating-point numbers. For example, the number 2469/200 is a floating-point number in base ten with five digits: 2469/200 = 12.345 = \! \underbrace{12345}_\text{significand} \! \times \! \underbrace{10}_\text{base}\!\!\!\!\!\!\!\overbrace{{}^{-3}}^{\text{exponent}} However, 7716/625 = 12.3456 is not a floating-point number in base ten with five digits—it needs six digits. The nearest floating-point number with only five digits is 12.346. And 1/3 = 0.3333… is not a floating-point number in base ten with any finite number of digits. In practice, most floating-point systems use base two, though base ten (decimal floating point) is also common. Floating-point arithmetic operations, such as addition and division, approximate the corresponding real number arithmetic operations by rounding any result that is not a floating-point number itself to a nearby floating-point number. For example, in a floating-point arithmetic with five base-ten digits, the sum 12.345 + 1.0001 = 13.3451 might be rounded to 13.345.…

, included floating-point arithmetic (replica on display at Deutsches Museum in Munich). In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a significand (a signed sequence of a fixed number of digits in some base) multiplied by an integer power of that base. Numbers of this form are called floating-point numbers. For example, the number 2469/200 is a floating-point number in base ten with five digits: 2469/200 = 12.345 = \! \underbrace{12345}_\text{significand} \! \times \! \underbrace{10}_\text{base}\!\!\!\!\!\!\!\overbrace{{}^{-3}}^{\text{exponent}} However, 7716/625 = 12.3456 is not a floating-point number in base ten with five digits—it needs six digits. The nearest floating-point number with only five digits is 12.346. And 1/3 = 0.3333… is not a floating-point number in base ten with any finite number of digits. In practice, most floating-point systems use base two, though base ten (decimal floating point) is also common. Floating-point arithmetic operations, such as addition and division, approximate the corresponding real number arithmetic operations by rounding any result that is not a floating-point number itself to a nearby floating-point number. For example, in a floating-point arithmetic with five base-ten digits, the sum 12.345 + 1.0001 = 13.3451 might be rounded to 13.345. The term floating point refers to the fact that the number's radix point can "float" anywhere to the left, right, or between the significant digits of the number. This position is indicated by the exponent, so floating point can be considered a form of scientific notation. A floating-point system can be used to represent, with a fixed number of digits, numbers of very different orders of magnitude — such as the number of meters between galaxies or between protons in an atom. For this reason, floating-point arithmetic is often used to allow very small and very large real numbers that require fast processing times. The result of this dynamic range is that the numbers that can be represented are not uniformly spaced; the difference between two consecutive representable numbers varies with their exponent. : the green lines mark representable values. of representable values Over the years, a variety of floating-point representations have been used in computers. In 1985, the IEEE 754 Standard for Floating-Point Arithmetic was established, and since the 1990s, the most commonly encountered representations are those defined by the IEEE. The speed of floating-point operations, commonly measured in terms of FLOPS, is an important characteristic of a computer system, especially for applications that involve intensive mathematical calculations. Floating-point numbers can be computed using software implementations (softfloat) or hardware implementations (hardfloat). Floating-point units (FPUs, colloquially math coprocessors) are specially designed to carry out operations on floating-point numbers and are part of most computer systems. When FPUs are not available, software implementations can be used instead. \frac{s}{b^{\,p-1}} \times b^e, where is the significand (ignoring any implied decimal point), is the precision (the number of digits in the significand), is the base (in our example, this is the number ten), and is the exponent. Historically, several number bases have been used for representing floating-point numbers, with base two (binary) being the most common, followed by base ten (decimal floating point), and other less common varieties, such as base sixteen (hexadecimal floating point ), base eight (octal floating point ), base four (quaternary floating point ), base three (balanced ternary floating point ) and even base 256 and base . A floating-point number is a rational number, because it can be represented as one integer divided by another; for example is (145/100)×1000 or /100. The base determines the fractions that can be represented; for instance, 1/5 cannot be represented exactly as a floating-point number using a binary base, but 1/5 can be represented exactly using a decimal base ( , or ). However, 1/3 cannot be represented exactly by either binary (0.010101...) or decimal (0.333...), but in base 3, it is trivial (0.1 or 1×3 −1 ) . The occasions on which infinite expansions occur depend on the base and its prime factors. The way in which the significand (including its sign) and exponent are stored in a computer is implementation-dependent. The common IEEE formats are described in detail later and elsewhere, but as an example, in the binary single-precision (32-bit) floating-point representation, p = 24 , and so the significand is a string of 24 bits. For instance, the number 's first 33 bits are: 11001001\ 00001111\ 1101101\underline{0}\ 10100010\ 0. In this binary expansion, let us denote the positions from 0 (leftmost bit, or most significant bit) to 32 (rightmost bit). The 24-bit significand will stop at position 23, shown as the underlined bit above. The next bit, at position 24, is called the round bit or rounding bit. It is used to round the 33-bit approximation to the nearest 24-bit number (there are specific rules for halfway values, which is not the case here). This bit, which is in this example, is added to the integer formed by the leftmost 24 bits, yielding: 11001001\ 00001111\ 1101101\underline{1}. When this is stored in memory using the IEEE 754 encoding, this becomes the significand . The significand is assumed to have a binary point to the right of the leftmost bit. So, the binary representation of is calculated from left-to-right as follows: \begin{align} &\biggl(\sum_{n=0}^{p-1} \text{bit}_n \times 2^{-n}\biggr) \times 2^e \\ &\qquad{}= \left(1 \times 2^{-0} + 1 \times 2^{-1} + 0 \times 2^{-2} + 0 \times 2^{-3} + \cdots + 1 \times 2^{-23}\right) \times 2^1 \\[2mu] &\qquad{} \approx 1.57079637 \times 2 \\[3mu] &\qquad{} \approx 3.1415927 \end{align} where is the precision ( in this example), is the position of the bit of the significand from the left (starting at and finishing at here) and is the exponent ( in this example). It can be required that the most significant digit of the significand of a non-zero number be non-zero (except when the corresponding exponent would be smaller than the minimum one). This process is called normalization. For binary formats (which uses only the digits and ), this non-zero digit is necessarily . Therefore, it does not need to be represented in memory, allowing the format to have one more bit of precision. This rule is variously called the leading bit convention, the implicit bit convention, the hidden bit convention, or the assumed bit convention. In 1938, Konrad Zuse of Berlin completed the Z1, the first binary, programmable mechanical computer; it uses a 24-bit binary floating-point number representation with a 7-bit signed exponent, a 17-bit significand (including one implicit bit), and a sign bit. The more reliable relay-based Z3, completed in 1941, has representations for both positive and negative infinities; in particular, it implements defined operations with infinity, such as division by infinity, where 1/\infty = 0 , and it stops on undefined operations, such as 0 \times \infty . Zuse also proposed, but did not complete, carefully rounded floating-point arithmetic that includes \pm\infty and NaN representations, anticipating features of the IEEE Standard by four decades. In contrast, von Neumann recommended against floating-point numbers for the 1951 IAS machine, arguing that fixed-point arithmetic is preferable. The first commercial computer with floating-point hardware was Zuse's Z4 computer, designed in 1942–1945. In 1946, Bell Laboratories introduced the Model V, which implemented decimal floating-point numbers. The Pilot ACE has binary floating-point arithmetic, and it became operational in 1950 at National Physical Laboratory, UK. Thirty-three were later sold commercially as the English Electric DEUCE. The arithmetic is actually implemented in software, but with a one megahertz clock rate, the speed of floating-point and fixed-point operations in this machine were initially faster than those of many competing computers. The mass-produced IBM 704 followed in 1954; it introduced the use of a biased exponent. For many decades after that, floating-point hardware was typically an optional feature, and computers that had it were said to be "scientific computers", or to have "scientific computation" (SC) capability (see also Extensions for Scientific Computation (XSC)). It was not until the launch of the Intel i486 in 1989 that general-purpose personal computers had floating-point capability in hardware as a standard feature. The UNIVAC 1100/2200 series, introduced in 1962, supported two floating-point representations: Single precision: 36 bits, organized as a 1-bit sign, an 8-bit exponent, and a 27-bit significand. Double precision: 72 bits, organized as a 1-bit sign, an 11-bit exponent, and a 60-bit significand. The IBM 7094, also introduced in 1962, supported single-precision and double-precision representations, but with no relation to the UNIVAC's representations. Indeed, in 1964, IBM introduced hexadecimal floating-point representations in its System/360 mainframes; these same representations are still available for use in modern z/Architecture systems. In 1998, IBM implemented IEEE-compatible binary floating-point arithmetic in its mainframes; in 2005, IBM also added IEEE-compatible decimal floating-point arithmetic. Initially, computers used many different representations for floating-point numbers. The lack of standardization at the mainframe level was an ongoing problem by the early 1970s for those writing and maintaining higher-level source code; these manufacturer floating-point standards differed in the word sizes, the representations, and the rounding behavior and general accuracy of operations. Floating-point compatibility across multiple computing systems was in desperate need of standardization by the early 1980s, leading to the creation of the IEEE 754 standard once the 32-bit (or 64-bit) word had become commonplace. This standard was significantly based on a proposal from Intel, which was designing the i8087 numerical coprocessor; Motorola, which was designing the 68000 around the same time, gave significant input as well. , principal architect of the IEEE 754 floating-point standard In 1989, mathematician and computer scientist William Kahan was honored with the Turing Award for being the primary architect behind this proposal; he was aided by his student Jerome Coonen and a visiting professor, Harold Stone. Among the x86 (more specifically i8087) innovations are these: A precisely specified floating-point representation at the bit-string level, so that all compliant computers interpret bit patterns the same way. This makes it possible to accurately and efficiently transfer floating-point numbers from one computer to another (after accounting for endianness). A precisely specified behavior for the arithmetic operations: A result is required to be produced as if infinitely precise arithmetic were used to yield a value that is then rounded according to specific rules. This means that a compliant computer program would always produce the same result when given a particular input, thus mitigating the almost mystical reputation that floating-point computation had developed for its hitherto seemingly non-deterministic behavior. The ability of exceptional conditions (overflow, divide by zero, etc.) to propagate through a computation in a benign manner and then be handled by the software in a controlled fashion. These features would be inherited into IEEE 754-1985 (with the exception of the encoding of special values and exceptions), though the extended internal precision of x87 means it requires explicit rounding of exact results directly to the destination precision in order to match standard IEEE 754 results. However, the behavior may not be the same as a rounding to the destination format due to a possible wider exponent range of the extended format. On a typical computer system, a double-precision (64-bit) binary floating-point number has a coefficient of 53 bits (including 1 implied bit), an exponent of 11 bits, and 1 sign bit. Since 2 10 = 1024, the complete range of the positive normal floating-point numbers in this format is from 2 −1022  ≈ 2 × 10 −308 to approximately 2 1024  ≈ 2 × 10 308 . The number of normal floating-point numbers in a system (B, P, L, U) where B is the base of the system, P is the precision of the significand (in base B), L is the smallest exponent of the system, U is the largest exponent of the system, is 2 \left(B - 1\right) \left(B^{P-1}\right) \left(U - L + 1\right) , or 2 \left(B - 1\right) \left(B^{P-1}\right) \left(U - L + 1\right) + 1 considering the value 0. There is a smallest positive normal floating-point number, Underflow level = UFL = B^L , which has a 1 as the leading digit and 0 for the remaining digits of the significand, and the smallest possible value for the exponent. There is a largest floating-point number, Overflow level = OFL = \left(1 - B^{-P}\right)\left(B^{U + 1}\right) , which has B − 1 as the value for each digit of the significand and the largest possible value for the exponent. In addition, there are representable values strictly between −UFL and UFL. Namely, positive and negative zeros, as well as subnormal numbers. sign = 0 ; e = 1 ; s = 110010010000111111011011 (including the hidden bit) The sum of the exponent bias (127) and the exponent (1) is 128, so this is represented in the single-precision format as 0 10000000 10010010000111111011011 (excluding the hidden bit) = 40490FDB as a hexadecimal number. An example of a layout for 32-bit floating point is and the 64-bit ("double") layout is similar. By their nature, all numbers expressed in floating-point format are rational numbers with a terminating expansion in the relevant base (for example, a terminating decimal expansion in base-10, or a terminating binary expansion in base-2). Irrational numbers, such as or \sqrt{2} , or non-terminating rational numbers, must be approximated. The number of digits (or bits) of precision also limits the set of rational numbers that can be represented exactly. For example, the decimal number 123456789 cannot be exactly represented if only eight decimal digits of precision are available (it would be rounded to one of the two straddling representable values, 12345678 × 10 1 or 12345679 × 10 1 ), the same applies to non-terminating digits (. to be rounded to either .55555555 or .55555556). When a number is represented in some format (such as a character string) which is not a native floating-point representation supported in a computer implementation, then it will require a conversion before it can be used in that implementation. If the number can be represented exactly in the floating-point format then the conversion is exact. If there is not an exact representation then the conversion requires a choice of which floating-point number to use to represent the original value. The representation chosen will have a different value from the original, and the value thus adjusted is called the rounded value. Whether or not a rational number has a terminating expansion depends on the base. For example, in base-10 the number 1/2 has a terminating expansion (0.5) while the number 1/3 does not (0.333...). In base-2 only rationals with denominators that are powers of 2 (such as 1/2 or 3/16) are terminating. Any rational with a denominator that has a prime factor other than 2 will have an infinite binary expansion. This means that numbers that appear to be short and exact when written in decimal format may need to be approximated when converted to binary floating-point. For example, the decimal number 0.1 is not representable in binary floating-point of any finite precision; the exact binary representation would have a "1100" sequence continuing endlessly: e = −4; s = 1100110011001100110011001100110011..., where, as previously, s is the significand and e is the exponent. When rounded to 24 bits this becomes e = −4; s = 110011001100110011001101, which is actually 0.100000001490116119384765625 in decimal. As a further example, the real number , represented in binary as an infinite sequence of bits is 11.0010010000111111011010101000100010000101101000110000100011010011... but is 11.0010010000111111011011 when approximated by rounding to a precision of 24 bits. In binary single-precision floating-point, this is represented as s = 1.10010010000111111011011 with e = 1. This has a decimal value of 3.1415927410125732421875, whereas a more accurate approximation of the true value of is 3.14159265358979323846264338327950... The result of rounding differs from the true value by about 0.03 parts per million, and matches the decimal representation of in the first 7 digits. The difference is the discretization error and is limited by the machine epsilon. The arithmetical difference between two consecutive representable floating-point numbers which have the same exponent is called a unit in the last place (ULP). For example, if there is no representable number lying between the representable numbers 1.45A70C22 16 and 1.45A70C24 16 , the ULP is 2×16 −8 , or 2 −31 . For numbers with a base-2 exponent part of 0, i.e. numbers with an absolute value higher than or equal to 1 but lower than 2, an ULP is exactly 2 −23 or about 10 −7 in single precision, and exactly 2 −52 or about 10 −16 in double precision. The mandated behavior of IEEE-compliant hardware is that the result be within one-half of a ULP. 123456.7 = 1.234567 × 10^5 101.7654 = 1.017654 × 10^2 = 0.001017654 × 10^5 Hence: 123456.7 + 101.7654 = (1.234567 × 10^5) + (1.017654 × 10^2) = 1.235584654 × 10^5 In detail: e=5; s=1.234567 (123456.7) + e=2; s=1.017654 (101.7654) e=5; s=1.234567 + e=5; s=0.001017654 (after shifting) -------------------- e=5; s=1.235584654 (true sum: 123558.4654) This is the true result, the exact sum of the operands. It will be rounded to seven digits and then normalized if necessary. The final result is e=5; s=1.235585 (final sum: 123558.5) The lowest three digits of the second operand (654) are essentially lost. This is round-off error. In extreme cases, the sum of two non-zero numbers may be equal to one of them: e=5; s=1.234567 + e=−3; s=9.876543 e=5; s=1.234567 + e=5; s=0.00000009876543 (after shifting) ---------------------- e=5; s=1.23456709876543 (true sum) e=5; s=1.234567 (after rounding and normalization) In the above conceptual examples it would appear that a large number of extra digits would need to be provided by the adder to ensure correct rounding; however, for binary addition or subtraction using careful implementation techniques only a guard bit, a rounding bit and one extra sticky bit need to be carried beyond the precision of the operands. Another problem of loss of significance occurs when approximations to two nearly equal numbers are subtracted. In the following example e = 5; s = 1.234571 and e = 5; s = 1.234567 are approximations to the rationals 123457.1467 and 123456.659. e=5; s=1.234571 − e=5; s=1.234567 ---------------- e=5; s=0.000004 e=−1; s=4.000000 (after rounding and normalization) The floating-point difference is computed exactly because the numbers are close—the Sterbenz lemma guarantees this, even in case of underflow when gradual underflow is supported. Despite this, the difference of the original numbers is e = −1; s = 4.877000, which differs more than 20% from the difference e = −1; s = 4.000000 of the approximations. In extreme cases, all significant digits of precision can be lost. This cancellation illustrates the danger in assuming that all of the digits of a computed result are meaningful. Dealing with the consequences of these errors is a topic in numerical analysis; see also Accuracy problems. e=3; s=4.734612 × e=5; s=5.417242 ----------------------- e=8; s=25.648538980104 (true product) e=8; s=25.64854 (after rounding) e=9; s=2.564854 (after normalization) Similarly, division is accomplished by subtracting the divisor's exponent from the dividend's exponent, and dividing the dividend's significand by the divisor's significand. There are no cancellation or absorption problems with multiplication or division, though small errors may accumulate as operations are performed in succession. In practice, the way these operations are carried out in digital logic can be quite complex (see Booth's multiplication algorithm and Division algorithm). The default return value for each of the exceptions is designed to give the correct result in the majority of cases such that the exceptions can be ignored in the majority of codes. inexact returns a correctly rounded result, and underflow returns a value less than or equal to the smallest positive normal number in magnitude and can almost always be ignored. divide-by-zero returns infinity exactly, which will typically then divide a finite number and so give zero, or else will give an invalid exception subsequently if not, and so can also typically be ignored. For example, the effective resistance of n resistors in parallel (see fig. 1) is given by R_\text{tot}=1/(1/R_1+1/R_2+\cdots+1/R_n) . If a short-circuit develops with R_1 set to 0, 1/R_1 will return +infinity which will give a final R_{tot} of 0, as expected (see the continued fraction example of IEEE 754 design rationale for another example). Overflow and invalid exceptions can typically not be ignored, but do not necessarily represent errors: for example, a root-finding routine, as part of its normal operation, may evaluate a passed-in function at values outside of its domain, returning NaN and an invalid exception flag to be ignored until finding a useful start point. // Enough digits to be sure we get the correct approximation. const double pi = 3.1415926535897932384626433832795; double z = tan(pi / 2.0); will give a result of 16331239353195370.0. In single precision (using the tanf function), the result will be −22877332.0. By the same token, an attempted computation of sin( ) will not yield zero. The result will be (approximately) 0.1225 in double precision, or −0.8742 in single precision. While floating-point addition and multiplication are both commutative ( and ), they are not necessarily associative. That is, is not necessarily equal to . Using 7-digit significand decimal arithmetic: a = 1234.567, b = 45.67834, c = 0.0004 (a + b) + c: 1234.567 (a) + 45.67834 (b) ____________ 1280.24534 rounds to 1280.245 1280.245 (a + b) + 0.0004 (c) ____________ 1280.2454 rounds to 1280.245 ← (a + b) + c a + (b + c): 45.67834 (b) + 0.0004 (c) ____________ 45.67874 1234.567 (a) + 45.67874 (b + c) ____________ 1280.24574 rounds to 1280.246 ← a + (b + c) They are also not necessarily distributive. That is, may not be the same as : 1234.567 × 3.333333 = 4115.223 1.234567 × 3.333333 = 4.115223 4115.223 + 4.115223 = 4119.338 but 1234.567 + 1.234567 = 1235.802 1235.802 × 3.333333 = 4119.340 In addition to loss of significance, inability to represent numbers such as and 0.1 exactly, and other slight inaccuracies, the following phenomena may occur: On 25 February 1991, a loss of significance in a MIM-104 Patriot missile battery prevented it from intercepting an incoming Scud missile in Dhahran, Saudi Arabia, contributing to the death of 28 soldiers from the U.S. Army's 14th Quartermaster Detachment. The weapons control computer counted time in an integer number of tenths of a second since boot. For conversion to a floating-point number of seconds in velocity and position calculations, the software originally multiplied this number by a 24-bit fixed-point binary approximation to 0.1, specifically 0.00011001100110011001100_2 = 0.1 \times (1 - 2^{-20}). Some parts of the software were later adapted to use a more accurate conversion to floating-point, but some parts were not updated and still used the 24-bit approximation. These parts of the software drifted from one another by about 3.43 milliseconds per hour. After 20 hours, the discrepancy of about 68.7 ms was enough for the radar tracking system to lose track of Scuds; the control system in the Dhahran missile battery had been running for about 100 hours when it failed to track and intercept an incoming Scud. The failure to intercept arose not from using floating point specifically, but from subtracting two different approximations to unit conversion with different errors when representing time, so the unit conversion error in the difference did not cancel out but rather grew indefinitely with uptime. \Epsilon_\text{mach} = B^{1-P},\, whereas rounding to nearest, \Epsilon_\text{mach} = \tfrac{1}{2} B^{1-P}, where B is the base of the system and P is the precision of the significand (in base B). This is important since it bounds the relative error in representing any non-zero real number within the normalized range of a floating-point system: \left| \frac{\operatorname{fl}(x) - x}{x} \right| \le \Epsilon_\text{mach}. Backward error analysis, the theory of which was developed and popularized by James H. Wilkinson, can be used to establish that an algorithm implementing a numerical function is numerically stable. The basic approach is to show that although the calculated result, due to roundoff errors, will not be exactly correct, it is the exact solution to a nearby problem with slightly perturbed input data. If the perturbation required is small, on the order of the uncertainty in the input data, then the results are in some sense as accurate as the data "deserves". The algorithm is then defined as backward stable. Stability is a measure of the sensitivity to rounding errors of a given numerical procedure; by contrast, the condition number of a function for a given problem indicates the inherent sensitivity of the function to small perturbations in its input and is independent of the implementation used to solve the problem. As a trivial example, consider a simple expression giving the inner product of (length two) vectors x and y , then \begin{align} \operatorname{fl}(x \cdot y) &= \operatorname{fl}\big(\operatorname{fl}(x_1 \cdot y_1) + \operatorname{fl}(x_2 \cdot y_2)\big), && \text{ where } \operatorname{fl}() \text{ indicates correctly rounded floating-point arithmetic} \\ &= \operatorname{fl}\big((x_1 \cdot y_1)(1 + \delta_1) + (x_2 \cdot y_2)(1 + \delta_2)\big), && \text{ where } \delta_n \leq \Epsilon_\text{mach}, \text{ from above} \\ &= \big((x_1 \cdot y_1)(1 + \delta_1) + (x_2 \cdot y_2)(1 + \delta_2)\big)(1 + \delta_3) \\ &= (x_1 \cdot y_1)(1 + \delta_1)(1 + \delta_3) + (x_2 \cdot y_2)(1 + \delta_2)(1 + \delta_3), \end{align} and so \operatorname{fl}(x \cdot y) = \hat{x} \cdot \hat{y}, where \begin{align} \hat{x}_1 &= x_1(1 + \delta_1); & \hat{x}_2 &= x_2(1 + \delta_2);\\ \hat{y}_1 &= y_1(1 + \delta_3); & \hat{y}_2 &= y_2(1 + \delta_3),\\ \end{align} where \delta_n \leq \Epsilon_\text{mach} by definition, which is the sum of two slightly perturbed (on the order of Ε mach ) input data, and so is backward stable. For more realistic examples in numerical linear algebra, see Higham 2002 and other references below. For example, the following algorithm is a direct implementation to compute the function f(x)= \frac{x-1}{\exp(x-1)-1} , which is well-conditioned at x = 1 . However, it can be shown to be numerically unstable and lose up to half the significant digits carried by the arithmetic when computed near 1.0. include double f(double x) { double y = x - 1.0; double z = exp(y); if (z != 1.0) { z = y / (z - 1.0); } return z; } A numerical analysis of the algorithm reveals that if the highlighted z = y / (z - 1.0); was replaced with z = log(z) / (z - 1.0); in an non-obvious change, then the algorithm becomes numerically stable and can compute to full double precision. To maintain the properties of such carefully constructed numerically stable programs, careful handling by the compiler is required. Certain "optimizations" that compilers might make (for example, reordering operations) can work against the goals of well-behaved software. There is some controversy about the failings of compilers and language designs in this area: C99 is an example of a language where such optimizations are carefully specified to maintain numerical precision. See the external references at the bottom of this article. More accurate implementations of many commonly-used functions that would encounter precision problems are found in the C mathematical functions and the standard libraries of other languages. For example, the above operation, which suffers from catastrophic cancellation in computing x-1 , could instead be implemented by . Similar functions include , . A detailed treatment of the techniques for writing high-quality floating-point software is beyond the scope of this article, and the reader is referred to, and the other references at the bottom of this article. Kahan suggests several rules of thumb that can substantially decrease by orders of magnitude the risk of numerical anomalies, in addition to, or in lieu of, a more careful numerical analysis. These include: as noted above, computing all expressions and intermediate results in the highest precision supported in hardware (a common rule of thumb is to carry twice the precision of the desired result, i.e. compute in double precision for a final single-precision result, or in double extended or quad precision for up to double-precision results ); and rounding input data and results to only the precision required and supported by the input data (carrying excess precision in the final result beyond that required and supported by the input data can be misleading, increases storage cost and decreases speed, and the excess bits can affect convergence of numerical procedures: notably, the first form of the iterative example given below converges correctly when using this rule of thumb). Brief descriptions of several additional issues and techniques follow. Expectations from mathematics may not be realized in the field of floating-point computation. For example, it is known that (x+y)(x-y) = x^2-y^2\; , and that \sin^2{\theta}+\cos^2{\theta} = 1\; . However, these facts cannot be relied on when the quantities involved are the result of floating-point computation: both expressions are subject to round-off errors and the former is additionally at risk from underflow, overflow, and catastrophic cancellation. The use of the exact equality test ( if (x==y) ... ) requires care when dealing with floating-point numbers, as the many errors (even tiny ones) tend to stop most equalities from evaluating as true. Even simple expressions like 0.6 / 0.2 - 3 == 0 will be false when computed under any binary floating-point format (in IEEE 754 double precision, for example, 0.6 / 0.2 - 3 is approximately equal to ). Consequently, such tests are sometimes replaced with "fuzzy" comparisons ( if (abs(x-y) , where epsilon is sufficiently small and tailored to the application, such as 1.0E−13). The wisdom of doing this varies greatly, and can require numerical analysis to bound epsilon. Values derived from the primary data representation and their comparisons should be performed in a wider, extended, precision to minimize the risk of such inconsistencies due to round-off errors. It is often better to organize the code in such a way that such tests are unnecessary. For example, in computational geometry, exact tests of whether a point lies off or on a line or plane defined by other points can be performed using adaptive precision or exact arithmetic methods. t_0 = \frac{1}{\sqrt{3}} First form: t_{i+1} = \frac{\sqrt{t_i^2+1}-1}{t_i} Second form: t_{i+1} = \frac{t_i}{\sqrt{t_i^2+1}+1} \pi \sim 6 \times 2^i \times t_i , converging as i \rightarrow \infty Here is a computation using IEEE "double" (a significand with 53 bits of precision) arithmetic: i 6 × 2 i × t i , first form 6 × 2 i × t i , second form --------------------------------------------------------- 0 .4641016151377543863 .4641016151377543863 1 .2153903091734710173 .2153903091734723496 2 596599420974940120 596599420975006733 3 60862151314012979 60862151314352708 4 27145996453136334 27145996453689225 5 8730499801259536 8730499798241950 6 6627470548084133 6627470568494473 7 6101765997805905 6101766046906629 8 70343230776862 70343215275928 9 37488171150615 37487713536668 10 9278733740748 9273850979885 11 7256228504127 7220386148377 12 717412858693 707019992125 13 189011456060 78678454728 14 717412858693 46593073709 15 19358822321783 8571730119 16 717412858693 6566394222 17 810075796233302 6065061913 18 717412858693 939728836 19 4061547378810956 908393901 20 05434924008406305 900560168 21 00068646912273617 8608396 22 349453756585929919 8122118 23 00068646912273617 95552 24 .2245152435345525443 68907 25 62246 26 62246 27 62246 28 62246 The true value is While the two forms of the recurrence formula are clearly mathematically equivalent, the first subtracts 1 from a number extremely close to 1, leading to an increasingly problematic loss of significant digits. As the recurrence is applied repeatedly, the accuracy improves at first, but then it deteriorates. It never gets better than about 8 digits, even though 53-bit arithmetic should be capable of about 16 digits of precision. When the second form of the recurrence is used, the value converges to 15 digits of precision.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378637805 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

25 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.