Editing Positional notation (section)

== Mathematics ==
{{unreferenced section|date=March 2013}}

=== Base of the numeral system ===
In [[numeral system|mathematical numeral systems]] the [[radix]] {{mvar|r}} is usually the number of unique [[Numerical digit|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]] <math>r=|b|</math> of the base {{mvar|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 <math>|b| </math> 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 [[logarithm]]ic 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 ([[decimal]]) positional notation, there are ten [[decimal digit]]s and the number
: <math>5305_{\mathrm{dec}} = (5 \times 10^3) + (3 \times 10^2) + (0 \times 10^1) + (5 \times 10^0)</math>.
In standard base-sixteen ([[hexadecimal]]), there are the sixteen hexadecimal digits (0–9 and A–F) and the number
: <math>14\mathrm{B}9_{\mathrm{hex}} = (1 \times 16^3) + (4 \times 16^2) + (\mathrm{B} \times 16^1) + (9 \times 16^0) \qquad (= 5305_{\mathrm{dec}}) ,</math>
where B represents the number eleven as a single symbol.

In general, in base-''b'', there are ''b'' digits <math>\{d_1,d_2,\dotsb,d_b\} =:D</math> and the number
:<math>(a_3 a_2 a_1 a_0)_b = (a_3 \times b^3) + (a_2 \times b^2) + (a_1 \times b^1) + (a_0 \times b^0) </math>
has <math>\forall k \colon a_k \in D .</math>
Note that <math>a_3 a_2 a_1 a_0</math> represents a sequence of digits, not [[multiplication]].

=== Notation ===
When describing base in [[mathematical notation]], the letter ''b'' is generally used as a [[symbol]] for this concept, so, for a [[Binary numeral system|binary]] system, ''b'' [[equality (mathematics)|equals]] 2. Another common way of expressing the base is writing it as a '''decimal''' subscript after the number that is being represented (this notation is used in this article). 1111011<sub>2</sub> implies that the number 1111011 is a base-2 number, equal to 123<sub>10</sub> (a [[decimal notation]] representation), 173<sub>8</sub> ([[octal]]) and 7B<sub>16</sub> ([[hexadecimal]]). In books and articles, when using initially the written abbreviations of number bases, the base is not subsequently printed: it is assumed that binary 1111011 is the same as 1111011<sub>2</sub>.

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 {{nowrap|{0, 1, 2, ..., 8, 9};}} and so on. Therefore, the following are notational errors: 52<sub>2</sub>, 2<sub>2</sub>, 1A<sub>9</sub>. (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 [[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 ''n''th power, where ''n'' is the number of other digits between a given digit and the [[radix point]]. If a given digit is on the left hand side of the radix point (i.e. its value is an [[integer]]) then ''n'' is positive or zero; if the digit is on the right hand side of the radix point (i.e., its value 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:
: <math>4\times b^2 + 6\times b^1 + 5\times b^0</math>

If the number 465 was in base-10, then it would equal:
: <math>465_{10} = 4\times 10^2 + 6\times 10^1 + 5\times 10^0 = 4\times 100 + 6\times 10 + 5\times 1 = 465_{10}</math>

If however, the number were in base 7, then it would equal:
: <math>465_{7} = 4\times 7^2 + 6\times 7^1 + 5\times 7^0 = 4\times 49 + 6\times 7 + 5\times 1 = 243_{10}</math>

10<sub>''b''</sub> = ''b'' for any base ''b'', since 10<sub>''b''</sub> = 1×''b''<sup>1</sup> + 0×''b''<sup>0</sup>. For example, 10<sub>2</sub> = 2; 10<sub>3</sub> = 3; 10<sub>16</sub> = 16<sub>10</sub>. 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 5<sup>2</sup> (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<sup>2</sup> (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 [[Arabic numerals|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.<ref>The digit will retain its meaning in other number bases, in general, because a higher number base would normally be a notational extension of the lower number base in any systematic organization. In the [[mathematical science]]s there 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.</ref> For example, the base-8 numeral 23<sub>8</sub> contains two digits, "2" and "3", and with a base number (subscripted) "8". When converted to base-10, the 23<sub>8</sub> is equivalent to 19<sub>10</sub>, i.e. 23<sub>8</sub> = 19<sub>10</sub>. In our notation here, the subscript "<sub>8</sub>" of the numeral 23<sub>8</sub> is part of the numeral, but this may not always be the case.

Imagine the numeral "23" as having [[#Non-standard positional numeral systems|an ambiguous base]] number. Then "23" could likely be any base, from base-4 up. In base-4, the "23" means 11<sub>10</sub>, i.e. 23<sub>4</sub> = 11<sub>10</sub>. In base-60, the "23" means the number 123<sub>10</sub>, i.e. 23<sub>60</sub> = 123<sub>10</sub>. 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 '''{{val|215999}}'''. If we use the entire collection of our [[alphanumerics]] we could ultimately serve a base-''62'' numeral system, but we remove two digits, uppercase "I" and uppercase "O", to reduce confusion with digits "1" and "0".<ref>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".</ref>
We are left with a base-60, or sexagesimal numeral system utilizing 60 of the 62 standard alphanumerics. (But see ''[[#Sexagesimal system|Sexagesimal system]]'' below.) In general, the number of possible values that can be represented by a <math>d</math> digit number in base <math>r</math> is <math>r^d</math>.

The common numeral systems in computer science are binary (radix 2), octal (radix 8), and hexadecimal (radix 16). In [[Binary numeral system|binary]] only digits "0" and "1" are in the numerals. In the [[octal]] numerals, are the eight digits 0–7. [[Hexadecimal|Hex]] is 0–9 A–F, where the ten numerics retain their usual meaning, and the alphabetics correspond to values 10–15, for a total of sixteen digits. The numeral "10" is binary numeral "2", octal numeral "8", or hexadecimal numeral "16".

=== Radix point ===
{{main|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 [[integer]]s use places beyond the [[radix point]]. For every position behind this point (and thus after the units digit), the exponent ''n'' of the power ''b''<sup>''n''</sup> decreases by 1 and the power approaches 0. For example, the number 2.35 is equal to:
:<math>2\times 10^0 + 3\times 10^{-1} + 5\times 10^{-2}</math>

=== Sign ===
{{main|Sign (mathematics)}}
If the base and all the digits in the set of digits are non-negative, negative numbers cannot be expressed. To overcome this, a [[Negative number|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 is the target of a redirect -->
{{expand section|date=March 2017}}
The conversion to a base <math>b_2</math> of an integer {{math|''n''}} represented in base <math>b_1</math> can be done by a succession of [[Euclidean division]]s by <math>b_2:</math> the right-most digit in base <math>b_2</math> is the remainder of the division of {{math|''n''}} by <math>b_2;</math> the second right-most digit is the remainder of the division of the quotient by <math>b_2,</math> and so on. The left-most digit is the last quotient. In general, the {{math|''k''}}th digit from the right is the remainder of the division by <math>b_2</math> of the  {{math|(''k''−1)}}th quotient.

For example: converting A10B<sub>Hex</sub> to decimal (41227):
 0xA10B/10 = Q: 0x101A R: 7 (ones place)
 0x101A/10 = Q: 0x19C  R: 2 (tens place)
  0x19C/10 = Q: 0x29   R: 2 (hundreds place)
   0x29/10 = Q: 0x4    R: 1  ...
                          4

When converting to a larger base (such as from binary to decimal), the remainder represents <math>b_2</math> as a single digit, using digits from <math>b_1</math>. For example: converting 0b11111001 (binary) to 249 (decimal):
 0b11111001/10 = Q: 0b11000 R: 0b1001 (0b1001 = "9" for ones place)
    0b11000/10 = Q: 0b10    R: 0b100  (0b100 =  "4" for tens)
       0b10/10 = Q: 0b0     R: 0b10   (0b10 =   "2" for hundreds)

For the [[Fraction (mathematics)|fractional]] part, conversion can be done by taking digits after the radix point (the numerator), and [[Long division|dividing]] it by the [[Fraction (mathematics)#Decimal fractions and percentages|implied denominator]] in the target radix. Approximation may be needed due to a possibility of [[Repeating decimal#Extension to other bases|non-terminating digits]] if the [[Irreducible fraction|reduced]] fraction's denominator has a prime factor other than any of the base's prime factor(s) to convert to. For example, 0.1 in decimal (1/10) is 0b1/0b1010 in binary, by dividing this in that radix, the result is 0b0.0<span style="text-decoration: overline;">0011</span> (because one of the prime factors of 10 is 5). For more general fractions and bases see the [[Repeating decimal#Algorithm for positive bases|algorithm for positive bases]].

Alternatively, [[Horner's method]] can be used for base conversion using repeated multiplications, with the same computational complexity as repeated divisions.<ref>
{{cite book
 | last1 = Collins | first1 = G. E.
 | last2 = Mignotte | first2 = M.
 | last3 = Winkler | first3 = F.
 | editor1-last = Buchberger | editor1-first = Bruno
 | editor2-last = Collins | editor2-first = George Edwin
 | editor3-last = Loos | editor3-first = Rüdiger
 | editor4-last = Albrecht | editor4-first = Rudolf
 | contribution = Arithmetic in basic algebraic domains
 | contribution-url = https://www3.risc.jku.at/publications/download/risc_229/paper_55.pdf
 | doi = 10.1007/978-3-7091-7551-4_13
 | isbn = 3-211-81776-X
 | mr = 728973
 | pages = 189–220
 | publisher = Springer | location = Vienna
 | series = Computing Supplementa
 | title = Computer Algebra: Symbolic and Algebraic Computation
 | volume = 4
 | year = 1983
}}</ref>  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 [[Exponentiation by squaring|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]]
: <math>\frac{\N_0}{b^{\N_0}} := \left\{mb^{-\nu}\mid m\in \N_0 \wedge \nu\in \N_0 \right\} .</math>
More explicitly, if <math>p_1^{\nu_1} \cdot \ldots \cdot p_n^{\nu_n} := b</math> is a [[factorization]] of <math>b</math> into the primes <math>p_1, \ldots ,p_n \in \mathbb P</math> with exponents {{nowrap|<math>\nu_1, \ldots ,\nu_n \in \N</math>,<ref>The exact size of the <math>\nu_1, \ldots ,\nu_n</math> does not matter. They only have to be ≥ 1.</ref>}} then with the non-empty set of denominators <math> S := \{ p_1, \ldots, p_n \} </math>
we have
: <math> \Z_S := \left\{x \in \Q \left | \, \exists \mu_i \in \Z : x \prod_{i=1}^n {p_i}^{\mu_i} \in \Z \right . \right\} = b^{\Z} \, \Z = {\langle S\rangle}^{-1}\Z </math>
where <math>\langle S\rangle</math> is the group generated by the <math>p\in S</math> and <math> {\langle S\rangle}^{-1}\Z </math> is the so-called [[Localization (algebra)#Localization of a ring|localization]] of <math>\Z</math> with respect to {{nowrap|<math>S</math>.}}

The [[Fraction (mathematics)|denominator]] of an element of <math> \Z_S </math> contains if reduced to lowest terms only prime factors out of <math>S</math>.
This [[Ring (mathematics)|ring]] of all terminating fractions to base <math>b</math> is [[Dense set|dense]] in the field of [[rational number]]s <math>\Q</math>. Its [[Complete metric space|completion]] for the usual (Archimedean) metric is the same as for <math>\Q</math>, namely the real numbers <math>\R</math>. So, if <math> S = \{ p\} </math> then <math> \Z_{\{ p\}} </math> has not to be confused with <math>\Z_{(p)} </math>, the [[discrete valuation ring]] for the [[prime number|prime]] <math>p</math>, which is equal to <math>\Z_{T} </math> with <math> T = \mathbb P \setminus \{ p\} </math>.

If <math>b</math> divides <math>c</math>, we have <math> b^{\Z} \, \Z \subseteq c^{\Z} \, \Z.</math>

=== 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&nbsp;... base-3 represents the sum of the infinite [[series (mathematics)|series]]:
:<math>\begin{array}{l}
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
\end{array}</math>

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 (symbol)|vinculum]] across the repeating block:<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Vinculum |url=https://mathworld.wolfram.com/Vinculum.html |access-date=2024-08-22 |website=mathworld.wolfram.com |language=en}}</ref>
: <math>2.42\overline{314}_5 = 2.42314314314314314\dots_5</math>

This is the [[Repeating decimal#Notation|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:
: <math>0.1_3</math>
: <math>0.\overline3_{10} = 0.3333333\dots_{10}</math>
:: or, with the base implied:
:: <math>0.\overline3 = 0.3333333\dots</math> (see also [[0.999...]])
: <math>0.\overline{01}_2 = 0.010101\dots_2</math>
: <math>0.2_6</math>

For integers ''p'' and ''q'' with [[greatest common divisor|''gcd'']] (''p'', ''q'') = 1, the [[fraction (mathematics)|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:
# A finite or infinite number of zeroes can be appended:
#: <math>3.46_7 = 3.460_7 = 3.460000_7 = 3.46\overline0_7</math>
# 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):
#: <math>3.46_7 = 3.45\overline6_7</math>
#: <math>1_{10} = 0.\overline9_{10}\qquad</math> (see also [[0.999...]])
#: <math>220_5 = 214.\overline4_5</math>

==== Irrational numbers ====
{{main|irrational number}}
A (real) irrational number has an infinite non-repeating representation in all integer bases.<ref>{{Cite web |date=2024-04-10 |title=Irrational Numbers: Definition, Examples and Properties |url=https://flamath.com/en/irrational-numbers#:~:text=The%20main%20characteristic%20of%20irrational%20numbers%20is%20that,number%20where%20a%20group%20of%20digits%20repeats%20constantly. |access-date=2024-08-22 |website=flamath.com |language=en-US}}</ref>

Examples are the non-solvable [[nth root|''n''th roots]]
: <math>y = \sqrt[n]{x} </math>
with <math>y^n = x</math> and {{math|''y'' ∉ '''Q'''}}, numbers which are called [[algebraic number|algebraic]], or numbers like
:<math>\pi,e</math>
which are [[transcendental number|transcendental]]. The number of transcendentals is [[uncountable]] and the sole way to write them down with a finite number of symbols is to give them a symbol or a finite sequence of symbols.