Comparing Floating-Point Numbers
Within a computer program, comparing floating-point numbers for
equality is problematic. Writing an if statement to compare
floating-point numbers in the same way we would for integers like the
following Java code will sometimes give unexpected results.
float e = …
float f = …
// WRONG! Don't use this comparison code
// for floating-point numbers. It will
// occasionally give incorrect results.
if (e == f) {
// e and f are equal.
}
else {
// e and f are not equal.
}
These unexpected results are technically correct but contrary to the intent of the programmer. In other words, these unexpected results are incorrect from the perspective of the programmer and users of a program. The reason a simple comparison for equality with floating-point numbers will sometimes give unexpected results is that computers approximate most real numbers as floating-point numbers. Each time a computer performs calculations with floating-point numbers, rounding error almost always occurs. Consider the simple example of adding 0.1 ten times as shown in this Java code and its output:
final float tenth = 0.1F;
float sum = 0F;
for (int i = 0; i < 10; ++i) {
sum += tenth;
}
System.out.println("sum = " + sum);/* Output */ sum = 1.0000001
Similar code written in C gives a more precise but equally strange output.
const float tenth = 0.1F;
float sum = 0F;
for (int i = 0; i < 10; ++i) {
sum += tenth;
}
printf("sum = %.15f\n", sum);/* Output */ sum = 1.000000014901161
Of course, neither answer is correct because the correct answer to 0.1 added ten times is obviously 1. Because of the rounding error that occurs when the computer performs floating-point calculations, we cannot compare floating-point numbers for equality with the simple equality operator (==) that we use for integers. We must compare floating-point numbers in a way that evaluates to true when the numbers are close enough to be considered equal. One simple way to compare two floating-point numbers is to compare the absolute difference between the two numbers like this:
if (Math.abs(e - f) <= epsilon) {
// e and f are equal.
}
else {
// e and f are not equal.
}But how do we choose the value for epsilon? For some applications, we may know the range of values that will be in e and f and be able to choose a good value for epsilon, but for many applications, we know very little about the range of values that will be in e and f. Perhaps the value of epsilon could be calculated from the values of e and f. One possibility is to calculate epsilon as a percentage of the larger of e and f. For example:
float max = Math.max(Math.abs(e), Math.abs(f));
float epsilon = max * 0.01;
if (Math.abs(e - f) <= epsilon) {
// e and f are equal.
}
else {
// e and f are not equal.
}The previous Java code will compare two floats e and f to see if the difference between them is within 1% (0.01) of the larger float. Of course, the 1% could be changed to be smaller if we desire. This is a pretty good way to compare floating-point numbers. However, computer scientists have known for a long time that comparing floating-point numbers for equality is problematic, so they developed some concepts and functions to help.
One concept that can help us compare two floating-point numbers is
unit in the last place, which is often abbreviated as ulp. An
ulp is the unit of least significance within a floating-point
number. In other words, it is the distance from one positive
floating-point number to the next larger floating-point number. We can
use the concept of ulp to make floating-point comparisons for equality
more exact and robust. Many programming languages that include
floating-point arithmetic include a function to calculate ulps. Java
contains two functions in the Math class for computing
ulps.
Math.ulp(float f)Math.ulp(double d)
Here is Java code to compare two floats for equality by checking if the distance between them is less than or equal to two ulps of the larger float.
float max = Math.max(Math.abs(e), Math.abs(f));
float ulp = Math.ulp(max);
if (Math.abs(e - f) <= ulp * 2) {
// The distance between e and f is less than or
// equal to 2 ulps of the larger of e and f, so
// they are close enough to be considered equal.
}
else {
// The distance between e and f is larger than
// than 2 ulps of the larger of e and f, so they
// are considered unequal.
}We can use the previous code to write a small function to compare two floating-point numbers for equality.
public static boolean equals(float e, float f, int maxULPs) {
boolean eq;
boolean enan = Float.isNaN(e);
boolean fnan = Float.isNaN(f);
if (enan && fnan) {
// Both e and f are not numbers (NaN),
// so we consider them to be equal.
eq = true;
}
else if (enan || fnan) {
// Either e or f but not both is not a
// number (NaN), so they aren't equal.
eq = false;
}
else {
boolean einf = Float.isInfinite(e);
boolean finf = Float.isInfinite(f);
if (einf && finf) {
// Both e and f are infinite, so they
// are equal if their signs are equal,
// otherwise they are not equal.
int esign = (int)Math.signum(e);
int fsign = (int)Math.signum(f);
eq = (esign == fsign);
}
else if (einf || finf) {
// Either e or f but not both is
// infinite, so they aren't equal.
eq = false;
}
else {
// Both e and f are finite numbers, so
// compare them to see if they are
// close enough to be considered equal.
float max = Math.max(Math.abs(e), Math.abs(f));
float ulp = Math.ulp(max);
eq = (Math.abs(e - f) <= ulp * maxULPs);
}
}
return eq;
}This function may seem complex and may run slowly, but if we use simpler and naive techniques for comparing floating-point numbers for equality, then we may have faster code, but it will return incorrect results for some numbers. What good is fast code if it produces incorrect results?
Futher Reading
If you want to learn more about how computers store and process numbers, check out the book Really Understand Binary.