When is it worth using Hexadecimal over Decimal?

Question

How many bits does a number need to have, to make it worth using hexadecimal notation of the form 0xHHH...H over its decimal representation of the form DDD...D?

Here, "being worth" is defined as "giving a shorter average length for uniformly distributed values in the range $0$ to $2^N-1$", where $N$ is the number of bits. Negative numbers are not considered.

For example, clearly for all $N \ge 64$ it's worth using hexadecimal over decimal, because 18446744073709551615 has length 20, while 0xFFFFFFFFFFFFFFFF has length 18, and there are many more decimal numbers within the range that are longer than their hexadecimal counterparts than shorter, making it pretty obvious that the decimal lengths in the range where the decimal numbers are shorter don't compensate for the hex gain with greater lengths.

Extra credit for giving solutions to the same problem but with these representations for hexadecimal:

• HHH...Hh (e.g. E5F3h, 3FEh)
• DHHH...Hh (i.e. add leading zero if it starts with a letter, e.g. 0E5F3h, 3FEh)

Answer 1

For $n$-bit numbers, $2^n$ times the average number of base-$b$ digits required -- equivalently, the total number of digits required to write down all the $n$-bit numbers -- equals (probability of needing at least 1 digit) + (probability of needing at least 2 digits) + etc., which equals $\sum_{k>0} (2^n-b^{k-1})$ with the provisos that (1) when $k=0$ we take $b^{k-1}=0$ and (2) when the summand is negative we replace it with zero. (Each summand is then the number of $n$-bit numbers that are not representable using fewer than $k$ base-$b$ digits.)

This is of course evaluable in closed form without much pain but I am lazy and just wrote a program to do it. The result is that (with the extra two characters for 0x) hex wins once

$n>=40$ (where $2^n$ times the average number of characters is 13182540049978 for decimal and 13120838758128 for hex).

With the more economical (but to my mind uglier) suffix-h notation, hex wins once

$n>=20$ (where $2^n$ times the average number of characters is 6228922 for decimal and 6221552 for hex).

The third notation (with a leading 0 when, and only when, the number's hex representation starts with a letter) is a little hairier. We need at least one character always; at least two when the number is at least 10; at least three when it is at least 160; etc. Again, there is certainly a not-too-painful closed form; again, I am lazy; if my code isn't made of bugs then hex wins once

$n>=24$, at which point $2^n$ times the average number of characters is 123106618 for decimal and 123032918 for hex.

Answer 2

The solution for the first problem is

41 bits.

Reasoning:

(counting from 1, as that makes the math easier)

DECIMAL
For the first 9 * 1 = 9 numbers, you need 9 * 1 = 9 digits.
For the next 9 * 10 = 90 numbers, you need 90 * 2 = 180 digits.
For the next 9 * 100 = 900 numbers, you need 900 * 3 = 2700 digits.
In general, for all numbers with $n$ digits (those between $10^{n-1}$ and $10^n$) you need $9n \cdot 10^{n-1}$ digits.
Summing this (it's a harmonic series) gives a formula for the number of digits needed to write all numbers with up to $n$ digits: $(n-\frac{1}{9}) \cdot 10^n + \frac{1}{9}$.
The average for all $10^n$ numbers is thus approximately $n-\frac{1}{9}$.

HEXADECIMAL
For the first 15 numbers, you need 15 * 3 = 45 digits.
For the next 15 * 16 numbers, you need 15 * 16 * 4 = 960 digits.
For the next 15 * 256 numbers, you need 15 * 256 * 5 = 19200 digits.
In general, for all numbers with $x$ digits (those between $16^{x-1}$ and $16^x$) you need $15(x+2) \cdot 16^{x-1}$ digits.
Summing this gives a formula for the number of digits needed to write all numbers with up to $x$ digits: $(x+2-\frac{1}{15}) \cdot 16^x - \frac{29}{15}$.
The average for all $16^x$ numbers is thus approximately $x+2-\frac{1}{15}$.

While these formulas are only valid for integer values of $n$ and $x$ (so for numbers up to $10^n$ for the total number of decimal digits, and up to $16^x$ for the hexadecimal case), it's interesting to see where they intersect, because from that point on, the hexadecimal numbers are bound to be shorter on average. We know $10^n = 16^x$, so $x = n \cdot \log_{16}10$. Plugging this into the equation $n - \frac{1}{9} = x + 2 - \frac{1}{15}$ gives:

$n - \frac{1}{9} = n \cdot \log_{16}10 + 2 - \frac{1}{15}$

$n (1 - \log_{16}10) = \frac{29}{15} + \frac{1}{9} = \frac{92}{45}$

$n = \frac{92}{45 (1 - \log_{16}10)}$

The number of bits is a factor $\log_2 10$ higher than $n$, so $\frac{92 \log_2 10}{45 (1 - \log_{16}10)} = \frac{92}{45(\log_{10}2 - \frac14)} \approx 40.06$. So while at 40 bits, decimal is shorter, at 41 bits, we expect the hexadecimal notation to win.

For the second problem, the main equation becomes

$n - \frac{1}{9} = x + 1 - \frac{1}{15}$

which leads to a number of bits equal to

$\frac{47}{45(\log_{10}2 - \frac14)} \approx 20.47$

so the cutoff is here already 21 bits.

Answer 3

I would have to say

16 bits or 15 bits technically

This is because

at 14 bits 0x3FFE = 16,382. At this point the DEC is larger than the HEX representation. So at this point if the binary was increased by another bit, more than 50% of the conversion from DEC to HEX would be shorter than the DEC representation. Thus, making it "worth it".