News for hackers. Stuff that matters.
Re:Making all your integers positive with zigzag encoding by fluoridation on Friday November 25, 2022 @04:16PM (#33746867)
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.
Re:Making all your integers positive with zigzag encoding by Someone on Saturday November 26, 2022 @07:21AM (#33752071)
> 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_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_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.