I began my day today with this interesting question about how large factorials are in terms of digits. Which brought back another interesting question I had to answer many years ago: if you represent a number \(n\) in both decimal and binary, how much more space is writing the binary string expected to take? And by space I mean character length. I forget the context - maybe something to do with storage efficiency? - but I haven’t posted in a while, and this is a delightful little problem, so why not?

Here are some examples of decimal to binary conversions, and the binary-to-decimal length ratio:

Decimal Binary Length
3 11 2x
400 110010000 3x
99 1100011 3.5x
5000 1001110001000 3.25x


My question is: what is an approximate value for the last column? Especially for large \(n\).

To answer, first think about how we might mathematically calculate the string length of a number \(n\), when represented in decimal. I will denote this by \(L_{10}(n)\). One way to approach this is that when you divide \(n\) by \(10\) you move the decimal point leftwards by exactly one position, e.g., \(347/10=34.7\). The number of digits then is how many such left shifts are possible. Or to rephrase, how many such divisions by \(10\) are possible until the number becomes less than \(1\).

Dividing a number multiple times by \(10\) also (trivially) implies that you could construct that number by multiplying \(10\)s, i.e., \(10^x=n\), where \(x\) is not necessarily an integer. For example, \(10^{2.54} \approx 347\). So really, we need to determine \(x\) to obtain the approximate length of \(n\). But that’s just \(log_{10}(n)\)! Of course, string lengths aren’t fractional, so we’ll make an adjustment: \(L_{10}(n)=\lfloor log_{10}(n) \rfloor + 1\).

The binary string length may be similarly found. Recall that we convert a decimal number to binary by repeatedly dividing by \(2\). By the same logic as before, we’ve \(L_{2}(n) = \lfloor log_{2}(n) \rfloor + 1\).

Almost there … we want:

\[\frac{L_{2}(n)}{L_{10}(n)} = \frac{\lfloor log_{2}(n) \rfloor + 1}{\lfloor log_{10}(n) \rfloor + 1} \approx\frac{log_{2}(n)}{log_{10}(n)} = log_{2}(10)=3.32\]

The result is an approximation because we ignored the floor functions and the “\(+1\)”. The final simplification is a property of logarithms: \(log_p(x)/log_q(x)=log_p(q)\).

That’s our answer - we can expect the binary representation of a number to be around \(\textbf{3.32}\) times as long as the decimal representation.

Here’s a plot that shows this is a fairly good approximation. I ran through integers from \(1\) upto five million (x-axis), and for each integer, computed the ratio of the binary-to-decimal lengths (y-axis). This works better for larger numbers since ignoring the floor functions has a smaller impact on the ratio \(L_{2}(n)/L_{10}(n)\). Not too bad for a back-of-the-envelope calculation!

binary_lengths