Radix Economy

In a coffee shop this afternoon, I was reading an interesting article in Quanta Magazine titled How Base 3 Computing Beats Binary. I like the graphic also that began the article and which I've reproduced in Figure 1.

Figure 1: source

The article introduces the notion of "radix economy" that is explained as follows:

The hallmark feature of ternary notation is that it’s ruthlessly efficient. With two binary bits, you can represent four numbers. Two “trits” — each with three different states — allow you to represent nine different numbers. A number that requires 42 bits would need only 27 trits.

If a three-state system is so efficient, you might imagine that a four-state or five-state system would be even more so. But the more digits you require, the more space you’ll need. It turns out that ternary is the most economical of all possible integer bases for representing big numbers.

To see why, consider an important metric that tallies up how much room a system will need to store data. You start with the base of the number system, which is called the radix, and multiply it by the number of digits needed to represent some large number in that radix. For example, the number 100,000 in base 10 requires six digits. Its “radix economy” is therefore 10 × 6 = 60. In base 2, the same number requires 17 digits, so its radix economy is 2 × 17 = 34. And in base 3, it requires 11 digits, so its radix economy is 3 × 11 = 33. For large numbers, base 3 has a lower radix economy than any other integer base.

This Wikipedia article explains it in more formal terms for a number \(N\):$$ \text{radix economy of } N =b \lfloor \log_b(N)+1 \rfloor $$For large \(N\) we can thus write:$$ \begin{align} \text{radix economy of } N &\approx b \log_b(N) \\ &= \frac{b}{ln \,(b)} ln \,(N) \end{align}$$Using the number 123456789 as an example, the radix efficiency for integer bases from 3 to 16 is shown in Figure 2.

Figure 2: base 3 is best

The Quanta article goes on to say that:

In addition to its numerical efficiency, base 3 offers computational advantages. It suggests a way to reduce the number of queries needed to answer questions with more than two possible answers. A binary logic system can only answer “yes” or “no.” So if you’re comparing two numbers, x and y, to find out which is larger, you might first ask the computer “Is x less than y?” If the answer is no, you need a second query: “Is x equal to y?” If the answer is yes, then they’re equal; if the answer is no, then y is less than x. A system using ternary logic can give one of three answers. Because of this, it requires only one query: “Is x less than, equal to, or greater than y?”

And finally, also quoting from the article:

Surprisingly, if you allow a base to be any real number, and not just an integer, then the most efficient computational base is the irrational number e.

The table in Figure 2 looks as shown in Figure 3 when we add "e" to the list of bases.

Figure 3: e is best

Representing numbers using "e" as the number base is the stuff of a future post perhaps but here is a link to how to go about it.