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.

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;

}

Is this only for INTs or LONGs as well? I was trying to put this code into Java, but the reverse doesn't work for large numbers (Iike 1350642439149, long returned by System.currentTimeMillis())

ReplyDeleteI haven't tried it for longs but I guess using a double where ulong is used in the above code might work.

ReplyDeleteS