Universal Coding of the Reals using Bisection

We propose a simple yet expressive framework for encoding any real number as a binary string based on bisecting intervals, starting with (--∞, +∞). Each bit of such a string represents the outcome of a binary comparison with a value contained in the interval. Our framework draws upon ideas from unbounded search and binary search, and requires only the specification of two functions: a generator for producing a monotonic sequence that brackets the number being encoded, and a refinement operator that computes an "average" of two finite numbers. Our framework is flexible enough to support many well-known representations, including Posits, Elias codes, logarithmic number systems, and a slightly modified version of ieee floating point. We show that the associated generators are simple expressions given by hyperoperators. Moreover, the generality of our approach allows for exponent-less number systems based on Fibonacci and other sequences. We further analyze the probability densities associated with known and new encoding schemes and show how a compatible refinement operator and density can be derived from the bracketing sequence. This gives an almost everywhere smooth mapping between bit strings and real numbers and shows, for instance, that Posits follow a Pareto distribution. Contributions of our work include new insights into existing number systems, suggestions for how to build new, perhaps exponent-less number systems, a method for designing number systems that match a desired density, and a much simpler and verifiably correct implementation of existing representations using as few as two lines of code.