5 ms·

Re: pairing functions, two of my favorite are: 1. Moser–de Bruijn sequence https://en.wikipedia.org/wiki/Moser%E2%80%93de_Bruijn_sequence https://en.wikipedia.

• psykotic 8y ago
  Yeah, if you use the Moser-de Bruijn sequence for constructing a pairing function you just get bit interleaving. You define the map expand(x_0, x_1, ..., x_n) = (x_0, 0, x_1, 0, ..., 0, x_n), apply it to x and y, multiply expand(y) by 2 to shift it over, and add them to merge the now disjoint even/odd positions. Incidentally, this decomposition of the problem is exactly how you efficiently implement bit interleaving in software except you don't even need addition: z = interleave(x, y) = expand(x) | (expand(y) << 1) For the inverse you define the map compact(x_0, x_1, ..., x_2n) = (x_0, x_2, ..., x_2n) and then uninterleave(z) = (compact(z), compact(x >> 1)) = (x, y) The expand map can be implemented efficiently as a logarithmic number of shift-and-merge stages, and compact can be constructed by inverting each stage separately and composing them in reverse order. A stage has this form: x' = x | (x << n) You sometimes also see it written with xor. That's not necessary. What you care about is that the operation is bitwise (e.g. no carries from addition) and it must have 0 as an identity. If x has 2n bits then this is reversible: the lower n bits in x and x' are the same, and the upper n bits in x and (x' >> n) are the same, so you can recover all 2n bits of x from x' with low(x') | high(x' >> n). You can cascade stages like this if you alternate them with appropriate masking to allow data-parallel operation. The net effect of the first stage, after masking, is to shift the upper n bits of x up by n bits while leaving the lower n bits in place. The next stage then does the same thing on the two halves in parallel with a shift of n/2, and so on until you're done. The masking prevents cross-talk between subvectors so you can operate on a single vector as if it were a set of independent subvectors. Or put another way, it enforces the precondition for the reversibility of each stage. Anyway, just some random connections to low-level hacking.