Radix economy


Radix economy

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

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:cite journal | title = Third Base | author = Brian Hayes | work = American Scientist | volume = 89 | issue = 6 | year = 2001 | pages = 490 | doi = 10.1511/2001.40.3268] :
:E(b,N) = b lfloor log_b (N) +1 floor , . :
For example, 100 in decimal has three digits, so its radix economy is 10x3 = 30; its binary respresentation has seven digits (11001002) so it has radix economy 2x7 = 14 in base 2; in base 3 its representation has five digits (102013) with a radix economy of 3x5 = 15; in base 36 (2S36) its radix economy is 36x2 = 72.

The radix economy of bases "b"1 and "b"2 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) } ight) over left( dfrac{b_2 ln (N) }{ ln (b_2)} ight) } = b_1 ln (b_2)} over {b_2 ln (b_1), .

Since the function

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

has a minimum value when "x" = "e", the base with the lowest average radix economy is theoretically base "e". The integral base with the lowest average radix economy is base 3 (because 3 is the nearest integer to "e") followed by binary and base 4.

For example, the average radix economy of the integers from 1 to 100 in various bases is:

:

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. [Engineering Research Associates pp.20-23: 3-6. The "r"-triode Counter, Modulo "r"] (Larger radices required 2"r" triodes arranged as "r" flip-flops, as in ENIAC's decimal counters.) [Engineering Research Associates pp.23-25: 3-7. The 2"r"-triode Counter, Modulo "r"]

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,

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.

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." [Engineering Research Associates pp.419-521: 16-2. New Techniques]

ee also

*Ternary computer

References

*cite book |author=Engineering Research Associates Staff |title=High-Speed Computing Devices |publisher=McGraw-Hill |year=1950 |url=http://www.archive.org/details/HighSpeedComputingDevices |accessdate=2008-08-27

Further reading

*S.L. Hurst, "Multiple-Valued Logic-Its Status and its Future", "IEEE trans. computers", Vol. C-33, No 12, pp. 1160–1179, DEC 1984.
*J. T. Butler, "Multiple-Valued Logic in VLSI Design, ” IEEE Computer Society Press Technology Series, 1991.
*C.M. Allen, D.D. Givone “The Allen-Givone Implementation Oriented Algebra", in "Computer Science and Multiple-Valued Logic: Theory and Applications", D.C. Rine, second edition, D.C. Rine, ed., The Elsevier North-Holland, New York, N.Y., 1984. pp. 268–288.
*G. Abraham, "Multiple-Valued Negative Resistance Integrated Circuits", in "Computer Science and Multiple-Valued Logic: Theory and Applications", D.C. Rine, second edition, D.C. Rine, ed., The Elsevier North-Holland, New York, N.Y., 1984. pp. 394–446.

External links

* [http://gtode.tripod.com/Optimum.htm The Optimum Radix In Multiple-Valued Logic Systems]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Non-integer representation — A non integer representation uses non integer numbers as the radix, or bases, of a positional numbering system. For a non integer radix β > 1, the value of is The numbers di are non negative integers less than β. This is also known as a β… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Base 30 — or trigesimal is a positional numeral system using 30 as the radix. Digits in this base can be represented using the Arabic numerals 0 9 and the Latin letters A T.From a mathematical viewpoint, 30 is a convenient choice for a base in that it is… …   Wikipedia

  • Octadecimal — or base 18 is a positional numeral system using 18 as the radix. Digits in this base can be represented using the Arabic numerals 0 9 and the Latin letters A H.Octadecimal is a rarely used base, though the ancient Mayan calendar is sometimes… …   Wikipedia

  • Base 36 — is a positional numeral system using 36 as the radix. The choice of 36 is convenient in that the digits can be represented using the Arabic numerals 0 9 and the Latin letters A Z. Base 36 is therefore the most compact case insensitive… …   Wikipedia

  • Hwa Chong Institution — Infobox School name = Hwa Chong Institution (zh c|c=华侨中学) imagesize = 100px caption = motto = Zi Qiang Bu Xi (自强不息) established = 1 January 2005 from the merger of The Chinese High School (est. 21 March 1919) Hwa Chong Junior College (est. 1974)… …   Wikipedia

  • Numerical digit — The ten digits of the Arabic numerals, in order of value. A digit is a symbol (a numeral symbol such as 3 or 7 ) used in combinations (such as 37 ) to represent numbers in positional numeral systems. The name digit comes from the fact that the 10 …   Wikipedia

  • List of non-marine molluscs of Montana — Location of Montana The non marine mollusks of the state of Montana are a part of the molluscan fauna of Montana (wildlife of Montana), a northwestern state in the USA. The non marine mollusks of Montana consist of land snails and slugs as well… …   Wikipedia

  • Robot — This article is about mechanical robots. For other uses of the term, see robot (disambiguation). For software agents, see Bot. ASIMO (2000) at the Expo 2005, a humanoid robot …   Wikipedia

  • CNBC — Coordinates: 40°53′55″N 73°56′21″W / 40.89861°N 73.93917°W / 40.89861; 73.93917 This article is about the business news chan …   Wikipedia