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.
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 where we use the floor function
is therefore, in some senses, more efficient than a base with a higher average value.
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
is the total number of digit faces needed to inclusively represent any integer from 0 to N. The quantity
for large N can be approximated as follows: The asymptotically best value is obtained for base 3, since
of bases b1 and b2 may be compared for a large value of N: Choosing e for b2 gives The average
of various bases up to several arbitrary numbers (avoiding proximity to powers of 2 through 12 and e) are given in the table below.
, making unary the most economical for the first few integers, but this no longer holds as N climbs to infinity.
N = 1 to 6 N = 1 to 43 N = 1 to 182 N = 1 to 5329 One result of the relative economy of base 3 is that ternary search trees offer an efficient strategy for retrieving elements of a database.
[1] In a d-ary heap, a priority queue data structure based on d-ary trees, the worst-case number of comparisons per operation in a heap containing
choices per step, the time to traverse the menu is proportional to the product of
(the number of choices that need to be made to determine the outcome).
From this analysis, the optimal number of choices per step in such a menu is three.
[1] 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: The authors conclude, Under these assumptions, the radix 3, on the average, is the most economical choice, closely followed by radices 2 and 4.
These assumptions are, of course, only approximately valid, and the choice of 2 as a radix is frequently justified on more complete analysis.