Curiosity is bliss    Archive    Feed    About    Search

Julien Couvreur's programming blog and more

The efficiency of ternary base

 

Here is an old but interesting article about numeric bases and their efficiency.

Different bases have different "efficiencies".
Base 10000, for example, has a really huge alphabet (0 thru 9999) but may express large numbers with very few digits (9999 is just one digit, in comparison to 4 in base 10).
Base 2, on the other hand, has a small alphabet (only 2 symbols) but requires more digits to express large numbers (14 digits are required to write the number 9999).

The problem is then to optimize both the number of symbols in the alphabet and the number of digits needed to express a given large number, by minimizing the product of these two indicators for example. This approach brings out the ternary base as being the most efficient.

Finding the minima
Although the calculus is pretty simple, it's been a couple years since I hadn't done such a function analysis, so I wanted to verify I could still do it.

Here is how you get to the result described in the article:
Let's call b the base (>1) and n the number of digits needed to express some large number N in that base. We want to minimize bxn.
Because N=b^n, you can write n=log(N)/log(b).
So we are now trying to minimize b/log(b), which is defined for b in ]0,1[ and ]1,∞[, and can be derived on those interval.
The derived function is 1/log(b) - 1/log(b)^2.
Given that log(b)<1 for b in ]1,e[ and log(b)>1 for b in ]e,∞[, we find the minima we were looking for: b=e.

comments powered by Disqus