3

Anyone care to explain in detail (code by code) what this is doing? I have read Bruce Dawson's paper on comparing floats and have found converted C# code of it but don't quite understand it. What is maxDeltaBits and its purpose? In Dawson's paper it states that this can also be applied to double, so if that is the case then would you need to convert the double value to Int64 instead of int32?

public static int FloatToInt32Bits( float f )
{
    return BitConverter.ToInt32( BitConverter.GetBytes( b ), 0 );
}

public static bool AlmostEqual2sComplement
    ( float a, float b, int maxDeltaBits )
{
    int aInt = FloatToInt32Bits( a );
    if ( aInt < 0 ) // Why only if it is less than 0?
        aInt = Int32.MinValue - aInt; // What is the purpose of this?

    int bInt = FloatToInt32Bits( b );
    if ( bInt < 0 ) // Why only if it is less than 0?
        bInt = Int32.MinValue - bInt; // What is the purpose of this?

    int intDiff = Math.Abs( aInt - bInt );
    return intDiff <= ( 1 << maxDeltaBits ); // Why ( 1 << maxDeltaBits )?
}
Community
  • 1
  • 1
gng
  • 31
  • 2
  • (note that you don't need `
    ` or ``; the wonder of Markdown means the four space indent is enough. Edited to avoid horizontal scrollbars)
     – AakashM Aug 25 '11 at 21:34
  • Anyone else able to give any more explanation? – gng Aug 26 '11 at 21:56

2 Answers2

2

It's all there in Bruce Dawson's papers. A float (or double for that matter) has a finite precision. That also means there is a set of all the numbers that a float can represent.

What Dawson's method does, is to count how many steps away in that set you can accept as "equal value", rather than use a fixed acceptable error value. The relative error of one such step will vary with a factor (almost) 2, where the relative error is less for a high value of the mantissa and bigger for a low value of the mantissa. However, the relative error for a fixed number of steps will not vary more than that.

To Roland Illig:

Why is it "a fact that you can never test two FP numbers for equality directly"? You can, but you will not always get what you expect. Not too large integer numbers stored as floats will work. However, a fraction that can be written as a finite number of decimal digits, cannot generally be stored with a finite number of binary digits. The number will be truncated. If you do some arithmetic, the error introduced with the truncation comes into play. Also, the FPU of your machine may store values with a higher precision, and you can end up with a comparison of values with unequal precision.

Test the following (C includes, change to cstdio and cmath for modern C++):

#include <stdio.h>
#include <math.h>

void Trig(float x, float y)
{
  if (cos(x) == cos(y)) printf("cos(%f) equal to cos(%f)\n",x,y);
  else printf("cos(%f) not equal to cos(%f)\n",x,y);
}

int main()
{
  float f = 0.1;
  f = f * 0.1 * 0.1 * 0.1;
  if (f == 0.0001f) printf("%f equals 0.0001\n",f);
  else printf("%f does not equal 0.0001\n",f);
  Trig(1.44,1.44);
  return 0;
}

On my machine, I get the "not equal" branch in both cases:

0.000100 does not equal 0.0001
cos(1.440000) not equal to cos(1.440000)

What you get on your machine is implementation dependant.

Jonas L.
  • 21
  • 2
1

The <0 stuff is due to http://en.wikipedia.org/wiki/Two%27s_complement. The maxDeltaBits handles the fact that you can never test two FP numbers for equality directly, you can only make sure they're "almost the same" within a certain amount of precision.

Marc B
  • 356,200
  • 43
  • 426
  • 500
  • why it's not enough to multiply with (-1)? – Tigran Aug 25 '11 at 21:44
  • Thanks for the wiki link, that makes so much sense as to why that is being done now. On the maxDeltaBits, so if I am understanding you correctly, the maxDeltaBits should be set to the maximum floating point I would like to test for? For example if I wanted to test it to the 14th floating point precision I would set it to 14? – gng Aug 25 '11 at 21:45
  • Anyone else able to shed some light on this? – gng Aug 26 '11 at 13:40
  • sub/add is usually a faster instruction at the cpu level than a mult/div. on an old 387, fmul is 29-52 cycles and fadd is 23-37. And yes, 1 << max delta is doing 2^maxdelta, then checking if the difference is less than that. – Marc B Aug 26 '11 at 14:17
  • Using the method above, shouldn't 0.000000000000018216822322255345 = 0? –  Sep 02 '11 at 14:02
  • Why is it "a fact that you can never test two FP numbers for equality directly"? I can do that, and it works very well. For example, `1.0 + 3.0 == 4.0`, exactly. – Roland Illig Sep 13 '11 at 23:42