Interleaving the binary encodings of the two numbers a and b
seems to be the best solution: For example the encoding of a =
20d = 10100b b = 5d = 101b We interleave the bits starting with
the least significant bits (we pad shorter numbers with 0's so
they are the same length). The two original numbers resulting
paired number is 0100110010b = 306d This pairing function can be
easily decoded in computed and reversed by a constant time.depth
(see http://mathworld.wolfram.com/PairingFunction.html, depth
1?) circuit and so is in FAC0. - Pigeon, P. Contributions à la
compression de données. Ph.D. thesis. Montreal, Université de
Montréal, 2001. (page 115)