The inspiration for this code comes from Bruce Dawson's excellent article on comparing floats -- specifically, the technique of reinterpreting the bits as sign-magnitude integers and measuring the distance "lexicographically". The idea is to provide a little slack for truncation and representation errors, without coding any hard values for absolute or relative error.
I thank Jeroen Frijters for suggesting the cool trick of using LayoutKind.Explicit to implement a union in managed code, thus allowing the floating point bits to be reinterpreted as an Int32, in fully verifiable code. (The FCL's BitConverter class has a DoubleToInt64Bits method, but no corresponding SingleToInt32Bits.)
I've provided some unit tests, along with this code, to verify that it compares all the special values (NaN, infinities, etc) with the same semantics as System.Single.
Final note: as elegant as this technique may be, it still runs a cost of several dozen x86 instructions. However, the performance seems to be on par with the cost of a call to Single.CompareTo(), and the native float comparison operations.
using System;
using System.Runtime.InteropServices;
using dbg=System.Diagnostics.Debug;
namespace Jitsu
{
public class FloatComparer : System.Collections.IComparer
{
int System.Collections.IComparer.Compare(object x, object y)
{
// Handle special cases (nulls, wrong types, etc).
if (x == null && y == null) return 0;
if (x == null)
if (y is float) return -1;
else throw new ArgumentException("Object must be of type Single.","y");
if (y == null)
if (x is float) return +1;
else throw new ArgumentException("Object must be of type Single.","x");
// Compare the floats' distance in units of least-precise bits.
const int tolerance = 5; // a pretty robust default
return Compare((float)x,(float)y,tolerance);
}
public static int Compare(float x, float y, int tolerance)
{
int dummy;
return Compare(x,y,tolerance, out dummy);
}
private static int Compare(float x, float y, int tolerance, out int difference)
{
// Make sure maxUlps is non-negative and small enough that the
// default NAN won't compare as equal to anything.
dbg.Assert(tolerance >= 0 && tolerance < 4*1024*1024);
// Reinterpret float bits as sign-magnitude integers.
int xi = BitReinterpreter.Convert(x);
int yi = BitReinterpreter.Convert(y);
// Convert from sign-magnitude to two's complement form,
// by subtracting from 0x80000000.
if (xi < 0)
xi = Int32.MinValue - xi;
if (yi < 0)
yi = Int32.MinValue - yi;
// How many epsilons apart?
difference = xi-yi;
// Is the difference outside our tolerance?
if (xi > yi+tolerance)
return +1;
if (xi < yi-tolerance)
return -1;
else
return 0;
}
//
// Implementation
[StructLayout(LayoutKind.Explicit)]
private struct BitReinterpreter
{
public static int Convert(float f)
{
BitReinterpreter br = new BitReinterpreter(f);
return br.i;
}
public static float Convert(int i)
{
BitReinterpreter br = new BitReinterpreter(i);
return br.f;
}
[FieldOffset(0)] float f;
[FieldOffset(0)] int i;
private BitReinterpreter(float f)
{ this.i = 0; this.f = f; }
private BitReinterpreter(int i)
{ this.f = 0; this.i = i; }
}
//
// Testing
#if TESTING
[Jitsu.Testing.UnitTest]
private static bool TestSpecialRelationships()
{
// Test each pairwise combination of special float values (infinities, nans, etc),
// against the behavior of Single.CompareTo().
foreach (uint val1 in System.Enum.GetValues(typeof(Specials)))
foreach (uint val2 in System.Enum.GetValues(typeof(Specials)))
{
int i1 = (int)val1;
int i2 = (int)val2;
f1 = BitReinterpreter.Convert(i1);
f2 = BitReinterpreter.Convert(i2);
const int tolerance = 0; // for comparison to Single.CompareTo()
int actual = FloatComparer.Compare(f1,f2,tolerance);
int expected = f1.CompareTo(f2);
if (actual != expected)
{
string n1 = System.Enum.GetName(typeof(Specials),val1);
string n2 = System.Enum.GetName(typeof(Specials),val2);
Console.Error.WriteLine("Failure: {0} vs {1}", n1,n2);
Console.Error.WriteLine("\t{0:X8} ({1}) vs {2:X8} ({3})", val1,f1,val2,f2);
Console.Error.WriteLine("\tactual: {0}, expected: {1}", actual,expected);
}
}
return true;
}
private enum Specials:uint
{
PositiveInfinity=
0x7F800000,
PositiveNearInfinity=
0x7F7FFFFF,
PositiveMidrange=
0x40E00000,//+7
PositiveNearZero=
0x00000001,
PositiveZero=
0x00000000,
NaN=
0xFFC00000,
NegativeZero=
0x80000000,
NegativeNearZero=
0x80000001,
NegativeMidrange=
0xC0E00000,//-7
NegativeNearInfinity=
0xFF7FFFFF,
NegativeInfinity=
0xFF800000
}
[Jitsu.Testing.UnitTest]
private static bool TestPrecisionErrorsAtRandom()
{
// Run a few thousand iterations of this random fuzz test.
for (int i=0; i < 10000; ++i)
{
// Construct a random float value.
f1 = GetRandomFloat();
// Run some math on it, accumulating some error along the way.
f2 = (float)Math.Pow(Math.Abs(f1),0.25);
f2 = ((f1 < 0f) ? -1 : +1) * (float)Math.Pow(f2,4.0);
// Compare, with a tolerance of 3 steps.
int d;
if (0 != FloatComparer.Compare(f1,f2, 3, out d))
{
int i1 = BitReinterpreter.Convert(f1);
int i2 = BitReinterpreter.Convert(f2);
Console.Error.WriteLine("{0}({1:X8}) != {2}({3:X8}), d={4}",f1,i1,f2,i2,d);
}
}
return true;
}
private static volatile float f1,f2; // to avoid in-line storage in x87 registers
private static float GetRandomFloat()
{
int i = rng.Next(Int32.MinValue,Int32.MaxValue);
i &= ~0x00800000; // mask out the infinity/nan range
float f = BitReinterpreter.Convert(i);
return f;
}
private static Random rng = new Random(7);
#endif
}
}
