In mathematics and computer science, optimal radix choice is the problem of choosing the base, or radix, that is best suited for representing numbers. Various proposals have been made to quantify the relative costs of using different radices in representing numbers, especially in computer systems. One formula is the number of digits needed to express it in that base, multiplied by the base (the number of possible values each digit could have). This expression also arises in questions regarding organizational structure, networking, and other fields.
The cost of representing a number N in a given base b can be defined as
E(b,N)=b\lfloorlogb(N)+1\rfloor
logb
If both b and N are positive integers, then the quantity
E(b,N)
E(b,N)
For example, 100 in decimal has three digits, so its cost of representation is 10×3 = 30, while its binary representation has seven digits (11001002), so the analogous calculation gives 2×7 = 14. Likewise, in base 3 its representation has five digits (102013), for a value of 3×5 = 15, and in base 36 (2S36) one finds 36×2 = 72.
If the number is imagined to be represented by a combination lock or a tally counter, in which each wheel has b digit faces, from
0,1,...,b-1
\lfloorlogb(N)+1\rfloor
E(b,N)
The quantity
E(b,N)
E(b,N)=b\lfloorlogb(N)+1\rfloor\simb logb(N)={b\overln(b)}ln(N).
{E(b,N)\overln(N)}\sim{b\overln(b)}.
The asymptotically best value is obtained for base 3, since
b\overln(b)
b=3
{2\overln(2)} ≈ 2.88539,
{3\overln(3)} ≈ 2.73072,
{4\overln(4)} ≈ 2.88539.
{10\overln(10)} ≈ 4.34294.
The values of
E(b,N)
{{E(b1,N)}\over{E(b2,N)}} ≈ {{b1
{log | |
b1 |
(N)}}\over{b2
{log | |
b2 |
(N)}}} ={\left(\dfrac{b1ln(N)}{ln(b1)}\right)\over\left(\dfrac{b2ln(N)}{ln(b2)}\right)}={{b1ln(b2)}\over{b2ln(b1)}}.
Choosing e for b2 gives
{{E(b)}\over{E(e)}} ≈ {{bln(e)}\over{eln(b)}}={{b}\over{eln(b)}}.
The average
E(b,N)
E(1,N)
N
N
Base b | Avg. E(b,N)N = 1 to 6 | Avg. E(b,N)N = 1 to 43 | Avg. E(b,N)N = 1 to 182 | Avg. E(b,N)N = 1 to 5329 | {{E(b)}\over{E(e)}} | Relative size of E (b )/E (e ) |
---|---|---|---|---|---|---|
1 | 3.5 | 22.0 | 91.5 | 2,665.0 | infty | - |
2 | 4.7 | 9.3 | 13.3 | 22.9 | ||
e | 4.5 | 9.0 | 12.9 | 22.1 | ||
3 | 5.0 | 9.5 | 13.1 | 22.2 | ||
4 | 6.0 | 10.3 | 14.2 | 23.9 | ||
5 | 6.7 | 11.7 | 15.8 | 26.3 | ||
6 | 7.0 | 12.4 | 16.7 | 28.3 | ||
7 | 7.0 | 13.0 | 18.9 | 31.3 | ||
8 | 8.0 | 14.7 | 20.9 | 33.0 | ||
9 | 9.0 | 16.3 | 22.6 | 34.6 | ||
10 | 10.0 | 17.9 | 24.1 | 37.9 | ||
12 | 12.0 | 20.9 | 25.8 | 43.8 | ||
15 | 15.0 | 25.1 | 28.8 | 49.8 | ||
16 | 16.0 | 26.4 | 30.7 | 50.9 | ||
20 | 20.0 | 31.2 | 37.9 | 58.4 | ||
30 | 30.0 | 39.8 | 55.2 | 84.8 | ||
40 | 40.0 | 43.7 | 71.4 | 107.7 | ||
60 | 60.0 | 60.0 | 100.5 | 138.8 |
One result of the relative economy of base 3 is that ternary search trees offer an efficient strategy for retrieving elements of a database.[2] A similar analysis suggests that the optimum design of a large telephone menu system to minimise the number of menu choices that the average customer must listen to (i.e. the product of the number of choices per menu and the number of menu levels) is to have three choices per menu.[1]
In a -ary heap, a priority queue data structure based on -ary trees, the worst-case number of comparisons per operation in a heap containing
n
dlogdn
d=3
d=4
Brian Hayes suggests that
E(b,N)
n
r
r
logrn
The 1950 reference High-Speed Computing Devices describes a particular situation using contemporary technology. Each digit of a number would be stored as the state of a ring counter composed of several triodes. Whether vacuum tubes or thyratrons, the triodes were the most expensive part of a counter. For small radices r less than about 7, a single digit required r triodes.[4] (Larger radices required 2r triodes arranged as r flip-flops, as in ENIAC's decimal counters.)[5]
So the number of triodes in a numerical register with n digits was rn. In order to represent numbers up to 106, the following numbers of tubes were needed:
Radix r | Tubes N = rn | |
---|---|---|
2 | 39.20 | |
3 | 38.24 | |
4 | 39.20 | |
5 | 42.90 | |
10 | 60.00 |
The authors conclude,