2 History

See also History of natural numbers and the status of zero.

Tallies carved from wood and stone have been used since prehistoric times. Stone age cultures, including the American Indians, used tallies for gambling with horses, slaves, personal services and trade-goods.

The earliest known written tallies appear in the ruins of the Sumerian empire, using clay tablets impressed with a sharp stick and baked. The Sumerians had quite an exotic system based on counts to 60, used in astronomical and other calculations. This system was imported and used by every Mediterranean nation that used astronomy, including the Greeks, Romans and Egyptians. We still use it to count time (minutes per hour), and angle (degrees).

In China, armies and provisions were counted using modular tallies of prime numbers. Unique numbers of troops and measures of rice appear as unique combinations of these tallies. A great convenience of modular arithmetic is that it is easy to multiply, though quite difficult to add. This makes use of modular arithmetic for provisions especially attractive. Conventional tallies are quite difficult to multiply and divide. In modern times modular arithmetic is sometimes used in Digital signal processing.

The Roman empire used tallies written on wax, papyrus and stone, and roughly followed the Greek custom of assigning letters to various numbers. The Roman system remained in common use in Europe until positional notation came into common use in the 1500s.

The Maya of Central America used a base 20/base 18 system, possibly inherited from the Olmec, including advanced features such as positional notation and a zero. They used this to do advanced astronomical calculations, including highly accurate calculations of the length of the solar year and the orbit of Venus.

The Incan Empire ran a large command economy using quipu, tallies made by knotting colored fibers. Knowledge of the encodings of the knots and colors was suppressed by the Spanish conquistadors in the 16th century, and has not survived although simple quipu-like recording devices are still used in the Andean region.

Some authorities believe that positional arithmetic began with the wide use of the abacus in China. The earliest written positional records seem to be tallies of abacus results in China around 400. In particular, zero was correctly described by Chinese mathematicians around 932, and seems to have originated as a circle of a place empty of beads.

From China, both the abacus and written tallies may have moved to India, perhaps via Chinese traders and businesses. In India, recognizably modern positional numeral systems, passed to the Arabians, probably along with the astronomical tables, was brought to Baghdad by an Indian ambassador around 773 A.D.. For greater discussion of numeral systems from India, see Arabic numerals and Indian numerals.

From India, the thriving trade between Islamic Moguls and Africa carried the concept to Cairo. Arabic mathematicians extended the system to decimal fractions, and al-Khwarizmi wrote an important work about it in the 9th century. The system was introduced to Europe with the translation of this work in the 12th century in Spain and Leonardo of Pisas Liber Abaci of 1201. In Europe, the complete Indian system with the zero was derived from the Arabs in the 12th century.

The binary system (base 2), propagated in the 17th century by Gottfried Leibniz who had heard about it from China, came in common use in the 20th century because of computer applications.

3 Bases used

The base-10 system is one most commonly used by humans today. It is assumed to have originated because humans have ten fingers. A base-eight system was devised by (at least) the Yuki Pomo of Northern California, who used the spaces between the fingers to count. The Maya civilization and other civilizations of Pre-Columbian Mesoamerica used base 20, (possibly originating from the number of a person's fingers and toes). Base 60 was used by the Sumerians and survives today in our system of time, hence the division of an hour into 60 minutes and a minute into 60 seconds. 60 is a useful base because it has large number of factors, allowing it to be divided without creating fractions. Base-12 systems were popular because multiplication is easier in them than in base-10, (addition just as easy) and because the year has twelve months; we still have a special word for "dozen" and use 12 hours for every night and day.

Switches (and their electronic successors, build of vacuum tubes, or later of transistors) have only 2 possible states: "open" and "closed". Substituting open=1 and closed=0 (or the other way around), one yields exactly the set of binary digits. Because arithmetics in a binary system are the easiest to describe electronically (using Boolean algebra), the binary system became natural for electronic computers. It is used to perform integer arithmetic in almost all electronic computers (the only exception being the exotic base-3 and base-10 designs that were discarded very early in the history of computing hardware). Note however that a computer does not treat all of its data as integers. Thus, some of it may be treated as texts and program data. Real numbers (numbers that can be not whole) are usually stored as approximations in floating point notation, that has different rules of arithmetic.

4 Positional systems in detail

Also see Positional notation.

In a positional base-b numeral system (with b a positive natural number known as the radix), b basic symbols (or digits) corresponding to the first b natural numbers including zero are used. To generate the rest of the numerals, the position of the symbol in the figure is used. The symbol in the last position has its own value, and as it moves to the left its value is multiplied by b.

For example, in the decimal system (base 10), the numeral 4327 means (4×10³) + (3×10²) + (2×10¹) + (7×10⁰), noting that 10⁰ = 1.

In general, if b is the base, we write a number in the numeral system of base b by expressing it in the form a₁b^k + a₂b^k-1 + a₃b^k-2 + ... + a_k+1b⁰ and writing the digits a₁a₂a₃ ... a_k+1 in order. The digits are natural numbers between 0 and b-1, inclusive.

If a text (such as this one) discusses multiple bases, and if ambiguity exists, the base is added in subscript to the right of the number, like this: number_base. Unless specified by context, numbers without subscript are considered to be decimal.

By using a dot to divide the digits into two groups, one can also write fractions in the positional system. For example, the base-2 numeral 10.11 denotes 1×2¹+ 0×2⁰ +1×2^-1 +1×2^-2 = 2.75.

In general, numbers in the base b system are of the form:

Note that a number has a terminating or repeating expansion if and only if it is rational; this does not depend on the base. A number that terminates in one base may repeat in another (thus 0.3₁₀ = 0.0100110011001...₂). An irrational number stays unperiodic (infinite amount of unrepeating digits) in all integral bases. Thus, for example in base 2, π = 3.1415926...₁₀ can be written down as the unperiodic 11.001001000011111...₂.

If b=p is a prime number, one can define base-p numerals whose expansion to the left never stops; these are called the p-adic numbers.

5 Specific numeral systems

5.1 Positional systems

• b=2: Binary
• b=3: Ternary (or trinary)
• b=4: Quaternary
• b=5: Quinary
• b=6: Senary
• b=7: Septimal
• b=8: Octal or Octonary
• b=9: Novenary
• b=10: Decimal or Denary (a single system, but there are both long scale and short scale naming variants in widespread use)
• b=12: Duodecimal (used in the Chepang language of Nepal)
• b=13: Tredecimal
• b=16: Hexadecimal (properly sedecimal, but hexadecimal is standard)
• b=20: Vigesimal (see Maya numerals)
• b=25: Quinquevigesimal (see D'ni numerals)
• b=27: Septemvigesimal
• b=60: Sexagesimal (see Babylonian numerals)
• b=64: Quattuorsexagesimal
• b=120: Centivigesimal

5.2 Positional-like systems with non-standard bases

• b=−3: Negaternary
• b=−2: Negabinary
• b= φ: Golden mean base
• b= e: Natural base
• b=2i: Quater-imaginary base
• b=: Binary square-root-2 times i base
• b=i − 1: Binary i−1 base
• b= Fibonacci number: Fibonacci coding
• b= ω: Cantor Normal Form for ordinal numbers
• b varies: Mixed radix

5.3 Other

• b=1 Unary numeral system
• b=10 Decimal without a zero
• Binary-coded decimal

5.4 Other systems

• Unary numeral system
• Roman numerals
• Church integers

6 Change of radix

The easiest way of 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 X into base VII:

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 => 11446435

E.g., 10110111 base II into base V:

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

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

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...

7 See also

• computer numbering formats
• billion
• subtractive notation

8 External resources

D. Knuth. The Art of Computer Programming. Volume 2, 3rd Ed. Addison-Wesley. pp.194-213, "Positional Number Systems"

<Hide>