[Qt-interest] strange qFuzzyCompare implementation

[Stephan Rose]

On Sun, 2009-04-12 at 18:42 +0200, Thiago Macieira wrote:
> Peter Radagast wrote:
> >Hello!
> >I think all of us got used to high quality of the Qt design and
> > implementation. And I was very disappointed, when I saw the
> > qFuzzyCompare implementation:
> 
> That's because you didn't understand the purpose behind those functions.
> 
> >static inline bool qFuzzyCompare(double p1, double p2)
> >{
> >    return (qAbs(p1 - p2) <= 0.000000000001 * qMin(qAbs(p1), qAbs(p2)));
> >}
> >
> >static inline bool qFuzzyCompare(float p1, float p2)
> >{
> >    return (qAbs(p1 - p2) <= 0.00001f * qMin(qAbs(p1), qAbs(p2)));
> >}
> >
> >Do you consider these hard-coded numbers etc effective, precise and
> > portable? 
> 
> Yes. They work fine for the intent that these functions are meant to have.
> 
> > I supposed to see smth like:
> >static inline bool qFuzzyCompare(double p1, double p2)
> >{
> >    return (qAbs(p1 - p2) <= std::numeric_limits::epsilon<double>());
> >}
> 
> That would have the opposite effect of what is wanted. And it would not 
> work.
> 
> For one thing, no two numbers can have a difference that is smaller than 
> epsilon / order of magnitude. They can either be equal (exactly), differ by 
> one epsilon/order of magnitude or more. Remember that epsilon is the 
> smallest number that, added to 1, makes it different from 1. But if you had 
> 1e-9 instead of 1, you the difference would be epsilon * 1e-9. Even if you 
> took the order of magnitude into consideration in your function, it would 
> compare only if the two numbers are exactly equal or differ by the smallest 
> unit that they could differ by.
> 
> Like I said, that's not the intent of the function. The intent of the 
> function is to verify if the two numbers are sufficiently close that they 
> should be considered equal for the code in question. The problem is that 
> the many floating point operations accumulate rounding errors: the more 
> operations you make, the greater that error is. It's definitely greater 
> than one epsilon.
> 
> So your code would definitely not work.
> 
> We could have chosen to make the code compare to a multiple of epsilons 
> (like 1000 epsilon), but instead we chose to make our lives easier and 
> just write a very small number.

There actually is another way to do a float compare like this that does
*not* rely on that type of hardcoded value.

#define MaxError 5

bool compareFloat(float p1, float p2)
{
  int a, b;
  memcpy(&a, &p1, sizeof(float));
  memcpy(&b, &p2, sizeof(float));
  
  a = a < 0 ? 0x80000000 - a : a;
  b = b < 0 ? 0x80000000 - b : b;

  return qabs(a - b) <= MaxError;
}

This basically will do the same as what you were looking to do,
*without* relying on a value like 0.0001 or equivalent. It exploits the
fact that if you copy the float data into an integer and subtract b from
a, the result will be how close the two values are to one another,
regardless of their magnitude.

If there is no error, a-b = 0.
The greater the error is the larger a-b will be. You simply set MaxError
to what you want the greatest deviation in your code to be.

Small numbers will have a very small margin of error, really large
numbers will have a correspondingly larger margin of error.

Of course, you have to make sure that on the platform that sizeof(int)
== sizeof(float) and if not, use a different type that matches.  Same
can be done with doubles as well, just use a 64-bit int instead.

Stephan