Mixed radix

From Wikipedia, the free encyclopedia

Numeral systems by culture
Hindu-Arabic numerals
Western Arabic Eastern Arabic Khmer	Indian family Brahmi Thai
East Asian numerals
Chinese Japanese	Korean
Alphabetic numerals
Abjad Armenian Cyrillic Ge'ez	Hebrew Ionian/Greek Sanskrit
Other systems
Attic Etruscan Roman	Babylonian Egyptian Mayan
List of numeral system topics
Positional systems by base
Decimal (10)
2, 4, 8, 16, 32, 64, 128
3, 9, 12, 24, 30, 36, 60, more…
v • d • e

Mixed radix numeral systems are non-standard positional numeral systems in which the numerical base varies from position to position. Such numerical representation is advantageous when representing units that are equivalent to each other, but not by the same ratio. For example, 32 weeks, 5 days, 7 hours, 45 minutes, 15 seconds, and 500 milliseconds might be rendered relative to minutes in mixed-radix notation as:

...  3,  2, 5,  7, 45; 15,  500
... 10, 10, 7, 24, 60; 60, 1000

or as

3₁₀2₁₀5₇7₂₄45₆₀.15₆₀500₁₀₀₀

In the tabular format, the digits are written above their base, and a semicolon is used to indicate the radix point. In numeral format, each digit has its associated base attached as a subscript, and the position of the radix point is indicated by a full stop.

1 Examples
2 Manipulation
3 Factorial based radix
4 References
5 External links

[edit] Examples

A mixed radix numeral system can often benefit from a tabular summary. The familiar system for describing the 604800 seconds of a week starting from midnight on Sunday runs as follows:

Radix:	7	2	12	60	60
Denomination:	day	half-day	hour	minute	second
Place value (seconds):	86400	43200	3600	60	1
Digit translations …
day:	0=Sunday, 1=Monday, 2=Tuesday, 3=Wednesday, 4=Thursday, 5=Friday, 6=Saturday
half-day:	0=AM, 1=PM
hour:	0 is written as "12" (!)

In this numeral system, the mixed radix numeral 3₇1₂5₁₂51₆₀57₆₀ seconds would be interpreted as 05:51:57 p.m. on Wednesday, and 0₇0₂0₁₂02₆₀24₆₀ would be 12:02 :24 a.m. on Sunday. Ad hoc notations for mixed radix numeral systems are commonplace.

A second example of a mixed radix numeral system in current use is in the design and use of currency, where a limited set of denominations are printed or minted with the objective of being able to represent any monetary quantity; the amount of money is then represented by the number of coins or banknotes of each denomination. When deciding which denominations to create (and hence which radices to mix), a compromise is aimed for between a minimal number of different denominations, and a minimal number of individual pieces of coinage required to represent typical quantities. So, for example, in the UK, banknotes are printed for £50, £20, £10 and £5, and coins are minted for £2, £1, 50p, 20p, 10p, 5p, 2p and 1p.

A historical example of a mixed radix numeral system is the system of Mayan numerals, which generally used base-20, except for the second place (the "10s" in decimal) which was base-18, so that the first two places counted up to 360 (an approximation to the number of days in the year).

Mixed-radix representation is also relevant to mixed-radix versions of the Cooley-Tukey FFT algorithm, in which the indices of the input values are expanded in a mixed-radix representation, the indices of the output values are expanded in a corresponding mixed-radix representation with the order of the bases and digits reversed, and each subtransform can be regarded as a Fourier transform in one digit for all values of the remaining digits.

[edit] Manipulation

Mixed-radix numbers of the same base can be manipulated using a generalization of manual arithmetic algorithms. Conversion of values from one mixed base to another is easily accomplished by first converting the place values of the one system into the other, and then applying the digits from the one system against these.

APL includes operators to convert to and from mixed-radix systems.

[edit] Factorial based radix

Main article: Factoradic

An interesting proposal is a factorial based radix, also known as factoradic:

radix:	6	5	4	3	2	1
place value:	5!	4!	3!	2!	1!	0!
decimal:	120	24	6	2	1	1

For example, the biggest number that could be represented with six digits would be 543210 which equals 719 in decimal: 5×5! + 4×4! + 3×3! + 2×2! + 1×1! + 0×0!. It might not be clear at first sight but factorial based numbering system is also unambiguous. No number can be represented by more than one way because the sum of respective factorials multiplied by the index is always the next factorial minus one:

$\sum_{i=0}^{n} i\cdot i! = {(n+1)!} - 1.$

This can be easily proved with mathematical induction.

There is a natural mapping between the integers 0, ..., n! − 1 and permutations of n elements in lexicographic order, when the integers are expressed in factoradic form.

[edit] References

Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 208–209 and 290.