Efficiency of representations of number

Question

In everyday practice the most common ways to represent integers are the binary and decimal systems. We use floating point or fixed point systems to (approximately) represent the reals. There are some other ways, not so widely used in computational sciences, such as continued fractions, and the use of the square root sign.

1. Is there a way to formally assess the efficiency of these representations? Can we say, in some sense, the usual place-valued digital representation is the best way to represent integers?
2. Similarly, is there a theoretical basis for saying that the floating point numbers are the best way to approximately represent real numbers?

The question is a big vague because the meanings of "efficiency" and "best" are also part of the question. Without these words, perhaps a reformulation would be: Do we have any justification to use the standard methods, beyond the fact that they are traditional, reasonably convenient, and we (arguably) do not know anything else to replace them yet?

Answer 1

It depends what your criteria for efficiency is. Sticking to machine implemented arithmetic,

• I remember hearing as a freshman that for integers, base $e$ was optimal but, if you must use an integer base, then base $3$ is slightly better than base $2.$

• Floating point and fixed point approximate reals by rationals, usually with denominator a power of $2$ or $10.$ I have also seen arguments that approximating reals by the rationals which arise from continued fractions (ie the Eucludean algorithm ) makes better sense than using fixed point (consult the articles I linked if you want to see what, if anything, they say about floating point.)

I'll give justifications for both.

For the first claim about $2,e$ and $3$ I think the argument (which was over my head at the time) was as follows: If we want to represent an unknown integer $n$ two extreme and unsatisfactory solutions are unary (base $b=1$), and base $b=N$ where $N$ is immensely huge. In base $b=1$ we using a string of $n$ ones so the alphabet is simple but the number of digits is large. If $N$ is huge enough then only a single digit is needed, although the alphabet is huge. It is reasonable (one smoothly says) to try to minimize $b\cdot d_n$ where $d_n$ is the number of base $b$ digits needed to represent $n.$ So $d_n=\log_b{n}=\frac{\ln{n}}{\ln{b}}$ and we wish to minimize $\frac{b}{\ln{b}}\ln{n}.$ Evidently the $b$ giving the minimum is independent of $n$ and, setting the derivative $\left(\frac{b}{\ln{b}}\right)'=\frac{\ln{b}-b/b}{(\ln{b})^2}$ to zero we see that $b=e$ is optimal. $\frac{2}{\ln{2}}\gt 2.88$ while $\frac{3}{\ln{3}} \lt 2.731.$ So $2$ is good but $3$ better by this measure. Binary is quite elegant however and does have its charms. For example in long division (naively) one must guess the next digit of the the quotient. In base $b=2$ you need only decide between $0$ and $1$. Binary circuitry is streamlined as well.

For the second I'll just give give some rhetoric and then two references. How can it be satisfactory in fixed point that you can't get $\frac13$ exactly? Representing positive reals as $\frac{p}{q}$ where $p$ and $q$ together have $w$ bits (where $w$ is the word length) extends exact integer arithmetic to exact rational arithmetic for simple rationals and for reals gives a smooth transition of precision as the size changes. And perhaps in some settings one really does care about rational values. I imagine this would make $x$ and $1/x$ always multiply out to $1.$ in general, in approximating a calculation whose exact answer should be a rational, the simpler that rational, the greater the approximation error which will be exactly corrected . For implementation details and a better thought out rationale I found an early paper by E. C. R. Hehner and R. N. S. Horspool and a later one by Peter Kornerup and David Matula. Their systems may not be exactly the same.

Answer 2

The following assumptions seem natural:

1. Each natural number $0,1,2,\dots$ is to be represented by a nonempty binary string.
2. Smaller numbers are to have shorter representations.
3. No two strings should represent the same number.

From these we get $$0 \mapsto 0,\quad1\mapsto 1,$$ $$00,01,10,11\mapsto 2,3,4,5\quad\text{(in some order)},\quad \dots$$ However, we may also want

4. Addition should be easy using our representations.

To achieve (4), let's scrap (3), allowing "$0=00$" for instance. Then we can use the usual system, $$x_1\ldots x_n\mapsto \sum_i x_i2^{n-i}$$ although perhaps the left-handed ones among us would prefer $$x_1\ldots x_n\mapsto \sum_i x_i2^{i}.$$

Answer 3

Well, the idea behind floating-point numbers is simply having a representation that bounds the relative error between any number $x$ and its closest representable number $\mathrm{fl}(x)$. With the classical double-precision floating point numbers, for any $x$ such that $10^{-308} \leq |x| \leq 10^{308}$ (bounds "large enough" for almost all possible applications), one has $\frac{|x-\mathrm{fl}(x)|}{x} \leq u$, for a very small constant $u=2^{-53 } \approx 2\times 10^{-16}$). This is the same rationale behind scientific notation: you care only about a certain number of "most significant" digits.

There can be different ways to achieve this bound, but one of the simplest ones to implement in the context of a computer working with binary numbers is using base-2 scientific notation, which is precisely what floating point numbers are.

If you try to minimize the absolute error $|x-\mathrm{fl}(x)|$ instead, you end up with fixed-point representations, which means equispaced numbers.