37 ms·

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 repr

• 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.