Saturday, July 16, 2011

Another (Elegant) Pairing Function

 

In my last post I talked about Cantor Pairing function for uniquely pairing two integers into a single number. Unfortunately, I ran into some overflow issues with that when generating pairs for very big integers like int.Max – luckily, I don’t have to deal with such large numbers in my application!

Anyway, in case you do have to deal with very large numbers and are looking at reducing them into a single number then there’s another pairing function called Elegant Pairing Function (warning pdf), which lets you reduce 2 non-negative integers to a single pair.

image

I did run into some issues with rounding off errors while generating the square root due to the precision of the double data type (Math.Sqrt takes a double) causing the Math.Ceil value to be one higher. Basically, even though the square-root of 1152921506754330623 (the paired value of int.Max & int.Max-1) is 1073741824.9999999990686774262519 (which after calling the Math.Floor would return back 1073741824), the Math.Sqrt returns it as 1073741825. Once I found out that the problem was with the Math.Sqrt, the fix was easy – given that flooring the Square-root of a number might result in rounding error by 1, if you just check for that condition where Square Of Floor Of Square Root Of Number > Number, and just decrement the Floor by 1, you can successfully calculate the elegant pair and reverse them for any non-negative integers up to Int.Max. Below is the C# code for the calculation of the Elegant Pair along with the reversal -

        static ulong ElegantPair(uint x, uint y)
{
if (x >= y)
{
return (ulong)x * x + x + y;
}
else
{
return (ulong)y * y + x;
}
}

static uint[] ElegantReverse(ulong z)
{
uint[] pair = new uint[2];
double preciseZ = Math.Sqrt(z);
ulong floor = (ulong)Math.Floor(preciseZ);
if (floor * floor > z)
{
floor
--;
}
ulong t = z - (ulong)(floor*floor);
if (t < floor)
{
pair[
0] = (uint)t;
pair[
1] = (uint)floor;
}
else
{
pair[
0] = (uint)floor;
pair[
1] = (uint)t - (uint)floor;
}
return pair;
}