3/31/2024 0 Comments Mapping onto vs one to oneThe mapping for two maximum most 16 bit integers (65535, 65535) will be 8589803520 which as you see cannot be fit into 32 bits.Įnter Szudzik's function: a >= b ? a * a + a + b : a + b * b where a, b >= 0 This may not be of little practical importance in programming world.Ĭantor pairing function: (a + b) * (a + b + 1) / 2 + a where a, b >= 0 That is, if my inputs are two 16 bit integers ranging from 0 to 2^16 -1, then there are 2^16 * (2^16 -1) combinations of inputs possible, so by the obvious Pigeonhole Principle, we need an output of size at least 2^16 * (2^16 -1), which is equal to 2^32 - 2^16, or in other words, a map of 32 bit numbers should be feasible ideally. The limitation of Cantor pairing function (relatively) is that the range of encoded results doesn't always stay within the limits of a 2N bit integer if the inputs are two N bit integers. Cantor pairing function is really one of the better ones out there considering its simple, fast and space efficient, but there is something even better published at Wolfram by Matthew Szudzik, here.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |