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