The pairing function f(a,b) = (a + b)(a + b + 1)/2 + a is the one that arises by drawing diagonals on the natural number lattice, and marching down them from upper left to lower right. See the picture here.
To compute f(a,b), one needs to perform some additions and a multiplication, which seems to be quadratic time in the length of a and b, that is, in log(a)+log(b), which would seem to be constant time in max(a,b), but I'm not sure if this would be what you meant.
In that book, it is noted that Polya has proved that any surjective polynomial pairing function is equal to this function or to its dual form f(b,a). (And someone gave a talk here at CUNY a few weeks ago on precisely this fact.) So if this function is not acceptable to you, then you will find no polynomial surjective function.
But here is another function, which seems to be a little faster to compute. Suppose that a and b are given to me in their binary representation. Now, I just interleave their binary digits, using 0's if the digits of one of them runs out. This is surely a pairing function, and I can compute it linear time of the lengths of the input.
No comments:
Post a Comment