Positional notation
Part of a series on |
Numeral systems |
---|
List of numeral systems |
Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or decimal system). More generally, a positional system is a numeral system in which the contribution of a digit to the value of a number is the value of the digit multiplied by a factor determined by the position of the digit. In early numeral systems, such as Roman numerals, a digit has only one value: I means one, X means ten and C a hundred (however, the value may be negated if placed before another digit). In modern positional systems, such as the decimal system, the position of the digit means that its value must be multiplied by some value: in 555, the three identical symbols represent five hundreds, five tens, and five units, respectively, due to their different positions in the digit string.
The
Systems with negative base, complex base or negative digits have been described. Most of them do not require a minus sign for designating negative numbers.
The use of a
History
Today, the base-10 (
The polymath Archimedes (ca. 287–212 BC) invented a decimal positional system in his Sand Reckoner which was based on 108[2] and later led the German mathematician Carl Friedrich Gauss to lament what heights science would have already reached in his days if Archimedes had fully realized the potential of his ingenious discovery.[3] Hellenistic and Roman astronomers used a base-60 system based on the Babylonian model (see Greek numerals § Zero).
Before positional notation became standard, simple additive systems (sign-value notation) such as Roman numerals were used, and accountants in ancient Rome and during the Middle Ages used the abacus or stone counters to do arithmetic.[4]
Counting rods and most abacuses have been used to represent numbers in a positional numeral system. With counting rods or 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.
The oldest extant positional notation system is either that of Chinese
After the French Revolution (1789–1799), the new French government promoted the extension of the decimal system.[5] Some of those pro-decimal efforts—such as decimal time and the decimal calendar—were unsuccessful. Other French pro-decimal efforts—currency decimalisation and the metrication of weights and measures—spread widely out of France to almost the whole world.
History of positional fractions
J. Lennart Berggren notes that positional decimal fractions were used for the first time by Arab mathematician
The adoption of the
- European mathematicians, when taking over from the Hindus, via the Arabs, the idea of positional value for integers, neglected to extend this idea to fractions. For some centuries they confined themselves to using common and sexagesimal fractions... This half-heartedness has never been completely overcome, and sexagesimal fractions still form the basis of our trigonometry, astronomy and measurement of time. ¶ ... Mathematicians sought to avoid fractions by taking the radius R equal to a number of units of length of the form 10n and then assuming for n so great an integral value that all occurring quantities could be expressed with sufficient accuracy by integers. ¶ The first to apply this method was the German astronomer Regiomontanus. To the extent that he expressed goniometrical line-segments in a unit R/10n, Regiomontanus may be called an anticipator of the doctrine of decimal positional fractions.[11]: 17, 18
In the estimation of Dijksterhuis, "after the publication of De Thiende only a small advance was required to establish the complete system of decimal positional fractions, and this step was taken promptly by a number of writers ... next to Stevin the most important figure in this development was Regiomontanus." Dijksterhuis noted that [Stevin] "gives full credit to Regiomontanus for his prior contribution, saying that the trigonometric tables of the German astronomer actually contain the whole theory of 'numbers of the tenth progress'."[11]: 19
Mathematics
Base of the numeral system
In mathematical numeral systems the radix r is usually the number of unique digits, including zero, that a positional numeral system uses to represent numbers. In some cases, such as with a negative base, the radix is the absolute value of the base b. For example, for the decimal system the radix (and base) is ten, because it uses the ten digits from 0 through 9. When a number "hits" 9, the next number will not be another different symbol, but a "1" followed by a "0". In binary, the radix is two, since after it hits "1", instead of "2" or another written symbol, it jumps straight to "10", followed by "11" and "100".
The highest symbol of a positional numeral system usually has the value one less than the value of the radix of that numeral system. The standard positional numeral systems differ from one another only in the base they use.
The radix is an integer that is greater than 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 more than unique digits, numbers may have many different possible representations.
It is important that the radix is finite, from which follows that the number of digits is quite low. Otherwise, the length of a numeral would not necessarily be logarithmic in its size.
(In certain non-standard positional numeral systems, including bijective numeration, the definition of the base or the allowed digits deviates from the above.)
In standard base-ten (
- .
In standard base-sixteen (hexadecimal), there are the sixteen hexadecimal digits (0–9 and A–F) and the number
where B represents the number eleven as a single symbol.
In general, in base-b, there are b digits and the number
has Note that represents a sequence of digits, not multiplication.
Notation
When describing base in
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.
To a given radix b the set of digits {0, 1, ..., b−2, b−1} is called the standard set of digits. Thus, binary numbers have digits {0, 1}; decimal numbers have digits {0, 1, 2, ..., 8, 9}; and so on. Therefore, the following are notational errors: 522, 22, 1A9. (In all cases, one or more digits is not in the set of allowed digits for the given base.)
Exponentiation
Positional numeral systems work using
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:
If the number 465 was in base-10, then it would equal:
(46510 = 46510)
If however, the number were in base 7, then it would equal:
(4657 = 24310)
10b = b for any base b, since 10b = 1×b1 + 0×b0. For example, 102 = 2; 103 = 3; 1016 = 1610. Note that the last "16" is indicated to be in base 10. The base makes no difference for one-digit numerals.
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 52 (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 82 (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.
Digits and numerals
A digit is a symbol that is used for positional notation, and a numeral consists of one or more digits used for representing a number with positional notation. Today's most common digits are the decimal digits "0", "1", "2", "3", "4", "5", "6", "7", "8", and "9". The distinction between a digit and a numeral is most pronounced in the context of a number base.
A non-zero numeral with more than one digit position will mean a different number in a different number base, but in general, the digits will mean the same.[12] For example, the base-8 numeral 238 contains two digits, "2" and "3", and with a base number (subscripted) "8". When converted to base-10, the 238 is equivalent to 1910, i.e. 238 = 1910. In our notation here, the subscript "8" of the numeral 238 is part of the numeral, but this may not always be the case.
Imagine the numeral "23" as having an ambiguous base number. Then "23" could likely be any base, from base-4 up. In base-4, the "23" means 1110, i.e. 234 = 1110. In base-60, the "23" means the number 12310, i.e. 2360 = 12310. The numeral "23" then, in this case, corresponds to the set of base-10 numbers {11, 13, 15, 17, 19, 21, 23, ..., 121, 123} while its digits "2" and "3" always retain their original meaning: the "2" means "two of", and the "3" means "three of".
In certain applications when a numeral with a fixed number of positions needs to represent a greater number, a higher number-base with more digits per position can be used. A three-digit, decimal numeral can represent only up to 999. But if the number-base is increased to 11, say, by adding the digit "A", then the same three positions, maximized to "AAA", can represent a number as great as 1330. We could increase the number base again and assign "B" to 11, and so on (but there is also a possible encryption between number and digit in the number-digit-numeral hierarchy). A three-digit numeral "ZZZ" in base-60 could mean 215999. If we use the entire collection of our
The common numeral systems in computer science are binary (radix 2), octal (radix 8), and hexadecimal (radix 16). In
Radix point
The notation can be extended into the negative exponents of the base b. Thereby the so-called radix point, mostly ».«, is used as separator of the positions with non-negative from those with negative exponent.
Numbers that are not
Sign
If the base and all the digits in the set of digits are non-negative, negative numbers cannot be expressed. To overcome this, a minus sign, here »-«, is added to the numeral system. In the usual notation it is prepended to the string of digits representing the otherwise non-negative number.
Base conversion
This section needs expansion. You can help by adding to it. (March 2017) |
The conversion to a base of an integer n represented in base can be done by a succession of Euclidean divisions by the right-most digit in base is the remainder of the division of n by the second right-most digit is the remainder of the division of the quotient by and so on. The left-most digit is the last quotient. In general, the kth digit from the right is the remainder of the division by of the (k−1)th quotient.
For example: converting A10BHex to decimal (41227):
0xA10B/10 = 0x101A R: 7 (ones place) 0x101A/10 = 0x19C R: 2 (tens place) 0x19C/10 = 0x29 R: 2 (hundreds place) 0x29/10 = 0x4 R: 1 ... 4
When converting to a larger base (such as from binary to decimal), the remainder represents as a single digit, using digits from . For example: converting 0b11111001 (binary) to 249 (decimal):
0b11111001/10 = 0b11000 R: 0b1001 (0b1001 = "9" for ones place) 0b11000/10 = 0b10 R: 0b100 (0b100 = "4" for tens) 0b10/10 = 0b0 R: 0b10 (0b10 = "2" for hundreds)
For the
Alternatively Horner's method can be used for base conversion using repeated multiplications, with the same computational complexity as repeated divisions.[14] A number in positional notation can be thought of as a polynomial, where each digit is a coefficient. Coefficients can be larger than one digit, so an efficient way to convert bases is to convert each digit, then evaluate the polynomial via Horner's method within the target base. Converting each digit is a simple lookup table, removing the need for expensive division or modulus operations; and multiplication by x becomes right-shifting. However, other polynomial evaluation algorithms would work as well, like repeated squaring for single or sparse digits. Example:
Convert 0xA10B to 41227 A10B = (10*16^3) + (1*16^2) + (0*16^1) + (11*16^0) Lookup table: 0x0 = 0 0x1 = 1 ... 0x9 = 9 0xA = 10 0xB = 11 0xC = 12 0xD = 13 0xE = 14 0xF = 15 Therefore 0xA10B's decimal digits are 10, 1, 0, and 11. Lay out the digits out like this. The most significant digit (10) is "dropped": 10 1 0 11 <- Digits of 0xA10B --------------- 10 Then we multiply the bottom number from the source base (16), the product is placed under the next digit of the source value, and then add: 10 1 0 11 160 --------------- 10 161 Repeat until the final addition is performed: 10 1 0 11 160 2576 41216 --------------- 10 161 2576 41227 and that is 41227 in decimal.
Convert 0b11111001 to 249 Lookup table: 0b0 = 0 0b1 = 1 Result: 1 1 1 1 1 0 0 1 <- Digits of 0b11111001 2 6 14 30 62 124 248 ------------------------- 1 3 7 15 31 62 124 249
Terminating fractions
The numbers which have a finite representation form the semiring
More explicitly, if is a factorization of into the primes with exponents ,[15] then with the non-empty set of denominators we have
where is the group generated by the and is the so-called
The
If divides , we have
Infinite representations
Rational numbers
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:
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 vinculum across the repeating block:
This is the repeating decimal notation (to which there does not exist a single universally accepted notation or phrasing). For base 10 it is called a repeating decimal or recurring 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:
-
- or, with the base implied:
- (see also 0.999...)
For integers p and q with
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:
- 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):
- (see also 0.999...)
Irrational numbers
A (real) irrational number has an infinite non-repeating representation in all integer bases.
Examples are the non-solvable nth roots
with and y ∉ Q, numbers which are called algebraic, or numbers like
which are
Applications
Decimal system
In the
As an example, the number 2674 in a base-10 numeral system is:
- (2 × 103) + (6 × 102) + (7 × 101) + (4 × 100)
or
- (2 × 1000) + (6 × 100) + (7 × 10) + (4 × 1).
Sexagesimal system
The
Modern time separates each position by a colon or a
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,
Computing
In
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 bits relate to one and only one octal digit.
Hexadecimal, decimal, octal, and a wide variety of other bases have been used for binary-to-text encoding, implementations of arbitrary-precision arithmetic, and other applications.
For a list of bases and their applications, see list of numeral systems.
Other bases in human language
Base-12 systems (
The
Remnants of a
In English the same base-20 counting appears in the use of "scores". Although mostly historical, it is occasionally used colloquially. Verse 10 of Psalm 90 in the King James Version of the Bible starts: "The days of our years are threescore years and ten; and if by reason of strength they be fourscore years, yet is their strength labour and sorrow". The Gettysburg Address starts: "Four score and seven years ago".
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.
The Welsh language continues to use a base-20 counting system, particularly for the age of people, dates and in common phrases. 15 is also important, with 16–19 being "one on 15", "two on 15" etc. 18 is normally "two nines". A decimal system is commonly used.
The
Danish numerals display a similar base-20 structure.
The Māori language of New Zealand also has evidence of an underlying base-20 system as seen in the terms Te Hokowhitu a Tu referring to a war party (literally "the seven 20s of Tu") and Tama-hokotahi, referring to a great warrior ("the one man equal to 20").
A number of
North and Central American natives used base-4 (quaternary) to represent the four cardinal directions. Mesoamericans tended to add a second base-5 system to create a modified base-20 system.
A base-5 system (quinary) has been used in many cultures for counting. Plainly it is based on the number of digits on a human hand. It may also be regarded as a sub-base of other bases, such as base-10, base-20, and base-60.
A base-8 system (
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
The Telefol language, spoken in Papua New Guinea, is notable for possessing a base-27 numeral system.
Non-standard positional numeral systems
Interesting properties exist when the base is not fixed or positive and when the digit symbol sets denote negative values. There are many more variations. These systems are of practical and theoretic value to computer scientists.
Balanced ternary[20] uses a base of 3 but the digit set is {1,0,1} instead of {0,1,2}. The "1" has an equivalent value of −1. The negation of a number is easily formed by switching the on the 1s. This system can be used to solve the balance problem, which requires finding a minimal set of known counter-weights to determine an unknown weight. Weights of 1, 3, 9, ... 3n known units can be used to determine any unknown weight up to 1 + 3 + ... + 3n units. A weight can be used on either side of the balance or not at all. Weights used on the balance pan with the unknown weight are designated with 1, with 1 if used on the empty pan, and with 0 if not used. If an unknown weight W is balanced with 3 (31) on its pan and 1 and 27 (30 and 33) on the other, then its weight in decimal is 25 or 1011 in balanced base-3.
- 10113 = 1 × 33 + 0 × 32 − 1 × 31 + 1 × 30 = 25.
The
Decimal equivalents | −3 | −2 | −1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Balanced base 3 | 10 | 11 | 1 | 0 | 1 | 11 | 10 | 11 | 111 | 110 | 111 | 101 |
Base −2 | 1101 | 10 | 11 | 0 | 1 | 110 | 111 | 100 | 101 | 11010 | 11011 | 11000 |
Factoroid | 0 | 10 | 100 | 110 | 200 | 210 | 1000 | 1010 | 1100 |
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 | for the one and an open left pointing wedge ⟨ for the ten) — up to 5+9=14 symbols per position (i.e. 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).[21] 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).[22]
See also
Examples:
Related topics:
- Algorism
- Hindu–Arabic numeral system
- Mixed radix
- Non-standard positional numeral systems
- Scientific notation
Other:
Notes
- ^ Kaplan, Robert (2000). The Nothing That Is: A Natural History of Zero. Oxford: Oxford University Press. pp. 11–12 – via archive.org.
- ^ "Greek numerals". Archived from the original on 26 November 2016. Retrieved 31 May 2016.
- ISBN 3-525-40725-4, pp. 150–153
- ^ Ifrah, page 187
- ^ L. F. Menabrea. Translated by Ada Augusta, Countess of Lovelace. "Sketch of The Analytical Engine Invented by Charles Babbage" Archived 15 September 2008 at the Wayback Machine. 1842.
- ^ ISBN 978-0-691-11485-9.
- ^ Gandz, S.: The invention of the decimal fractions and the application of the exponential calculus by Immanuel Bonfils of Tarascon (c. 1350), Isis 25 (1936), 16–45.
- ^ a b Lam Lay Yong, "The Development of Hindu-Arabic and Traditional Chinese Arithmetic", Chinese Science, 1996, p. 38, Kurt Vogel notation
- ^ Lay Yong, Lam. "A Chinese Genesis, Rewriting the history of our numeral system". Archive for History of Exact Sciences. 38: 101–108.
- ^ B. L. van der Waerden (1985). A History of Algebra. From Khwarizmi to Emmy Noether. Berlin: Springer-Verlag.
- ^ Martinus Nijhoff Publishers, Dutch original 1943
- mathematical sciencesthere is virtually only one positional-notation numeral system for each base below 10, and this extends with few, if insignificant, variations on the choice of alphabetic digits for those bases above 10.
- ^ We do not usually remove the lowercase digits "l" and lowercase "o", for in most fonts they are discernible from the digits "1" and "0".
- MR 0728973.
- ^ The exact size of the does not matter. They only have to be ≥ 1.
- ISBN 9780940490291, archivedfrom the original on 1 October 2016, retrieved 18 September 2019
- ^ Bartley, Wm. Clark (January–February 1997). "Making the Old Way Count" (PDF). Sharing Our Pathways. 2 (1): 12–13. Archived (PDF) from the original on 25 June 2013. Retrieved 27 February 2017.
- ISBN 9780198539568.
- ^ (Mallory & Adams 1997) Encyclopedia of Indo-European Culture
- ^ Knuth, pages 195–213
- ^ Ifrah, pages 326, 379
- ^ Ifrah, pages 261–264
References
- O'Connor, John; Robertson, Edmund (December 2000). "Babylonian Numerals". Archived from the original on 11 September 2014. Retrieved 21 August 2010.
- Kadvany, John (December 2007). "Positional Value and Linguistic Recursion". Journal of Indian Philosophy. 35 (5–6): 487–520. S2CID 52885600.
- ISBN 0-201-89684-2.
- Ifrah, George (2000). The Universal History of Numbers: From Prehistory to the Invention of the Computer. Wiley. ISBN 0-471-37568-3.
- ISBN 9780486233680.
External links
- Accurate Base Conversion
- The Development of Hindu Arabic and Traditional Chinese Arithmetics
- Implementation of Base Conversion at cut-the-knot
- Learn to count other bases on your fingers
- Online Arbitrary Precision Base Converter