Editing Positional notation (section)

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