Mixed radix

Mixed radix
Numeral systems by culture
Hindu-Arabic numerals
Western Arabic (Hindu numerals)
Eastern Arabic
Indian family
Tamil
Burmese
Khmer
Lao
Mongolian
Thai
East Asian numerals
Chinese
Japanese
Suzhou
Korean
Vietnamese
Counting rods
Alphabetic numerals
Abjad
Armenian
Āryabhaṭa
Cyrillic
Ge'ez
Greek (Ionian)
Hebrew
Other systems
Aegean
Attic
Babylonian
Brahmi
Egyptian
Etruscan
Inuit
Kharosthi
Mayan
Quipu
Roman
Sumerian
Urnfield
List of numeral system topics
Positional systems by base
Decimal (10)
2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 20, 24, 30, 36, 60, 64
List of numeral systems
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 applies when a quantity is expressed using a sequence of units that are each a multiple of the next smaller one, but not by the same factor. Such units are common for instance in measuring time; a time of 32 weeks, 5 days, 7 hours, 45 minutes, 15 seconds, and 500 milliseconds might be expressed as a number of minutes in mixed-radix notation as:

... 32, 5,  7, 45; 15,  500
...  ∞, 7, 24, 60; 60, 1000

or as

32577244560.15605001000

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. The base for each digit is the number of corresponding units that make up the next larger unit. As a consequence there is no base (written as ∞) for the first (most significant) digit, since here the "next larger unit" does not exist (and note that one could not add a larger unit of "month" or "year" to the sequence of units, as they are not integer multiples of "week").

Contents

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 371251251605760 seconds would be interpreted as 05:51:57 p.m. on Wednesday, and 070201202602460 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—these follow the 1-2-5 series of preferred values. In theory, balanced ternary minimizes the number of pieces of coinage required to represent any quantity.

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.

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.

Factorial number system

Another proposal is the so-called factorial number system:

Radix 8 7 6 5 4 3 2 1
Place value 7! 6! 5! 4! 3! 2! 1! 0!
Place value in decimal 5040 720 120 24 6 2 1 0
Highest digit allowed 7 6 5 4 3 2 1 0

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! It might not be clear at first sight but the factorial based numbering system is unambiguous and complete. Every number can be represented in one and only one way because the sum of respective factorials multiplied by the index is always the next factorial minus one:

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

There is a natural mapping between the integers 0, ..., n! − 1 and permutations of n elements in lexicographic order, which uses the factorial representation of the integer, followed by an interpretation as a Lehmer code.

The above equation is a particular case of the following general rule for any radix (either standard or mixed) base representation which expresses the fact that any radix (either standard or mixed) base representation is unambiguous and complete. Every number can be represented in one and only one way because the sum of respective weights multiplied by the index is always the next weight minus one:

 \sum_{i=0}^{n} (m_{i+1} - 1) \cdot M_i  = M_{n+1} - 1 , where M_i = \prod_{j=1}^{i} m_j,  m_j > 1,  M_0 = 1 ,

which can be easily proved with mathematical induction.

Prime radix number system

Another interesting proposal is the number system with successive prime numbers as radix, whose place values are primorial numbers:

radix: 17 13 11 7 5 3 2
place value: (p6=13)# (p5=11)# (p4=7)# (p3=5)# (p2=3)# (p1=2)# (p0=1)#
decimal: 30030 2310 210 30 6 2 1
 \sum_{i=0}^{n} (p_{i+1} - 1) \cdot p_i\# = p_{n+1}\# - 1 where p_i\# = \prod_{j=1}^{i} p_j, and pj = jth prime, p0# = p0 = 1.

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • mixed — смешался; смешал; смешанный mixed investment company смешанная инвестиционная компания deposits of mixed character депозиты смешанного характера mixed school школа совместного обучения, смешанная школа mixed point radix смешанное основание… …   English-Russian travelling dictionary

  • Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… …   Wikipedia

  • Cooley-Tukey FFT algorithm — The Cooley Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 in terms of smaller… …   Wikipedia

  • Non-standard positional numeral systems — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Bit-reversal permutation — Product of Gray code permutation and bit reversal permutation (4 bit) (The result permutes a natural ordered into a sequence ordered Hadamard matrix.) In applied mathematics, a bit reversal permutation is a permutation of a sequence with… …   Wikipedia

  • Positional notation — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group …   Wikipedia

  • Babylonian numerals — were written in cuneiform, using a wedge tipped reed stylus to make a mark on a soft clay tablet which would be exposed in the sun to harden to create a permanent record in amman baccalaureate school.The Babylonians, who were famous for their… …   Wikipedia

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • Prime-factor FFT algorithm — The Prime factor algorithm (PFA), also called the Good Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re expresses the discrete Fourier transform (DFT) of a size N = N 1 N 2 as a two dimensional N 1 times; N 2 DFT …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”