Positional notation

Numeral systems by culture
Hindu-Arabic numerals
Western Arabic; Eastern Arabic; Indian family	Khmer; Mongolian; Thai
East Asian numerals
Chinese; Counting rods; Japanese	Korean; Suzhou
Alphabetic numerals
Abjad; Armenian; Āryabhaṭa; Cyrillic	Ge'ez; Greek (Ionian); Hebrew
Other systems
Attic; Babylonian; Brahmi; Egyptian; Etruscan	Inuit; 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

(Redirected from Place value)

Jump to: navigation, search

A positional notation or place-value notation system is a numeral system in which each digit is related to the next by a constant multiplier, (a common ratio) called the base or radix of that numeral system. The value of each digit position is the value of its digit multiplied by a power of the base; the power is determined by the digit's position. The total value of a positional number is the total of the values of all positions.

Various bases are commonly used. For example, the decimal system uses ten unique symbols, whereas the sexagesimal system usually uses a decimal-like system for each position and separates each position from the next by punctuation. Modern computers use binary, octal, and hexadecimal numbers, the last using decimal numerals (0–9) plus the letters A–F to provide the sixteen possible symbols in each position.

Generalising the positional system to infinite sequences of digits yields an intuitive description of the real line.

In the west, positional notation became standard after the 16th century.

[edit] History

Today the decimal system is the base used in everyday life. It was likely motivated by counting with the ten fingers. However, other civilizations and contexts used different bases. The Babylonian civilization used a base 60 system. There were not, however, 60 different symbols, as one would expect — each "digit" was represented by a modified decimal system, for example, "12 35 1" = 12×60² + 35×60 + 1. The Babylonians had their own number symbols.

Most abacuses in history represented numbers in a positional numeral system. Before positional notation became standard, simple additive systems (sign-value notation) were used such as Roman Numerals, and accountants in ancient Rome and during the Middle Ages used the abacus or stone counters to do arithmetic.^[1]

With an abacus to perform arithmetic operations, the writing of the starting, intermediate and final values of a calculation could easily be done with a simple additive system in each position or column. This approach required no memorization of tables (as does positional notation) and could produce practical results quickly. For four centuries (13th–16th) there was strong disagreement between those who believed in adopting the positional system in writing numbers and those who wanted to stay with the additive-system-plus-abacus. Although electronic calculators have largely replaced the abacus, the latter continues to be used in Japan and other Asian countries.

Georges Ifrah concludes in his Universal History of Numbers:

Thus it would seem highly probable under the circumstances that the discovery of zero and the place-value system were inventions unique to the Indian civilization. As the Brahmi notation of the first nine whole numbers (incontestably the graphical origin of our present-day numerals and of all the decimal numeral systems in use in India, Southeast and Central Asia and the Near East) was autochthonous and free of any outside influence, there can be no doubt that our decimal place-value system was born in India and was the product of Indian civilization alone.

—^[2]

Aryabhatta stated "Stanam Stanam Dasa Gunam" meaning "Place to place ten times in value". His system lacked zero. The zero was added by Brahmagupta. Brahmagupta also was responsible for developing four fundamental operations (addition, subtraction, multiplication and division). Indian mathematicians and astronomers also developed Sanskrit positional number words to describe astronomical facts or algorithms using poetic sutras.

A key argument against the positional system was its susceptibility to easy fraud by simply putting a number at the beginning or end of a quantity, thereby changing (e.g.) 100 into 5100, or 100 into 1000. Modern bank cheques require a natural language spelling of an amount, as well as the amount itself, to prevent such fraud.

[edit] Mathematics

[edit] Base of the numeral system

In mathematical numeral systems, the base or radix is usually the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is 10, because it uses the 10 digits from 0 through 9.

The highest symbol of a positional numeral system usually has the value one less than the value of the base of that numeral system. The standard positional numeral systems differ from one another only in the base they use.

The base is an integer that is greater than 1 (or less than negative 1), since a radix of zero would not have any digits, and a radix of 1 would only have the zero digit. Negative bases are rarely used. In a system with a negative radix, numbers may have many different possible representations.

(In certain non-standard positional numeral systems, including bijective numeration, the definition of the base or the allowed digits deviates from the above.)

[edit] Digits and numerals

In order to discuss bases other than the decimal system (base ten), a distinction needs to be made between a number and the digit representing that number. Each digit may be represented by a unique symbol or by a limited set of symbols.

For example, in the decimal positional numeral system, there are ten possible digits in each position. These are "0", "1", "2", "3", "4", "5", "6", "7", "8" , and "9" (henceforth "0-9"). In other bases, the digits used may be unfamiliar or may be used to indicate numbers other than those they represent in the decimal system. For example, in the base 32 numeral system, there are 32 possible digits for each position. These combinations are the numbers 0-31, but they could be signified (in ascending order) first by the symbols A-Z and then by the symbols 2-7. So A would represent 0, Z the number 25, 2 the number 26, 3 represents 27, etc. Because of the widespread use of the decimal system, it is common that numbers are written in base ten, and unless otherwise indicated, most numbers encountered are normally assumed to be decimal numbers. However, any real number can be represented with any base.

E.g., for octal only eight digits up to 7 and for binary only two digits 0 and 1 are needed. For bases above 10, extra digits are needed. For hexadecimal the first six letters of the alphabet A, B, C, D, E, and F are commonly used for decimal values 10 to 15. The alphabet can cover numeral systems with a base up to 10 + 26 = 36. However, some uppercase letters can be confused with 'existing' digits such as an I with a 1 and O with 0. When these are omitted it can reach 34. Adding lowercase letters (none of them can be confused with 'existing' digits, except l in some fonts) extends the digit set to 62 (or 60 when uppercase I and O are omitted). For a base 60 system a 'mixed' base with 10 as 'secondary' base is commonly used, please see below.

[edit] Notation

Sometimes, a subscript notation is used where the base number is written in subscript after the number represented. For example, $23_8 \$ indicates that the number 23 is expressed in base 8 (and is therefore equivalent in value to the decimal number 19). This notation will be used in this article.

When describing base in mathematical notation, the letter b is generally used as a symbol for this concept, so, for a binary system, b equals 2. Another common way of expressing the base is writing it as a decimal subscript after the number that is being represented. 1111011₂ implies that the number 1111011 is a base 2 number, equal to 123₁₀ (a decimal notation representation), 173₈ (octal) and 7B₁₆ (hexadecimal). When using the written abbreviations of number bases, the base is not printed: Binary 1111011 is the same as 1111011₂.

The base b may also be indicated by the phrase "base b". So binary numbers are "base 2"; octal numbers are "base 8"; decimal numbers are "base 10"; and so on.

Numbers of a given radix b have digits {0, 1, ..., b-2, b-1}. Thus, binary numbers have digits {0, 1}; decimal numbers have digits {0, 1, 2, ..., 8, 9}; and so on. Thus the following are notational errors and do not make sense: 52₂, 2₂, 1A₉. (In all cases, one or more digits is not in the set of allowed digits for the given base.)

[edit] Exponentiation

Positional number systems work using exponentiation of the base. A digit's value is the digit multiplied by the value of its place. Place values are the number of the base raised to the nth power, where n is the number of other digits between the current digit and the decimal point. If the current digit is on the left hand side of the decimal point (i.e., it is greater than or equal to 1) then n is positive; if the digit is on the right hand side of the decimal point (i.e., it is fractional) then n is negative.

As an example of usage, the number 465 in its respective base 'b' (which must be at least base 7 because the highest digit in it is 6) is equal to:

$4\times b^2 + 6\times b^1 + 5\times b^0$

If the number 465 was in base 10, then it would equal:

$4\times 10^2 + 6\times 10^1 + 5\times 10^0 = 4\times 100 + 6\times 10 + 5\times 1 = 465$

(465₁₀ = 465₁₀)

If however, the number were in base 7, then it would equal:

$4\times 7^2 + 6\times 7^1 + 5\times 7^0 = 4\times 49 + 6\times 7 + 5\times 1 = 243$

(465₇ = 243₁₀)

10_b = b for any base b, since 10_b = 1×b¹ + 0×b⁰. For example 10₂ = 2; 10₃ = 3; 10₁₆ = 16₁₀. Note that the last "16" is indicated to be in base 10. The base makes no difference for one-digit numerals.

Numbers that are not integers use places beyond a decimal point. For every position behind this point (and thus after the units digit), the power n decreases by 1. For example, the number 2.35 is equal to:

$2\times 10^0 + 3\times 10^{-1} + 5\times 10^{-2}$

This concept can be demonstrated using a diagram. One object represents one unit. When the number of objects is equal to or greater than the base b, then a group of objects is created with b objects. When the number of these groups exceeds b, then a group of these groups of objects is created with b groups of b objects; and so on. Thus the same number in different bases will have different values:

241 in base 5:
   2 groups of 5² (25)           4 groups of 5          1 group of 1
   ooooo    ooooo
   ooooo    ooooo                ooooo   ooooo
   ooooo    ooooo         +                         +         o
   ooooo    ooooo                ooooo   ooooo
   ooooo    ooooo

241 in base 8:
   2 groups of 8² (64)          4 groups of 8          1 group of 1
 oooooooo  oooooooo
 oooooooo  oooooooo
 oooooooo  oooooooo         oooooooo   oooooooo
 oooooooo  oooooooo    +                            +        o
 oooooooo  oooooooo
 oooooooo  oooooooo         oooooooo   oooooooo
 oooooooo  oooooooo
 oooooooo  oooooooo

The notation can be further augmented by allowing a leading minus sign. This allows the representation of negative numbers. For a given base, every representation corresponds to exactly one real number and every real number has at least one representation. The representations of rational numbers are those representations that are finite, use the bar notation, or end with an infinitely repeating cycle of digits.

[edit] Base conversion

Bases can be converted between each other by drawing the diagram above and rearranging the objects to conform the new base, for example:

241 in base 5:
   2 groups of 5²           4 groups of 5          1 group of 1
   ooooo    ooooo
   ooooo    ooooo           ooooo   ooooo
   ooooo    ooooo     +                        +         o
   ooooo    ooooo           ooooo   ooooo
   ooooo    ooooo

is equal to 107 in base 8:
    1 group of 8²           0 groups of 8          7 groups of 1
      oooooooo  
      oooooooo                                        o     o
      oooooooo
      oooooooo        +                        +    o    o    o
      oooooooo  
      oooooooo                                        o     o
      oooooooo  
      oooooooo

There is, however, a shorter method which is basically the above method calculated mathematically. Because we work in base ten normally, it is easier to think of numbers in this way and therefore easier to convert them to base ten first, though it is possible (but difficult) to convert straight between non-decimal bases without using this intermediate step.

A number a_na_n-1...a₂a₁a₀ where a₀, a₁... a_n are all digits in a base b (note that here, the subscript does not refer to the base number; it refers to different objects), the number can be represented in any other base, including decimal, by:

$\sum_{i=0}^n \left( a_i\times b^i \right)$

Thus, in the example above:

$241_5 = 2\times 5^2 + 4\times 5^1 + 1\times 5^0 = 50 + 20 + 1 = 71_{10}$

To convert from decimal to another base one must simply start dividing by the value of the other base, then dividing the result of the first division and overlooking the remainder, and so on until the base is larger than the result (so the result of the division would be a zero). Then the number in the desired base is the remainders being the most significant value the one corresponding to the last division and the least significant value is the remainder of the first division.

The most common example is that of changing from Decimal to Binary.

[edit] Infinite representations

The representation of non-integers can be extended to allow an infinite string of digits beyond the point. For example 1.12112111211112 ... base 3 represents the sum of the infinite series:

$1\times 3^{0\,\,\,} + {}$

$1\times 3^{-1\,\,} + 2\times 3^{-2\,\,\,} + {}$

$1\times 3^{-3\,\,} + 1\times 3^{-4\,\,\,} + 2\times 3^{-5\,\,\,} + {}$

$1\times 3^{-6\,\,} + 1\times 3^{-7\,\,\,} + 1\times 3^{-8\,\,\,} + 2\times 3^{-9\,\,\,} + {}$

$1\times 3^{-10} + 1\times 3^{-11} + 1\times 3^{-12} + 1\times 3^{-13} + 2\times 3^{-14} + \cdots$

Since a complete infinite string of digits cannot be explicitly written, the trailing ellipsis (...) designates the omitted digits, which may or may not follow a pattern of some kind. One common pattern is when a finite sequence of digits repeats infinitely. This is designated by drawing a bar across the repeating block:

$2.42\overline{314}_5 = 2.42314314314314314\dots_5$

For base 10 it is called a recurring decimal or repeating decimal.

An irrational number has an infinite non-repeating representation in all integer bases. Whether a rational number has a finite representation or requires an infinite repeating representation depends on the base. For example, one third can be represented by:

$0.1_3\,$

$0.\overline3_{10} = 0.3333333\dots_{10}$

$0.\overline{01}_2 = 0.010101\dots_2$

$0.2_6\,$

For integers p and q with gcd(p, q) = 1, the fraction p/q has a finite representation in base b if and only if each prime factor of q is also a prime factor of b.

For a given base, any number that can be represented by a finite number of digits (without using the bar notation) will have multiple representations, including one or two infinite representations:

1. A finite or infinite number of zeroes can be appended:

$3.46_7 = 3.460_7 = 3.460000_7 = 3.46\overline0_7$

2. The last non-zero digit can be reduced by one and an infinite string of digits, each corresponding to one less than the base, are appended (or replace any following zero digits):

$3.46_7 = 3.45\overline6_7$

$1_{10} = 0.\overline9_{10}$

$220_5 = 214.\overline4_5$

[edit] Applications

[edit] Decimal system

Main article: Decimal representation

Evolutions of Hindu-Arabic numerals

In the decimal (base-10) Hindu-Arabic numeral system, each position starting from the right is a higher power of 10. The first position represents 10⁰ (1), the second position 10¹ (10), the third position 10² (10 × 10 or 100), the fourth position 10³ (10 × 10 × 10 or 1000), and so on.

Fractional values are indicated by a separator, which varies by locale. Usually this separator is a period or full stop, or a comma. Digits to the right of it are multiplied by 10 raised to a negative power or exponent. The first position to the right of the separator indicates 10^-1 (0.1), the second position 10^-2 (0.01), and so on for each successive position.

As an example, the number 2674 in a base 10 numeral system is :

( 2 × 10³ ) + ( 6 × 10² ) + ( 7 × 10¹ ) + ( 4 × 10⁰ )

or

( 2 × 1000 ) + ( 6 × 100 ) + ( 7 × 10 ) + ( 4 × 1 ).

[edit] Sexagesimal system

The sexagesimal or base sixty system was used for the integral and fractional portions of Babylonian numerals and other mesopotamian systems, by Hellenistic astronomers using Greek numerals for the fractional portion only, and is still used for modern time and angles, but only for minutes and seconds. However, not all of these uses were positional.

Modern time separates each position by a colon or point. For example, the time might be 10:25:59 (10 hours 25 minutes 59 seconds). Angles use similar notation. For example, an angle might be 10°25'59" (10 degrees 25 minutes 59 seconds). In both cases, only minutes and seconds use sexagesimal notation — angular degrees can be larger than 59 (one rotation around a circle is 360°, two rotations are 720°, etc.), and both time and angles use decimal fractions of a second. This contrasts with the numbers used by Hellenistic and Renaissance astronomers, who used thirds, fourths, etc. for finer increments. Where we might write 10°25'59.392", they would have written 10°25′59″23‴31''''12''''' or 10°25^I59^II23^III31^IV12^V.

Using a digit set of digits with upper and lowercase letters allows short notation for sexagesimal numbers, e.g. 10:25:59 becomes 'ARz' (by omitting I and O, but not i and o), which is useful for use in URLs, etc., but it is not very intelligible to humans.

In the 1930s, Otto Neugebauer introduced a modern notational system for Babylonian and Hellenistic numbers that substitutes modern decimal notation from 0 to 59 in each position, while using a semicolon (;) to separate the integral and fractional portions of the number and using a comma (,) to separate the positions within each portion. For example, the mean synodic month used by both Babylonian and Hellenistic astronomers and still used in the Hebrew calendar is 29;31,50,8,20 days, and the angle used in the example above would be written 10;25,59,23,31,12 degrees.

[edit] Quadrosexagesimal

In the most common implementations of the quadrosexagesimal system, the 64 digits are "A-Z", followed by "a-z", followed by "0-9", followed by "+" and "/". A is zero, Z is 25, a is 26, z is 51, 0 is 52, 9 is 61, + is 62 and / is 63; for a total of 64 combinations, including 0.

(In the case of the "Base64" system, things are even more complicated, because it isn't just a base 64 numeral system, but a specific encoding whereby the base 64 numerical string is translated to an 8 bit character code (and vice versa).)

[edit] Computing

In computing, the binary (base 2) and hexadecimal (base 16) bases are used. Computers, at the very simplest level, deal only with sequences of conventional 1s and 0s, thus it is easier in this sense to deal with powers of two. The hexadecimal system came about as shorthand for binary - every 4 binary digits relates to one and only one hexadecimal digit. In hexadecimal, the six digits after 9 are denoted by A, B, C, D, E and F (sometimes a, b, c, d, e, f).

The octal numbering system is also used as another way to represent binary numbers. In this case the base is 8 and therefore only digits 0, 1, 2, 3, 4, 5, 6 and 7 are used. When converting from binary to octal every 3 binary digits relate to one and only one octal digit.

[edit] Other bases in human language

A number of Australian Aboriginal languages employ binary or binary-like counting systems. For example, in Kala Lagaw Ya, the numbers one through six are urapon, ukasar, ukasar-urapon, ukasar-ukasar, ukasar-ukasar-urapon, ukasar-ukasar-ukasar.

Various traditional systems of measurement use duodecimal reckoning (base twelve), which in English is represented by terms such as dozen (12) and gross (144 = 12 x 12), and measurements such as foot (12 inches).

Certain European languages including Basque, French and Danish incorporate elements of a vigesimal (base-twenty) counting system. The Maya and Aztecs in Mesoamerica used vigesimal, as do the Ainu in East Asia.

[edit] Non-positional positions

Each position does not need to be positional itself. Babylonian sexagesimal numerals were positional, but in each position were groups of two kinds of wedges representing ones and tens (a narrow vertical wedge ( | ) and an open left pointing wedge (<)) — up to 14 symbols per position (5 tens (<<<<<) and 9 ones ( ||||||||| ) grouped into one or two near squares containing up to three tiers of symbols, or a place holder (\\) for the lack of a position).^[3] Hellenistic astronomers used one or two alphabetic Greek numerals for each position (one chosen from 5 letters representing 10–50 and/or one chosen from 9 letters representing 1–9, or a zero symbol).^[4]

[edit] See also

[edit] External links

Online Converter for Different Numeral Systems (Base 2-36, JavaScript, GPL)
Implementation of Base Conversion at cut-the-knot

[edit] References

^ Ifrah, page 187
^ Ifrah, G. The Universal History of Numbers: From prehistory to the invention of the computer. John Wiley and Sons Inc., 2000. Translated from the French by David Bellos, E.F. Harding, Sophie Wood and Ian Monk.
^ Ifrah, pages 326, 379
^ Ifrah, pages 261-264

Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.1: Positional Number Systems, pp.195–213.
Georges Ifrah. The Universal History of Numbers: From Prehistory to the Invention of the Computer, Wiley, 2000. ISBN 0-471-37568-3.
John Kadvany. Positional Value and Linguistic Recursion. Journal of Indian Philosophy, December 2007.
O'Connor, J. J. and Robertson, E. F. Babylonian numerals. Retrieved 26 April 2005.

[0] Ifrah, page 187

[1] Ifrah, G. The Universal History of Numbers: From prehistory to the invention of the computer. John Wiley and Sons Inc., 2000. Translated from the French by David Bellos, E.F. Harding, Sophie Wood and Ian Monk.

[2] Ifrah, pages 326, 379

[3] Ifrah, pages 261-264

[1]

[2]

[3]

[4]