Numeral system

Numeral systems by culture
Hindu-Arabic numerals
Western Arabic; Indian family; Khmer	Eastern Arabic; Brahmi; Thai
East Asian numerals
Chinese; Suzhou	Counting rods; Mongolian
Alphabetic numerals
Abjad; Armenian; Cyrillic; Ge'ez	Hebrew; Greek (Ionian); Āryabhaṭa;
Other systems
Attic; Babylonian; Egyptian; Inuit	Etruscan; Mayan; Roman; Urnfield
	List of numeral system topics
Positional systems by base
	Decimal (10)
	2, 4, 8, 16, 32, 64
	1, 3, 6, 9, 12, 20, 24, 30, 36, 60, more…
	v • d • e

From Wikipedia, the free encyclopedia

Jump to: navigation, search

This article is about different methods of expressing numbers with symbols. For completely different sets of numbers, see number system.

A numeral system (or system of numeration) is a writing system for expressing numerals, and a mathematical notation for representing numbers of a given set, using graphemes or symbols in a consistent manner. It can be seen as the context that allows the numeral "11" to be interpreted as the binary numeral for three, the decimal numeral for eleven, or other numbers in different bases.

Ideally, a numeral system will:

Represent a useful set of numbers (e.g. all whole numbers, integers, or real numbers)
Give every number represented a unique representation (or at least a standard representation)
Reflect the algebraic and arithmetic structure of the numbers.

For example, the usual decimal representation of whole numbers gives every whole number a unique representation as a finite sequence of digits, with the operations of arithmetic (addition, subtraction, multiplication and division) being present as the standard algorithms of arithmetic. However, when decimal representation is used for the rational or real numbers, the representation is no longer unique: many rational numbers have two numerals, a standard one that terminates, such as 2.31, and another that recurs, such as 2.309999999... . Numerals which terminate have no non-zero digits after a given position. For example, numerals like 2.31 and 2.310 are taken to be the same, except in the experimental sciences, where greater precision is denoted by the trailing zero.

Numeral systems are sometimes called number systems, but that name is misleading, as it could refer to different systems of numbers, such as the system of real numbers, the system of complex numbers, the system of p-adic numbers, etc. Such systems are not the topic of this article.

[edit] Types of numeral systems

The most commonly used system of numerals is known as Hindu-Arabic numerals, and two great Indian mathematicians could be given credit for developing them. Aryabhatta of Kusumapura who lived during the 5th century developed the place value notation and Brahmagupta a century later introduced the symbol zero.^[1]

The simplest numeral system is the unary numeral system, in which every natural number is represented by a corresponding number of symbols. If the symbol / is chosen, for example, then the number seven would be represented by ///////. Tally marks represent one such system still in common use. In practice, the unary system is normally only useful for small numbers, although it plays an important role in theoretical computer science. Also, Elias gamma coding which is commonly used in data compression expresses arbitrary-sized numbers by using unary to indicate the length of a binary numeral.

The unary notation can be abbreviated by introducing different symbols for certain new values. Very commonly, these values are powers of 10; so for instance, if / stands for one, - for ten and + for 100, then the number 304 can be compactly represented as +++ //// and number 123 as + - - /// without any need for zero. This is called sign-value notation. The ancient Egyptian system is of this type, and the Roman system is a modification of this idea.

More useful still are systems which employ special abbreviations for repetitions of symbols; for example, using the first nine letters of our alphabet for these abbreviations, with A standing for "one occurrence", B "two occurrences", and so on, we could then write C+ D/ for the number 304. The numeral system of English is of this type ("three hundred [and] four"), as are those of virtually all other spoken languages, regardless of what written systems they have adopted.

More elegant is a positional system, also known as place-value notation. Again working in base 10, we use ten different digits 0, ..., 9 and use the position of a digit to signify the power of ten that the digit is to be multiplied with, as in 304 = 3×100 + 0×10 + 4×1. Note that zero, which is not needed in the other systems, is of crucial importance here, in order to be able to "skip" a power. The Hindu-Arabic numeral system, borrowed from India, is a positional base 10 system; it is used today throughout the world.

Arithmetic is much easier in positional systems than in the earlier additive ones; furthermore, additive systems have a need for a potentially infinite number of different symbols for the different powers of 10; positional systems need only 10 different symbols (assuming that it uses base 10).

The numerals used when writing numbers with digits or symbols can be divided into two types that might be called the arithmetic numerals 0,1,2,3,4,5,6,7,8,9 and the geometric numerals 1,10,100,1000,10000... respectively. The sign-value systems use only the geometric numerals and the positional system use only the arithmetic numerals. The sign-value system does not need arithmetic numerals because they are made by repetition (except for the Ionic system), and the positional system does not need geometric numerals because they are made by position. However, the spoken language uses both arithmetic and geometric numerals.

In certain areas of computer science, a modified base-k positional system is used, called bijective numeration, with digits 1, 2, ..., k (k ≥ 1), and zero being represented by the empty string. This establishes a bijection between the set of all such digit-strings and the set of non-negative integers, avoiding the non-uniqueness caused by leading zeros. Bijective base-k numeration is also called k-adic notation, not to be confused with p-adic numbers. Bijective base-1 is the same as unary.

[edit] Bases used

[edit] Computing

Switches, mimicked by their electronic successors built originally of vacuum tubes and in modern technology of transistors, have only two possible states: "open" and "closed". Substituting open=1 and closed=0 (or the other way around) yields the entire set of binary digits. This base-2 system (binary) is the basis for digital computers. It is used to perform integer arithmetic in almost all digital computers; some exotic base-3 (ternary) and base-10 computers have also been built, but those designs were discarded early in the history of computing hardware.

Modern computers use transistors that represent two states with either high or low voltages. The smallest unit of memory for this binary state is called a bit. Bits are arranged in groups to aid in processing, and to make the binary numbers shorter and more manageable for humans. More recently these groups of bits, such as bytes and words, are sized in multiples of four. Thus base 16 (hexadecimal) is commonly used as shorthand. Base 8 (octal) has also been used for this purpose.

A computer does not treat all of its data as numerical. For instance, some of it may be treated as program instructions or data such as text. However, arithmetic and Boolean logic constitute most internal operations. Whole numbers are represented exactly, as integers. Real numbers, allowing fractional values, are usually approximated as floating point numbers. The computer uses different methods to do arithmetic with these two kinds of numbers.

[edit] Five

A base-5 system (quinary) has been used in many cultures for counting. Plainly it is based on the number of fingers on a human hand. It may also be regarded as a sub-base of other bases, such as base 10 and base 60.

[edit] Eight

A base-8 system (octal) was devised by the Yuki tribe of Northern California, who used the spaces between the fingers to count, corresponding to the digits one through eight. There is also linguistic evidence which suggests that the Bronze Age Proto-Indo Europeans (from whom most European and Indic languages descend) might have replaced a base 8 system (or a system which could only count up to 8) with a base 10 system. The evidence is that the word for 9, newm, is suggested by some to derive from the word for 'new', newo-, suggesting that the number 9 had been recently invented and called the 'new number'.^[2]

[edit] Ten

The Algorists versus the Abacists by Gregor Reisch: Margarita Philosophica, 1508

The base-10 system (decimal) is the one most commonly used today. It is assumed to have originated because humans have ten fingers. These systems often use a larger superimposed base. See Decimal superbase.

[edit] Twelve

Base-12 systems (duodecimal or dozenal) have been popular because multiplication and division are easier than in base-10, with addition and subtraction being just as easy. Twelve is a useful base because it has many factors. It is the smallest multiple of one, two, three, four and six. There is still a special word for "dozen" and just like there is a word for 10², hundred, there is also a word for 12², gross.

There are 24 hours per day, usually counted up to 12 until noon (p.m.) and once again until midnight (a.m.), often further divided per 6 hours in counting (for instance in Thailand) or as switches between using terms like 'night', 'morning', 'afternoon', and 'evening', whereas other languages use such terms with durations of 3 to 9 hours often according to switches at some of the 3-hour interval marks.

Multiples of 12 have been in common use as English units of resolution in the analog and digital printing world, where 1 point equals 1/72 of an inch and 12 points equal 1 pica, and printer resolutions like 360, 600, 720, 1200 or 1440 dpi (dots per inch) are common. These are combinations of base-12 and base-10 factors: (3×12)×10, (5×12)×10, (6×12)×10, (10×12)×10 and (12×12)×10.

[edit] Twenty

The Maya civilization and other civilizations of Pre-Columbian Mesoamerica used base-20 (vigesimal). Evidence of base-20 counting systems is also found in the languages of central and western Africa.

Remnants of a Gaulish base-20 system also exist in French, as seen today in the names of the numbers from 60 through 99. For example, sixty-five is soixante-cinq (literally, "sixty [and] five"), while seventy-five is soixante-quinze (literally, "sixty [and] fifteen"). Furthermore, for any number between 80 and 99, the "tens-column" number is expressed as a multiple of twenty (somewhat similar to the archaic English manner of speaking of "scores", probably originating from the same underlying Celtic system). For example, eighty-two is quatre-vingt-deux (literally, four twenty[s] [and] two), while ninety-two is quatre-vingt-douze (literally, four twenty[s] [and] twelve). In Old French, forty was expressed as two twenties and sixty was three twenties, so that fifty-three was expressed as two twenties [and] thirteen, and so on.

The Irish language also used base-20 in the past, twenty being fichid, forty dhá fhichid, sixty trí fhichid and eighty ceithre fhichid. A remnant of this system may be seen in the modern word for 40, daoichead.

Danish numerals display a similar base-20 structure.

[edit] Sixty

Base 60 (sexagesimal) was used by the Sumerians and their successors in Mesopotamia and survives today in our system of time (hence the division of an hour into 60 minutes and a minute into 60 seconds) and in our system of angular measure (a degree is divided into 60 minutes and a minute is divided into 60 seconds). Sixty also has a large number of factors, including the first six counting numbers. Base-60 systems are believed to have originated through the merging of base-10 and base-12 systems. The Chinese Calendar, for example, uses a base-60 Jia-Zi甲子 system to denote years, with each year within the 60-year cycle being named with two symbols, the first being base-10 (called Tian-Gan or heavenly stems) and the second symbol being base 12 (called Di-Zhi地支 or earthly branches). Both symbols are incremented in successive years until the first pattern recurs 60 years later. The second symbol of this system is also related to the 12-animal Chinese zodiac system. The Jia-zi system can also be applied to counting days, with a year containing roughly six 60-day cycles.

[edit] Dual base (five and twenty)

Many ancient counting systems use five as a primary base, almost surely coming from the number of fingers on a person's hand. Often these systems are supplemented with a secondary base, sometimes ten, sometimes twenty. In some African languages the word for five is the same as "hand" or "fist" (Dyola language of Guinea-Bissau, Banda language of Central Africa). Counting continues by adding 1, 2, 3, or 4 to combinations of 5, until the secondary base is reached. In the case of twenty, this word often means "man complete". This system is referred to as quinquavigesimal. It is found in many languages of the Sudan region.

[edit] Base names

Number	From Latin			From Greek	Mixed or Other
	Cardinals	Ordinals	Distributives
1	unary	primal	singulary	henadic	Primary
2	dual		binary	dyadic	Secondary
3		tertial	ternary, trinary	triadic	Tertiary
4		quartal	quaternary	tetradic
5		quintal	quinary	pentadic	quinternary
6		sextal	senary	hexadic	heximal, hexary
7		septimal	septenary	hebdomadic	septuary
8	octal	octaval, octavary	octonary	ogdoadic	octonal
9		nonary	novenary	enneadic	novary, noval
10		decimal	denary	decadic
11		undecimal	undenary	hendecadic	unodecimal
12		duodecimal	duodenary	duodecadic	dozenal
13		tridecimal, tredecimal			triodecimal
14		quattuordecimal, quadrodecimal			tetradecimal
15		quindecimal	quindenary		pentadecimal
16		sedecimal	sedenary		hexadecimal, sexadecimal
17		septendecimal			heptadecimal
18		octodecimal			decennoctal
19		nonadecimal			novodecimal, decennoval
20		vicesimal, vigesimal	vicenary	icosadic	bigesimal, bidecimal
30		tricesimal, trigesimal	tricenary	triacontadic
40		quadragesimal	quadragenary
50		quinquagesimal	quinquagenary		pentagesimal
60		sexagesimal	sexagenary	hexecontadic
70		septuagesimal	septuagenary
80		octogesimal	octogenary
90		nonagesimal	nonagenary
100		centesimal	centenary	hecatontadic
200		ducentesimal	ducenary		bicentesimal, bicentimal
300		trecentesimal	trecenary		tercentimal, tricentesimal
400		quadringentesimal	quadringenary		quadricentesimal, quattrocentimal
500		quingentesimal	quingenary		pentacentesimal, quincentimal
600		sescentesimal			hexacentesimal, hexacentimal
700		septingentesimal	septingenary		heptacentesimal, heptacentimal
800		octingentesimal	octingenary		octacentesimal, octacentimal
900		noningentesimal	nongenary
1000		millesimal	millenary	chiliadic
10000				myriadic	decamillesimal

   24 - quadrovigesimal / quadriovigesimal
   26 - hexavigesimal / sexavigesimal
   27 - heptovigesimal
   28 - octovigesimal
   29 - novovigesimal
   31 - unotrigesimal
        (...repeat naming pattern...)
   36 - hexatridecimal / sexatrigesimal
        (...repeat naming pattern...)
   41 - unoquadragesimal
        (...repeat naming pattern...)
   51 - unoquinquagesimal 
        (...repeat naming pattern...)
   64 - quadrosexagesimal
        (...repeat naming pattern...)
  110 - decacentimal
  111 - unodecacentimal
        (...repeat naming pattern...)
  210 - decabicentimal
  211 - unodecabicentimal
        (...repeat naming pattern...)
  800 - octocentimal / octocentesimal
 2000 - bimillesimal
        (...repeat naming pattern...)

[edit] Positional systems in detail

[edit] Change of radix

A simple algorithm for converting integers between positive-integer radices is repeated division by the target radix; the remainders give the "digits" starting at the least significant. E.g., 1020304 base 10 into base 7:

1020304 / 7 = 145757 r 5
 145757 / 7 =  20822 r 3
  20822 / 7 =   2974 r 4
   2974 / 7 =    424 r 6
    424 / 7 =     60 r 4
     60 / 7 =      8 r 4
      8 / 7 =      1 r 1
      1 / 7 =      0 r 1   => 11446435

E.g., 10110111 base 2 into base 5:

10110111 / 101 = 100100 r 11  (3)
  100100 / 101 =    111 r  1  (1)
     111 / 101 =      1 r 10  (2)
       1 / 101 =      0 r  1  (1)  => 1213

To convert a "decimal" fraction, do repeated multiplication, taking the protruding integer parts as the "digits". Unfortunately a terminating fraction in one base may not terminate in another. E.g., 0.1A4C base 16 into base 9:

0.1A4C × 9 = 0.ECAC
0.ECAC × 9 = 8.520C
0.520C × 9 = 2.E26C
0.E26C × 9 = 7.F5CC
0.F5CC × 9 = 8.A42C 
0.A42C × 9 = 5.C58C  => 0.082785...

[edit] Generalized variable-length integers

More general is using a notation (here written little-endian) like $a 0 a 1 a 2$ for $a 0 + a 1 b 1 + a 2 b 1 b 2$ , etc.

This is used in punycode, one aspect of which is the representation of a sequence of non-negative integers of arbitrary size in the form of a sequence without delimiters, of "digits" from a collection of 36: a-z and 0-9, representing 0-25 and 26-35 respectively. A digit lower than a threshold value marks that it is the most-significant digit, hence the end of the number. The threshold value depends on the position in the number. For example, if the threshold value for the first digit is b (i.e. 1) then a (i.e. 0) marks the end of the number (it has just one digit), so in numbers of more than one digit the range is only b-9 (1-35), therefore the weight b₁ is 35 instead of 36. Suppose the threshold values for the second and third digit are c (2), then the third digit has a weight 34 × 35 = 1190 and we have the following sequence:

a (0), ba (1), ca (2), .., 9a (35), bb (36), cb (37), .., 9b (70), bca (71), .., 99a (1260), bcb (1261), etc.

Note that unlike a regular base-35 numeral system, we have numbers like 9b where 9 and b each represent 35; yet the representation is unique because ac and aca are not allowed.

The flexibility in choosing threshold values allows optimization depending on the frequency of occurrence of numbers of various sizes.

The case with all threshold values equal to 1 corresponds to bijective numeration, where the zeros correspond to separators of numbers with digits which are nonzero.

[edit] Properties of numerical systems with integer bases

Numeral systems with base A, where A is a positive integer, possess the following properties:

If A is even and A/2 is odd, all integral powers greater than zero of the number (A/2)+1 will contain (A/2)+1 as their last digit

If both A and A/2 are even, then all integral powers greater than or equal to zero of the number (A/2)+1 will alternate between having (A/2)+1 and 1 as their last digit. (For odd powers it will be (A/2)+1, for even powers it will be 1)

Proof of the first property:

Define ${A \over 2} + 1 = x$ Then x is even, and all $x p$ for p greater than 0 must be even. The property is equivalent to

$\!\ x^p \equiv\ x\ (\mbox{mod}\ A)$

We first check the case for p=1

$\!\ x \equiv\ x\ (\mbox{mod}\ A)$

x is less than A, so the result is trivial. We then check for p=2:

$\!\ x^2 = xx$

$\!\ x^2 = x(x-1) + x$

Since $x-1 = ({A \over 2} + 1) - 1 = {A \over 2}$ , then for all even N:

$\!\ {NA \over 2} = N(x-1) \equiv\ 0\ (\mbox{mod}\ A)\ (1)$

Because x is even, then $x (x - 1)$ is congruent to zero modulo A. Therefore:

$\!\ x^2 \equiv\ x\ (\mbox{mod}\ A)$

Using induction, assuming that the property holds for p-1:

$\!\ x^p = {x^{p-1}}x = {x^{p-1}}(x-1) + x^{p-1}$

Since the case holds for p-1, then ${x^{p-1}} \equiv\ x\ (\mbox{mod}\ A)$ . Since

$\!\ {x^{p-1}}(x-1)$

is a case of Equation 1, then ${x^{p-1}}(x-1) \equiv\ 0\ (\mbox{mod}\ A)$ . This leaves, for all p greater than 0,

$\!\ x^p \equiv\ x\ (\mbox{mod}\ A)$

Q.E.D.

Proof of the second property:

Define ${A \over 2} + 1 = x$ Then x is odd, and all $x p$ for p greater than or equal to 0 must be odd. The property is equivalent to

$\!\ x^p \equiv\ 1\ (\mbox{mod}\ A);\ \mbox{if}\ p \equiv\ 0\ (\mbox{mod}\ 2)$

$\!\ x^p \equiv\ x\ (\mbox{mod}\ A);\ \mbox{if}\ p \equiv\ 1\ (\mbox{mod}\ 2)$

Since $x-1 = ({A \over 2} + 1) - 1 = {A \over 2}$ , then for all odd E:

$\!\ {EA \over 2} = E(x-1) \equiv\ {A \over 2}\ (\mbox{mod}\ A)\ (2)$

The case is first checked for p=0:

$\!\ x^0 = 1$

$\!\ 1 \equiv\ 1\ (\mbox{mod}\ A)$

This result is trivial

Next, for p=1:

$\!\ x^1 = x$

$\!\ x \equiv\ x\ (\mbox{mod}\ A)$

This result is also trivial

Next, for p=2:

$\!\ x^2 = xx = x(x-1) + x$

Because x is odd, then x(x-1) is a case of Equation 2,

$x(x-1) + x \equiv\ {{A \over 2} + x}\ (\mbox{mod}\ A)$

$\!\ {A \over 2} + x = {A \over 2} + {A \over 2} + 1 = A+1$

$\!\ A+1 \equiv\ 1\ (\mbox{mod}\ A), (\mbox{so}\ x(x-1) + x = x^2 \equiv\ 1\ (\mbox{mod}\ A)$

Next, for p=3:

$\!\ x^3 = {x^2}x = {x^2}(x-1) + x^2$

Because $x 2$ is odd, $x 2 (x - 1) + x 2$ is a case of Equation 2,

$\!\ {x^2}(x-1) + x^2 \equiv\ {{A \over 2} + x^2}\ (\mbox{mod}\ A)$

Since $x^2 \equiv\ 1\ (\mbox{mod}\ A)$ ,

$\!\ {x^2}(x-1) + x^2 \equiv\ {{A \over 2} + 1}\ (\mbox{mod}\ A)$

${{A \over 2} + 1} = x$ , so $x^3 \equiv\ x\ (\mbox{mod}\ A)$ .

Using induction, assuming that the property holds for p-1:

$\!\ x^p \equiv\ {x^{p-1}}(x-1) + x^{p-1}$

If p is odd:

$\!\ x^{p-1} \equiv\ 1\ (\mbox{mod}\ A)$

Since $x p - 1 (x - 1)$ is a case of Equation (2), ${x^{p-1}}(x-1) + x^{p-1} \equiv\ {{A \over 2} + 1}\ (\mbox{mod}\ A)$ , so

$x^p \equiv\ x\ (\mbox{mod}\ A)$

If p is even:

$\!\ x^{p-1} \equiv\ x\ (\mbox{mod}\ A)$

Since $x p - 1 (x - 1)$ is a case of Equation (2), ${x^{p-1}}(x-1) + x^{p-1} \equiv\ {{A \over 2} + x}\ (\mbox{mod}\ A)$ .

${A \over 2} + x = {A \over 2} + {A \over 2} + 1 = A+1$

$A+1 \equiv\ 1\ (\mbox{mod}\ A)$ , so

$x^p \equiv\ 1\ (\mbox{mod}\ A)$

Q.E.D.

[edit] See also

Babylonian numerals — a sexagesimal (base-60) system
Computer numbering formats
Golden ratio base
List of numeral system topics
N-ary
Number names
Quipu
Recurring decimal
Residue number system
Subtractive notation

[edit] References

^ Hindu Arabic Numerals by David Eugene Smith Google Books)
^ (Mallory & Adams 1997)

Georges Ifrah. The Universal History of Numbers : From Prehistory to the Invention of the Computer, Wiley, 1999. ISBN 0-471-37568-3.
D. Knuth. The Art of Computer Programming. Volume 2, 3rd Ed. Addison-Wesley. pp.194–213, "Positional Number Systems".
J.P. Mallory and D.Q. Adams, Encyclopedia of Indo-European Culture, Fitzroy Dearborn Publishers, London and Chicago, 1997.
Hans J. Nissen, P. Damerow, R. Englund, Archaic Bookkeeping, University of Chicago Press, 1993, ISBN 0-226-58659-6.
Denise Schmandt-Besserat, How Writing Came About, University of Texas Press, 1992, ISBN 0-292-77704-3.
Claudia Zaslavsky, Africa Counts: Number and Pattern in African Cultures, Lawrence Hill Books, 1999, ISBN 1-55652-350-5.

[edit] External links

Correspondences with numerals and letters (nine different alphabets)
Counting Systems of Papua New Guinea
History of Counting and Numeral Systems-PlainMath.Net
Number Sense & Numeration Lessons
Numerical Mechanisms and Children's Concept of Numbers
Online Converter for Decimal/Roman Numerals (JavaScript, GPL)
Online Converter for Different Numeral Systems (Base 2-36, JavaScript, GPL)
Online Java applet for converting from any base to another
Software for converting from one numeral system to another

[0] Hindu Arabic Numerals by David Eugene Smith Google Books)

[1] (Mallory & Adams 1997)

[1]

[2]

Position	3	2	1	0	-1	-2	...
Weight	$b 3$	$b 2$	$b 1$	$b 0$	$b - 1$	$b - 2$	...
Digit	$a 3$	$a 2$	$a 1$	$a 0$	$c 1$	$c 2$	...
Decimal example weight	1000	100	10	1	0.1	0.01	...
Decimal example digit	4	3	2	7	0	0	...