Loss of significance
Encyclopedia
Loss of significance is an undesirable effect in calculations using floating-point
arithmetic. It occurs when an operation on two numbers increases relative error substantially more than it increases absolute error, for example in subtracting two large and nearly equal numbers. The effect is that the number of accurate (significant) digits in the result is reduced unacceptably. Ways to avoid this effect are studied in numerical analysis
.
In floating-point arithmetic, only a limited number of digits of the number are maintained; floating-point numbers can only approximate most real numbers.
Example:
For the purposes of this example, if the reader is not familiar with binary numbers, bits can be considered as decimal digits.
Consider the real binary number
1.001111111
A floating-point representation of this number on a machine that keeps 4 floating-point bits would be
1.001,
which is fairly close — the difference is very small in comparison with either of the two numbers.
Now perform the calculation
1.001111111 − 1
The real answer, accurate to 7 significant bits, is
0.001111111
However, on the 4-bit floating-point machine, the calculation yields
1.001 − 1.000 = 0.001
Whereas the original numbers are significant in all of the first 4 bits, their floating-point difference is only accurate in its first nonzero bit. This amounts to loss of information.
This phenomenon is relevant for any size Floating Point number.
Instead of 4 significant bits, an IEEE standard single precision floating point number has 23 significant bits and 1 sign bit.
Additionally, the phenomenon can also be demonstrated with decimal numbers.
The following example demonstrates Loss of Significance for a Decimal floating point data type with 10 significant digits:
Consider the real decimal number
0.1234567891234567890.
A floating-point representation of this number on a machine that keeps 10 floating-point digits would be
0.1234567891,
which is fairly close — the difference is very small in comparison with either of the two numbers.
Now perform the calculation
0.1234567891234567890 − 0.1234567890.
The real answer, accurate to 10 digits, is
0.0000000001234567890.
However, on the 10-digit floating-point machine, the calculation yields
0.1234567891 − 0.1234567890 = 0.0000000001.
Whereas the original numbers are accurate in all of the first (most significant) 10 digits, their floating-point difference is only accurate in its first nonzero digit. This amounts to loss of information.
Workarounds
It is possible to do computations using an exact fractional representation of rational numbers and keep all significant digits, but this is often prohibitively slower than floating-point arithmetic. Furthermore, it usually only postpones the problem: What if the data is accurate to only 10 digits? The same effect will occur.
One of the most important parts of numerical analysis is to avoid or minimize loss of significance in calculations. If the underlying problem is well-posed, there should be a stable algorithm for solving it. The art is in finding a stable algorithm.
In the subtraction x − y, r significant bits are lost where
for some positive integers p and q.
.
For the polynomial equation,
,
the quadratic equation gives the two solutions as
The case
, 
, 
will serve to illustrate the problem:
We have
In real arithmetic, the roots are
In 10-digit floating-point arithmetic,
Notice that the solution of greater magnitude
is accurate to ten digits, but the first nonzero digit of the solution of lesser magnitude is wrong.
Because of the subtraction that occurs in the quadratic equation, it does not constitute a stable algorithm to calculate the two roots.
If
and
then we have the identity (one of Vi%C3%A8te%27s formulas for a second degree polynomial)
.
The above formulas (1) and (2) work perfectly for a quadratic equation whose coefficient 'b' is negative (b < 0). If 'b' is negative then '-b' in the formulas get converted to a positive value as -(-b) is equal to 'b'. Hence, we can avoid subtraction and loss of significant digits caused by it. But if the coefficient 'b' is positive then we need to use a different set of formulas. The second set of formulas that are valid for finding roots when coefficient 'b' is positive are mentioned below.
and
In the above formulas (3) and (4) when 'b' is positive the formula converts it to negative value as -(+b) is equal to -b. Now, as per the formulas '-b' is subtracted by square root of (b*b - 4ac) so basically it's an addition operation. In our example, coefficient 'b' of quadratic equation is positive . Hence, we need to use the second set of formulas i.e. Formula (3) and (4).
The algorithm is as follows. Use the quadratic formula to find the solution of greater magnitude, which does not suffer from loss of precision. Then use this identity to calculate the other root. Since no subtraction is involved, no loss of precision occurs.
Applying this algorithm to our problem, and using 10-digit floating-point arithmetic, the solution of greater magnitude, as before, is
The other solution is then
which is accurate.
Floating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
arithmetic. It occurs when an operation on two numbers increases relative error substantially more than it increases absolute error, for example in subtracting two large and nearly equal numbers. The effect is that the number of accurate (significant) digits in the result is reduced unacceptably. Ways to avoid this effect are studied in numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
.
In floating-point arithmetic, only a limited number of digits of the number are maintained; floating-point numbers can only approximate most real numbers.
Example:
For the purposes of this example, if the reader is not familiar with binary numbers, bits can be considered as decimal digits.
Consider the real binary number
1.001111111
A floating-point representation of this number on a machine that keeps 4 floating-point bits would be
1.001,
which is fairly close — the difference is very small in comparison with either of the two numbers.
Now perform the calculation
1.001111111 − 1
The real answer, accurate to 7 significant bits, is
0.001111111
However, on the 4-bit floating-point machine, the calculation yields
1.001 − 1.000 = 0.001
Whereas the original numbers are significant in all of the first 4 bits, their floating-point difference is only accurate in its first nonzero bit. This amounts to loss of information.
This phenomenon is relevant for any size Floating Point number.
Instead of 4 significant bits, an IEEE standard single precision floating point number has 23 significant bits and 1 sign bit.
Additionally, the phenomenon can also be demonstrated with decimal numbers.
The following example demonstrates Loss of Significance for a Decimal floating point data type with 10 significant digits:
Consider the real decimal number
0.1234567891234567890.
A floating-point representation of this number on a machine that keeps 10 floating-point digits would be
0.1234567891,
which is fairly close — the difference is very small in comparison with either of the two numbers.
Now perform the calculation
0.1234567891234567890 − 0.1234567890.
The real answer, accurate to 10 digits, is
0.0000000001234567890.
However, on the 10-digit floating-point machine, the calculation yields
0.1234567891 − 0.1234567890 = 0.0000000001.
Whereas the original numbers are accurate in all of the first (most significant) 10 digits, their floating-point difference is only accurate in its first nonzero digit. This amounts to loss of information.
Workarounds
It is possible to do computations using an exact fractional representation of rational numbers and keep all significant digits, but this is often prohibitively slower than floating-point arithmetic. Furthermore, it usually only postpones the problem: What if the data is accurate to only 10 digits? The same effect will occur.
One of the most important parts of numerical analysis is to avoid or minimize loss of significance in calculations. If the underlying problem is well-posed, there should be a stable algorithm for solving it. The art is in finding a stable algorithm.
Loss of significant bits
Let x and y be positive normalized floating point numbers.In the subtraction x − y, r significant bits are lost where
for some positive integers p and q.
Instability of the quadratic equation
For example, consider the venerable quadratic equationQuadratic equation
In mathematics, a quadratic equation is a univariate polynomial equation of the second degree. A general quadratic equation can be written in the formax^2+bx+c=0,\,...
.
For the polynomial equation,
,the quadratic equation gives the two solutions as
The case
, , will serve to illustrate the problem:We have
In real arithmetic, the roots are
In 10-digit floating-point arithmetic,
Notice that the solution of greater magnitude
Absolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
is accurate to ten digits, but the first nonzero digit of the solution of lesser magnitude is wrong.
Because of the subtraction that occurs in the quadratic equation, it does not constitute a stable algorithm to calculate the two roots.
A better algorithm
A better algorithm for solving quadratic equations is based on two observations: that one solution is always accurate when the other is not, and that given one solution of the quadratic, the other is easy to find.If
and
then we have the identity (one of Vi%C3%A8te%27s formulas for a second degree polynomial)
.The above formulas (1) and (2) work perfectly for a quadratic equation whose coefficient 'b' is negative (b < 0). If 'b' is negative then '-b' in the formulas get converted to a positive value as -(-b) is equal to 'b'. Hence, we can avoid subtraction and loss of significant digits caused by it. But if the coefficient 'b' is positive then we need to use a different set of formulas. The second set of formulas that are valid for finding roots when coefficient 'b' is positive are mentioned below.
and
In the above formulas (3) and (4) when 'b' is positive the formula converts it to negative value as -(+b) is equal to -b. Now, as per the formulas '-b' is subtracted by square root of (b*b - 4ac) so basically it's an addition operation. In our example, coefficient 'b' of quadratic equation is positive . Hence, we need to use the second set of formulas i.e. Formula (3) and (4).
The algorithm is as follows. Use the quadratic formula to find the solution of greater magnitude, which does not suffer from loss of precision. Then use this identity to calculate the other root. Since no subtraction is involved, no loss of precision occurs.
Applying this algorithm to our problem, and using 10-digit floating-point arithmetic, the solution of greater magnitude, as before, is
The other solution is thenwhich is accurate.