Radix economy

Various proposals have been made to quantify the relative costs between using different radices in representing numbers, especially in computer systems.

Contents

Definition

The radix economy E(b,N) for any particular number N in a given base b is equal to the number of digits needed to express it in that base, multiplied by the radix:[1]


E(b,N) = b \lfloor \log_b (N) %2B1 \rfloor \, .

The radix economy measures the cost of storing or transmitting the number N in base b if the cost of each "digit" is proportional to b. A base with a lower average radix economy is therefore, in some senses, more efficient than a base with a higher average radix economy.

For example, 100 in decimal has three digits, so its radix economy is 10×3 = 30; its binary respresentation has seven digits (11001002) so it has radix economy 2×7 = 14 in base 2; in base 3 its representation has five digits (102013) with a radix economy of 3×5 = 15; in base 36 (2S36) its radix economy is 36×2 = 72.

The radix economy of bases b1 and b2 may be compared for a large fixed value of N:

{{E(b_1,N)} \over {E(b_2,N)}} \approx {{b_1 {\log_{b_1} (N)} } \over {b_2 {\log_{b_2} (N)}}} = { \left(\dfrac{b_1 \ln (N) }{ \ln (b_1) } \right) \over \left( \dfrac{b_2 \ln (N) }{ \ln (b_2)} \right) } = {{b_1 \ln (b_2)} \over {b_2 \ln (b_1)}}\, .

Since the function

y = \frac {x} {\ln(x)}\,

is strictly decreasing on 0 < x < e and strictly increasing on x > e, its minimum is at e, which is therefore the base with the lowest average radix economy. Since 2 / ln(2) ≈ 2.89 and 3 / ln(3) ≈ 2.73, it follows that 3 is the integer base with the lowest average radix economy.

The average radix economy of the integers from 1 to 100 in various bases is:

Base b Average of E(b,N)

for N=1 to 100
2 11.6
e 11.33524
3 11.52
4 12.76
10 19.2

Radix times required digits

The classic 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.[2] (Larger radices required 2r triodes arranged as r flip-flops, as in ENIAC's decimal counters.)[3]

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,

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. Even with the optimistic assumption that 10 triodes will yield a decimal ring, radix 10 leads to about one and one-half times the complexity of radix 2, 3, or 4. This is probably significant despite the shallow nature of the argument used here.[4]

A similar analysis suggests that the optimum design of a large telephone menu system to minimise the number of menu choices that a 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]

Other criteria

In another application, the authors of High-Speed Computing Devices consider the speed with which an encoded number may be sent as a series of high-frequency voltage pulses. For this application the compactness of the representation is more important than in the above storage example. They conclude, "A saving of 58 per cent can be gained in going from a binary to a ternary system. A smaller percentage gain is realized in going from a radix 3 to a radix 4 system."[5]

See also

References

  1. ^ a b Brian Hayes (2001). "Third Base". American Scientist 89 (6): 490. doi:10.1511/2001.40.3268. 
  2. ^ Engineering Research Associates pp.20-23: 3-6. The r-triode Counter, Modulo r
  3. ^ Engineering Research Associates pp.23-25: 3-7. The 2r-triode Counter, Modulo r
  4. ^ Engineering Research Associates pp.84-87: 6-7. Economy Attained by Radix Choice
  5. ^ Engineering Research Associates pp.419-521: 16-2. New Techniques

Further reading

External links