Best. Number Base. Ever.

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.”

coin-obverse-small

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 B digits “costs” \gamma{}B, where \gamma>0 is a constant. A number N expressed in base B will be \log_B N base B digits long. If each digit costs \gamma{}B, then we can write the cost of encoding N in base B as:

A(B,N)=\gamma B \log_B N

And we want to find B that minimizes A(B,N) over all numbers. Fortunately for us, A(B,N) is convex in B, so solving

\displaystyle \frac{\partial}{\partial{}B}A(B,N)=0

will give us the desired, optimal B. Don’t be scared, all you need to solve the above is calculus 101. Let’s do it!

\displaystyle \frac{\partial}{\partial{}B}A(B,N)=\frac{\partial}{\partial{}B}\gamma{}B\log_B N

\displaystyle=\gamma\left(B\frac{\partial}{\partial{}B}\log_B N+\log_B N\frac{\partial}{\partial{}B}B\right)

\displaystyle=\gamma\left(B\left(-\frac{\ln N}{B (\ln B)^2}\right)+\frac{\ln N}{\ln B}\right)

\displaystyle=\gamma\left(\frac{\ln N}{\ln B}-\frac{\ln N}{(\ln B)^2}\right)

\displaystyle=\gamma\left(\frac{\ln B-1}{(\ln B)^2}\right)\ln N

And this is zero whenever \ln B-1=0. This results in B=e=2.71828182845904\ldots as the optimal solution. Since B=e is not an integer solution, and that 2<e<3, we examine B=2 and B=3 to determine which is best. With B=2, \ln 2-1=-0.44269\ldots, and with B=3, \ln 3-1=0.08976\ldots, 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 \gamma{}B \log_B N is not very good as a cost function representing hardware implementation costs. Hardware gets expensive quickly. Let us rather consider now:

A_2(B,N)=\gamma B^2 \log_B N

This is also very fortunately a convex (“convex up”) function in B, so we can find the optimal B for A_2(B,N) (for all N) using the same technique as before, that is, solving

\displaystyle \frac{\partial}{\partial{}B}A_2(B,N)=0

Let’s cut short on the derivation, it’s essentially the same, except with B^2, and we arrive at

\displaystyle \frac{\partial}{\partial{}B}A_2(B,N)=\gamma\left(\frac{B(2\ln B-1)}{(\ln B)^2}\ln N\right)=0

which we want to solve for B. Again, we only need to solve for 2\ln B-1=0, for which we find B=e^\frac{1}{2}=\sqrt{e}=1.64872\ldots. And since 1<\sqrt{e}<2, we consider 1 and 2 as optimal (integer) solutions. 1 is to be rejected right off the bat, since \log_1 does not make sense, leaving 2 as the only good solution. Therefore, if the cost function is A_2(B,N), then binary is indeed optimal!

*
* *

So we derived the results analytically, and saw that depending on the cost function, you can get different answers, B=3 is best in the first case, and B=2 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 \log N part?

Remember, I’ve stated that the cost functions were convex in B. What does it mean? Let us have a look at the plot of the two cost functions.

surfaces-axes

This graph shows the A(B,N) function in blue, the A_2(B,N) 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 B=1 then slowly grows back as B grows, and that it monotonically grows in N. We are interested in the optimal B where overall A_2(B,N) is the smallest. We find that the minimum is marked here:

surfaces-axes-solutions

Where B=\sqrt{e}, making B=2, 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 B^k yields \sqrt[k]{e} 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.

One Response to Best. Number Base. Ever.

  1. Reblogged this on nurdinawatikudus and commented:
    I wonder why it is called “Best Ever Number Base” ….

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: