4 ms·

A nice bijection from integers to natural numbers. Mappings exist for rationals -> natural numbers and other countable sets, but may be less practical.

fluoridation 4y ago
Easy enough. If you have a rational class represented as a pair of irreducible int32_ts, you can simply do ((u64)numerator << 32) | (u64)denominator.
- Someone 4y ago
  That either doesn’t map to rationals (making 1/1 and 2/2 two different numbers) or not a bijection (0x0000000100000001 and 0x0000000200000002 both map back to 1) and doesn’t work on “the integers”.
  - fluoridation 4y ago
    Most people just care about having a lossless round-trip conversion, from the source representation to a storage representation and then back to the source representation, not about having every possible bit sequence in the storage representation being valid. Univocally mapping the rationals onto a set of contiguous naturals is extremely tricky, computationally.
    - Someone 4y ago
      > Univocally mapping the rationals onto a set of contiguous naturals is extremely tricky, computationally. It is not that difficult. https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Stern's_diatomic_sequence https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Stern's_diato... defines fusc(n), a function that’s fairly easy to compute (it is recursively defined, but only requires a recursion depth of the number of bits in the binary presentation of n), with fusc(n)/fusc(n+1) being a mapping from the natural numbers to all positive rational numbers. That Wikipedia page also hints at how to implement the reverse. https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Definition_and_structure https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Definition_an...: “The parent of any rational number can be determined after placing the number into simplest terms, as a fraction a/b for which greatest common divisor of an and b is 1. If a/b < 1, the parent of a/b is a/(b − a); if a/b > 1, the parent of a/b is (a − b)/b.”* Repeatedly using that procedure, you eventually reach 1, and then have found the path from 1 down to your starting number a/b. if you have that finding the n for which fusc(n)/fusc(n+1) = a/b is trivial.
  - karamanolev 4y ago
    "pair of irreducible int32_ts" 2/2 is not irreducible, so not an issue. But yes, it does create some waste in the encoding. Not obvious how to fix it, as coprimality is hard to encode for.

fluoridation 4y ago

Easy enough. If you have a rational class represented as a pair of irreducible int32_ts, you can simply do ((u64)numerator << 32) | (u64)denominator.

Someone 4y ago
That either doesn’t map to rationals (making 1/1 and 2/2 two different numbers) or not a bijection (0x0000000100000001 and 0x0000000200000002 both map back to 1) and doesn’t work on “the integers”.
- fluoridation 4y ago
  Most people just care about having a lossless round-trip conversion, from the source representation to a storage representation and then back to the source representation, not about having every possible bit sequence in the storage representation being valid. Univocally mapping the rationals onto a set of contiguous naturals is extremely tricky, computationally.
  - Someone 4y ago
    > Univocally mapping the rationals onto a set of contiguous naturals is extremely tricky, computationally. It is not that difficult. https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Stern's_diatomic_sequence https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Stern's_diato... defines fusc(n), a function that’s fairly easy to compute (it is recursively defined, but only requires a recursion depth of the number of bits in the binary presentation of n), with fusc(n)/fusc(n+1) being a mapping from the natural numbers to all positive rational numbers. That Wikipedia page also hints at how to implement the reverse. https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Definition_and_structure https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Definition_an...: “The parent of any rational number can be determined after placing the number into simplest terms, as a fraction a/b for which greatest common divisor of an and b is 1. If a/b < 1, the parent of a/b is a/(b − a); if a/b > 1, the parent of a/b is (a − b)/b.”* Repeatedly using that procedure, you eventually reach 1, and then have found the path from 1 down to your starting number a/b. if you have that finding the n for which fusc(n)/fusc(n+1) = a/b is trivial.
- karamanolev 4y ago
  "pair of irreducible int32_ts" 2/2 is not irreducible, so not an issue. But yes, it does create some waste in the encoding. Not obvious how to fix it, as coprimality is hard to encode for.