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.

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;
        }

Cantor Pairing Function and Reversal

Update - In case you have to pair very large non-negative integers, do read my post on Elegant Pairing Function.

In my last post on Dice Coefficients I talked about how a nested NxN loop for finding similarity can be changed to a reducing inner loop since Similarity Score between X,Y is reversible i.e. Sim{X,Y} = Sim{Y,X}. This means if you have 26 sets in the universe (from A-Z), you would hit the same pair twice while calculating the Dice Coefficient between them. If we can somehow, store the similarity already calculated in the first iteration between two sets (say A,B), then we don’t have to re-calculate the similarity between (B,A). Hence, our nested loop can be rewritten as-

            for (int i = 0; i < universe.length; i++)
{
for (int j = i + 1; j < universe.length; j++)
{
//calc similarity between set[i] & set[j]
                }
}

By the way, for a very large value of N (universe.length), the average complexity of the above algorithm is still ~ O(N^2) but at least we have reduced the number of iterations by nearly half.


Now that we have a similarity score between two sets, we would need a mechanism to store this score and somehow tag it with the Pair for which the similarity is calculated. Also, it would be nice if the scores can be stored in a hashtable (as retrieval is on average O(1)) and make our hashtable key uniquely identify the pair for which the score is calculated. In short, we need some way to uniquely encode two docIds into a single number – enter "Cantor Pairing Function”. Pairing functions is a reversible process to uniquely encode two natural numbers into a single number. Calculating the “Cantor Pair” is quite easy but the documentation on the reversible process is a little convoluted. Anyway, below is the C# code for generating the unique number and then reversing it to get back the original numbers (for x,y>0).

static int CantorPair(short x, short y)
{
return ((x + y) * (x + y + 1)) / 2 + y;
}

static short[] Reverse(int z)
{
short[] pair = new short[2];
int t = (int)Math.Floor((-1D + Math.Sqrt(1D + 8 * z))/2D);
int x = t * (t + 3) / 2 - z;
int y = z - t * (t + 1) / 2;
pair[0] = (short)x;
pair[1] = (short)y;
return pair;
}

As you can see the CantorPair() returns back an int for two shorts to avoid any number overflows, if you are trying to generate the pair number for two ints, you would need to use long.