An Elegant Pairing Function [pdf] (opens in new tab)

(szudzik.com)

3 pointscodeismightier11y ago3 comments

3 comments

|R x R| = |R| so the existence of such functions is guaranteed but it is nice to see that some are just a method call away. Does anyone know what pairing function on non negative integers is the most efficient in the number of bits it requires ?

Someone11y ago

This PDF only handles mapping N x N to N and vice versa, though.

For R x R, I would mix the bits of the two numbers

  [a0 a1 a2 a3...]
  [b0 b1 b2 b3...]

  [a0 b0 a1 b1 a2 b2 a3 b3...]

I am not sure that is a computable function for infinite-length bit sequences, though. Maybe none of those mapping functions are?

sorokod11y ago

Ah yes, I was thinking |N x N| = |N|. So is there a pairing function f: NxN -> N which can be used as compression?

j / k navigate · click thread line to collapse

3 comments

sorokod11y ago

Someone11y ago

This PDF only handles mapping N x N to N and vice versa, though.

For R x R, I would mix the bits of the two numbers

  [a0 a1 a2 a3...]
  [b0 b1 b2 b3...]

  [a0 b0 a1 b1 a2 b2 a3 b3...]

I am not sure that is a computable function for infinite-length bit sequences, though. Maybe none of those mapping functions are?

sorokod11y ago

Ah yes, I was thinking |N x N| = |N|. So is there a pairing function f: NxN -> N which can be used as compression?

j / k navigate · click thread line to collapse