One of the first things we learn when we begin programming is that there are different number bases: base 10, the usual one, but also binary, octal, and hexadecimal. Their expressive power is strictly equivalent, but we also notice that hexadecimal numbers are written much more compactly than binary, and so, hexadecimal is “more efficient.”
But “efficiency” begs the question: how do we define it, and, once efficiency defined, which base is the best? Let’s find out!
First, representing a digit (let’s use the word digits for all the variants, despite digit meaning base-10 digit; so bits are digits too) in the computer (in a file in a piece of hardware in the CPU) costs something which isn’t necessarily bits; it costs hardware, power, and complexity of circuit. If we use a linear function as a proxy of this cost, we can say that a base digits “costs” , where is a constant. A number expressed in base will be base digits long. If each digit costs , then we can write the cost of encoding in base as:
And we want to find that minimizes over all numbers. Fortunately for us, is convex in , so solving
will give us the desired, optimal . Don’t be scared, all you need to solve the above is calculus 101. Let’s do it!
And this is zero whenever . This results in as the optimal solution. Since is not an integer solution, and that , we examine and to determine which is best. With , , and with , , we safely conclude that base 3 is the best (integer) base.
Wait, wut? 3?
How come computers use base 2, then?
Well, for one thing, that’s mainly because is not very good as a cost function representing hardware implementation costs. Hardware gets expensive quickly. Let us rather consider now:
This is also very fortunately a convex (“convex up”) function in , so we can find the optimal for (for all ) using the same technique as before, that is, solving
Let’s cut short on the derivation, it’s essentially the same, except with , and we arrive at
which we want to solve for . Again, we only need to solve for , for which we find . And since , we consider 1 and 2 as optimal (integer) solutions. 1 is to be rejected right off the bat, since does not make sense, leaving 2 as the only good solution. Therefore, if the cost function is , then binary is indeed optimal!
So we derived the results analytically, and saw that depending on the cost function, you can get different answers, is best in the first case, and is better when the cost grows quadratically with the number of different digits, that is, the base. What does it look graphically, and why were we able to basically ignore the part?
Remember, I’ve stated that the cost functions were convex in . What does it mean? Let us have a look at the plot of the two cost functions.
This graph shows the function in blue, the function in red. Let us focus on the red—the same applies to the blue, but let’s focus on the red for now. We see that the function goes down from then slowly grows back as grows, and that it monotonically grows in . We are interested in the optimal where overall is the smallest. We find that the minimum is marked here:
Where , making , the next integer solution, optimal.
So next time you hear “this and that is the optimal thingie”, take some time to reflect “on optimal, but as measured by what?” The solutions of the “best base” problem I know of usually only consider only the linear cost, and not at all the quadratic version (and even less that cost functions in yields as optimal).
When binary imposed itself as the preferred base for computer arithmetic, was it a deliberate act of maximizing explicitly efficiency? Well, I do not know for sure. I think it was just that it was because it’s easier to do only on/off switches, and that was serendipitously convenient.