Reliable Floating Point Equality Comparison

Introduction

A discussion in the Subtle Bugs forum concerning floating point number comparisons caused me to recall some code I wrote about 15 years ago. Back then, I was writing code that calculated federal and stats estate/inheritance taxes, as well as charitable giving scenarios. We needed to compare floating point values at various levels of precision depending on what we were doing and where in the calculation cycle we happened to be.

The Snippet

Anyone that's been writing code for any length of time knows what a pain in the butt it is to compare floating point numbers because they're mere approximations of their true value. For this reason, I wrote, and present you now with my AlmostEqual() function.

My approach centers around converting the floating point values to something a bit more reliable where comparisons are concerned - strings. In the example shown in this article, I use CStrings because I'm a fan of MFC. You could certainly use stdio functions or even STL for your strings if you don't (or can't) use MFC. I admit that this isn't some fancy thing that magically evaluates all of the parts of a floating point number, but it does work and it's handy if you need to compare floating point values to a specific level of precision.

bool AlmostEqual(double nVal1, double nVal2, int nPrecision)
{
	CString sVal1;
	CString sVal2;

	nPrecision = __max(__min(16, nPrecision), 0);
	sVal1.Format("%.*lf", nPrecision, nVal1);
	sVal2.Format("%.*lf", nPrecision, nVal2);

	bool bRet = (sVal1 == sVal2);
	return bRet;
}

There's really not much to say about the function. You merely pass in the two values that need to be compared along with the desired precision value.

Article Update: 12/08/2006

After being hounded about speed issues, I decided to try different methods for comparison. Here's a function similar to the first, but that uses stdio functions for the string formatting.

bool AlmostEqualStdIO(double nVal1, double nVal2, int nPrecision)
{
	char sVal1[40];
	char sVal2[40];

	nPrecision = __max(__min(16, nPrecision), 0);
	sprintf_s(sVal1, sizeof(sVal1), "%.*lf", nPrecision, nVal1);
	sprintf_s(sVal2, sizeof(sVal2), "%.*lf", nPrecision, nVal2);

	bool bRet = (strcmp(sVal1, sVal2) == 0);
	return bRet;
}

The function above requires less than half the time the CString version needs to perform the same task. Keep in mind that this is using VS2005, and that (I think) the MFC CString class is actually using STL now.

Finally, here a version of the function that doesn't do any string manipulation at all.

bool AlmostEqualDoubles(double nVal1, double nVal2, int nPrecision)
{
	nPrecision = __max(__min(16, nPrecision), 0);
	double nEpsilon = 1.0;
	for (int i = 1; i <= nPrecision; i++)
	{
		nEpsilon *= 0.1;
	}
	bool bRet = (((nVal2 - nEpsilon) < nVal1) && (nVal1 < (nVal2 + nEpsilon)));
	return bRet;
}

When I watched this function work in the debugger, I noticed that performing ANY math of the nEpsilon value caused it to become impure. The very last digit of the mantissa was some random value. This almost guarantees that at some point, the value will be such that it returns an incorrect result. Given the aim of this article (RELIABLE equality comparisons), this is not adequate.

Finally, here's a version of the function that accepts a direct value for nEpsilon in the form of an appropriate value. For instance, if you want a precision of 3, you would pass in 0.001.

bool AlmostEqualDoubles2(double nVal1, double nVal2, double nEpsilon)
{
	bool bRet = (((nVal2 - nEpsilon) < nVal1) && (nVal1 < (nVal2 + nEpsilon)));
	return bRet;
}

I didn't watch all 250,000 iterations in my test app, but none of the ones I traced through presented any value other than 0.0010000000000000, but that does not preclude the possibility that it could happen (given the nature of floating point values). Again - given the aim of this article (RELIABLE equality comparisons), this is not adequate.

Finally, the non-string versions of the function were admittedly very fast. My 250,001 iteration tests revealed an execution time of ZERO seconds (obviously more than 0 seconds but less than 1 second) compared to two seconds for the stdio and five seconds for the CString version. Again, my admittedly chunky timing code should probably be replaced by something with a far higher resolution, but you get the idea. So, here we are with four versions of the comparison function. I still have to say that the string comparison is far more consistent than the non-string versions. Take that for what it's worth.

Is everyone happy now?

Disclaimers

It's apparent that the original single disclaimer (the last one in this list) was not sufficient , so I've added a couple more:

• This article is not about rounding floating point values (although I do have a function for that as well). It is about truncating the specified values at a specific precision via string formatting for a direct comparison. Therefore, passing 1.2345 and 1.2346 with a precision of anything less than 4 will generate a return value of true. while passing a precision of anything higher than 3 will result in a return value of false. With this in mind, please don't post comments about how the function is rounding the values being compared, because it's not.

• Yes, I'm aware that using strings is somewhat inefficient, but they are used for the sake of accuracy regarding the function's desired result. It is impossible to reliably compare two floating point numbers for equality. String comparisons are not subject to the flaws, and are therefore the comparison vehicle of choice if you want to be sure the comparison is consistent. Like I said in the article, you certainly don't have to use CString and can instead use either stdio functions or even STL if you're so inclined. It would be an interesting test to see which of the three are the best performers in that regard.
  
  UPDATE:I ran a test iterating 250,001 calls to AlmostEqual using a version of the function that used CString, and another function that used stdio sprintf_s. The CString method took 5 seconds, and the stdio version took 2 seconds. Granted, using COleDateTime isn't as precise as one would like to get, and if the difference wasn't so pronounced, I'd look for something more accurate. (Test system is a P4 3.6 with 1GB of RAM.)

• I recognize that this article is fairly short, and there's no sample code to download or fancy screen shots, but my view is that a lot of code we use comes down to one or two functions that fits a specific need and simply doesn't need a screen shot to illustrate its functionality. By its very definition, a snippet is usually not worthy of being made into a full-blown class with exception handling and/or serialization. So, use it if you want to.