| Position | \(3\) | \(2\) | \(1\) | \(0\) | \(-1\) | \(-2\) | \(-3\) | \(\cdots\) |
| Weight | \(b^3\) | \(b^2\) | \(b^1\) | \(b^0\) | \(b^{-1}\) | \(b^{-2}\) | \(b^{-3}\) | \(\cdots\) |
| Digit | \(a_3\) | \(a_2\) | \(a_1\) | \(a_0\) | \(a_{-1}\) | \(a_{-2}\) | \(a_{-3}\) | \(\cdots\) |
| Example weight | \(10^3\) | \(10^2\) | \(10^1\) | \(10^0\) | \(10^{-1}\) | \(10^{-2}\) | \(10^{-3}\) | \(\cdots\) |
| Example digit | 5 | 6 | 2 | 7 | 3 | 5 | 0 | \(\cdots\) |
Appendix H — Positional number systems
Definition H.1 (Positional notation) Positional notation using base \(b\) (or radix \(b\)) is defined by the rule (Knuth 1997, 2:195):
\[(a_na_{n-1} \ldots a_1a_0.a_{-1}a_{-2}a_{-3} \ldots)_b= \sum_{k=0}^n a_kb^k + \sum_{k = 1}^{\infty} a_{-k}b^{-k}\] Where the \(a\)’s are called the digits of the representation.
Also \(0 \leq a_k < b\), \(0 \leq a_{-k} < b\) and \(b^k, b^{-k}\) are the weights, \(w\), of the corresponding digits where the position \(k\) is the base \(b\) logarithm of the corresponding \(w\), that is \(k = \log_b w = \log_b b^k\).
Furthermore, the dot, \(.\) , that appears between \(a_0\) and \(a_{-1}\) is called the radix point were it is used to identify the integer part from the fractional part of the representation. In that sense, \(a_n\) to \(a_0\) is the integer part follow by the radix point and then \(a_{-1}, a_{-2}, a_{-3}, \ldots\) is the fractional part.
Example H.1 (For \((5627.35)_{10}\)) We have that \(b=10\) and \((5627.35)_{10} = 5 \cdot 10^3 + 6 \cdot 10^2 + 2 \cdot 10^1 + 7 \cdot 10^0 + 3 \cdot 10^{-1} + 5 \cdot 10^{-2} + 0 \cdot 10^{-3} + \cdots\) where:
H.1 Base conversion (Britton 2017)
H.1.1 Convert from base \(10\) to base \(b\)
H.1.1.1 Integer part
- Divide the integer part by \(b\) and record the remainder
- Take the quotient from the previous division and divide it by \(b\), recording the new remainder
- Repeat step 2. until the quotient becomes \(0\)
- The integer part in base \(b\) is the remainders written in reverse order
H.1.1.2 Fraction part
- Multiply the fraction part by \(b\) and record the integer part
- Take the fractional part of the result and multiply it by \(b\), then record the new integer part
- Repeat step 2. until the fractional part becomes \(0\) or you have reached the desired number of digits to avoid infinite loops in repeating decimals
- The fractional part in base \(b\) is the sequence of recorded integers written in order
Example H.2 (For \((45.3689)_{10}\) to base \(2\) with 5 decimal places) In base \(2\) the digits can be defined as \(\{ 1, 2 \}\).
| Integer part | |||
|---|---|---|---|
| Step | Division | Quotient | Remainder |
| 1 | \(\frac{45}{2}\) | 22 | 1 |
| 2 | \(\frac{22}{2}\) | 11 | 0 |
| 3 | \(\frac{11}{2}\) | 5 | 1 |
| 4 | \(\frac{5}{2}\) | 2 | 1 |
| 5 | \(\frac{2}{2}\) | 1 | 0 |
| 6 | \(\frac{1}{2}\) | 0 | 1 |
| Fractional part | |||
|---|---|---|---|
| Step | Multiplication | Integer | Fraction |
| 1 | \(0.3689 \times 2 = 0.7378\) | 0 | 0.7378 |
| 2 | \(0.7378 \times 2 = 1.4756\) | 1 | 0.4756 |
| 3 | \(0.4756 \times 2 = 0.9512\) | 0 | 0.9512 |
| 4 | \(0.9512 \times 2 = 1.9024\) | 1 | 0.9024 |
| 5 | \(0.9024 \times 2 = 1.8048\) | 1 | 0.8048 |
Therefore \((45.3689)_{10} \approx (101101.01011)_2\)
Example H.3 (For \((1251.9324)_{10}\) to base \(16\) with 6 decimal places) In base \(16\) the digits can be defined as \(\{ 1, 2, \ldots, 8, 9, A, B, C, D, E, F \}\).
| Integer part | ||||
|---|---|---|---|---|
| Step | Division | Quotient | Remainder | 16 base digit |
| 1 | \(\frac{1251}{16}\) | 78 | 3 | 3 |
| 2 | \(\frac{78}{16}\) | 4 | 14 | E |
| 3 | \(\frac{4}{16}\) | 0 | 4 | 4 |
| Integer part | ||||
|---|---|---|---|---|
| Step | Multiplication | Integer | 16 base digit | Fraction |
| 1 | \(0.9324 \times 16 = 14.9184\) | 14 | E | 0.9184 |
| 2 | \(0.9184 \times 16 = 14.6944\) | 14 | E | 0.6944 |
| 3 | \(0.6944 \times 16 = 11.1104\) | 11 | B | 0.1104 |
| 4 | \(0.1104 \times 16 = 1.7664\) | 1 | 1 | 0.7664 |
| 5 | \(0.7664 \times 16 = 12.2624\) | 12 | C | 0.2624 |
| 6 | \(0.2624 \times 16 = 4.1984\) | 4 | 4 | 0.1984 |
Therefore \((1251.9324)_{10} \approx (4E3.EEB1C4)_{16}\)
H.1.2 Convert from base \(b\) to base \(10\)
H.1.2.1 Integer part
\[\begin{align*} (a_na_{n-1} \ldots a_1a_0)_b & = a_n \cdot b^n + a_{n-1} \cdot b^{n-1} + \dots a_1 \cdot b^1 + a_0 \cdot b^0 \\ & = \left( \sum_{k=0}^n a_kb^k \right)_{10} \end{align*}\]
H.1.2.2 Fraction part
\[\begin{align*} (a_{-1}a_{-2}a_{-3} \cdots)_b & = a_{-1} \cdot b^{-1} + a_{-2} \cdot b^{-2} + a_{-3} \cdot b^{-3} + \ldots \\ & = \left( \sum_{k=1}^{\infty} a_{-k}b^{-k} \right)_{10} \end{align*}\]
Example H.4 (For \((12011.1022)_3\) to base \(10\) with 4 decimal places) In base \(3\) the digits can be defined as \(\{ 1, 2, 3 \}\).
- Integer part
\[\begin{align*} (12011)_3 & = 1 \cdot 3^4 + 2 \cdot 3^3 + 0 \cdot 3^2 + 1 \cdot 3^1 + 1 \cdot 3^0 \\ & = 81 + 54 + 0 + 3 + 1 \\ & = (139)_{10} \end{align*}\]
- Fraction part
\[\begin{align*} (0.1022)_3 & = 1 \cdot 3^{-1} + 0 \cdot 3^{-2} + 2 \cdot 3^{-3} + 2 \cdot 3^{-4} \\ & = \frac{1}{3} + 0 + \frac{2}{27} + \frac{2}{81} \\ & \approx 0.3333 + 0 + 0.0741 + 0.0247 \\ & = 0.4321 \end{align*}\]
Therefore \((12011.1022)_3 \approx (139.4321)_{10}\)
Example H.5 (For \((C4B3.3A9D)_{14}\) to base \(10\) with 5 decimal places) In base \(14\) the digits can be defined as \(\{ 1, 2, \ldots, 8, 9, A, B, C, D \}\).
- Integer part
\[\begin{align*} (C4B3)_{14} & = C \cdot 14^3 + 4 \cdot 14^2 + B \cdot 14^1 + 3 \cdot 14^0 \\ & = 12 \cdot 14^3 + 4 \cdot 14^2 + 11 \cdot 14^1 + 3 \cdot 14^0 \\ & = 12 \cdot 2744 + 4 \cdot 196 + 11 \cdot 14 + 3 \\ & = (33869)_{10} \end{align*}\]
- Fraction part
\[\begin{align*} (0.3A9D)_{14} & = 3 \cdot 14^{-1} + A \cdot 14^{-2} + 9 \cdot 14^{-3} + D \cdot 14^{-4} \\ & = \frac{3}{14} + \frac{10}{196} + \frac{9}{2744} + \frac{13}{38416} \\ & \approx 0.21429 + 0.05102 + 0.00328 + 0.00034 \\ & = 0.26893 \end{align*}\]
Therefore \((12011.1022)_{14} \approx (33869.26893)_{10}\)
H.1.3 Convert from base \(b\) to base \(a\)
- Convert from base \(b\) to base \(10\)
- Convert from base \(10\) to base \(a\)
This workflow is implemented taking into account that many programming languages use base \(10\) arithmetic. Also in Table H.6 it is shown possible common digits used for different bases but there are other available options as described in (Josefsson 2006) to avoid that characters like 0 and O or 1, l and I are not easily confused.
| Base | Digits used |
|---|---|
| 2 | 0 1 |
| 8 | 0 1 2 3 4 5 6 7 |
| 10 | 0 1 2 3 4 5 6 7 8 9 |
| 16 | 0 1 2 3 4 5 6 7 8 9 A B C D E F |
| 32 | 0–9 + A–V |
| 36 | 0–9 + A–Z |
| 62 | 0–9 + A–Z + a–z |
In Listing H.1 it is shown an implementation to convert from base \(10\) to base \(b\) for the case of Example H.3 and adding the possibility to include negative numbers using ideas from GeeksforGeeks (2023).
Code
# From base 10 to base b ----
## Auxiliar functions ----
### From int to char ---
int_to_char <- function(int) {
# Define constants
zero <- utf8ToInt("0")
A <- utf8ToInt("A")
a <- utf8ToInt("a")
if (int >= 0 && int <= 9) {
return(intToUtf8(int + zero)) # 0–9 → '0'–'9'
} else if (int >= 10 && int <= 35) {
return(intToUtf8(int - 10 + A)) # 10–35 → 'A'–'Z'
} else if (int >= 36 && int <= 61) {
return(intToUtf8(int - 36 + a)) # 36–61 → 'a'–'z'
} else {
# Error for unsupported integers
stop(sprintf(
"Invalid integer: %d\nOnly integers from '0'-'61' are valid\n(base 2 to base 62).",
int
))
}
}
### Integer part ----
from_decimal_int_part <- function(int,
base) {
# Initial values
q <- int # quotient
r <- character() # residual
# Handling int = 0
if (q == 0) {
return("0")
}
# Convert int in base 10 to another base
# when num > 0
while (q > 0) {
r <- c(r, int_to_char(q %% base))
q <- q %/% base
}
# Reverse the result
int_part <- paste0(rev(r), collapse = "")
return(int_part)
}
### Fractional part ---
from_decimal_frac_part <- function(frac,
base,
decimal_places) {
# Initial values
frac_part <- character(0)
# Handling decimal_places = 0
if (decimal_places == 0) {
return(NULL)
}
# Convert frac in base 10 to another base
for (i in 1:decimal_places) {
mult <- frac * base
int <- trunc(mult)
frac_part <- c(frac_part, int_to_char(int))
frac <- mult - int
}
frac_part <- paste0(frac_part, collapse = "")
return(frac_part)
}
## Principal function ----
from_decimal <- function(num,
base,
decimal_places) {
# Handle num < 0
num_abs <- abs(num)
# Extract integer and fractional part
int <- trunc(num_abs)
frac <- num_abs - int
# Integer part
int_part <- from_decimal_int_part(int,
base)
# Fractional part
frac_part <- from_decimal_frac_part(frac,
base,
decimal_places)
# Mergin integer and fractional part
if (is.null(frac_part)) {
result <- int_part
} else {
result <- paste0(int_part, ".", frac_part)
}
# Add minus sign if needed
if (num < 0) {
result <- paste0("-", result)
}
return(result)
}
### Check ----
# It may generate
# imprecisions during the conversion process
# for the parameter decimal places
from_decimal(num = -1251.9324,
base = 16,
decimal_places = 6)[1] "-4E3.EEB1C4"Also in Listing H.2 using ideas from GeeksforGeeks (2023), it is shown an implementation to convert from base \(b\) to base \(10\) for the case of Example H.5.
Code
# From base b to base 10 ----
## Auxiliar functions ----
is_well_formed <- function(char) {
# Using raw strings
result <- grepl(r"(^[-]?[0-9A-Za-z]+(\.[0-9A-Za-z]+)?$)",
char)
return(result)
}
char_to_int <- function(char) {
# Convert character to int
int <- utf8ToInt(char)
# Define constants
zero <- utf8ToInt("0")
A <- utf8ToInt("A")
a <- utf8ToInt("a")
if (int >= zero && int <= zero + 9) {
return(int - zero) # '0'–'9' → 0–9
} else if (int >= A && int <= A + 25) {
return(int - A + 10) # 'A'–'Z' → 10–35
} else if (int >= a && int <= a + 25) {
return(int - a + 36) # 'a'–'z' → 36–61
} else {
# Error for unsupported characters
stop(sprintf(
"Invalid digit: '%s'.\nOnly characters from '0'-'9', 'A'-'Z', and 'a'-'z' are valid\n(base 2 to base 62).",
intToUtf8(int)
))
}
}
### Integer part ----
to_decimal_int_part <- function(char, base) {
char <- strsplit(char, "")[[1]]
len <- length(char)
power <- 1
num <- 0
for (i in rev(seq_len(len))) {
digit <- char_to_int(char[i])
if (digit >= base) {
stop(sprintf(
"Invalid digit: '%s'\nThis digit is not valid in base %d\n(base 2 to base 62)",
char[i], base
))
}
num <- num + digit * power
power <- power * base
}
return(num)
}
### Fractional part ---
to_decimal_frac_part <- function(char, base) {
char <- strsplit(char, "")[[1]]
len <- length(char)
power <- base^(-1)
num <- 0
for (i in seq_len(len)) {
digit <- char_to_int(char[i])
if (digit >= base) {
stop(sprintf(
"Invalid digit: '%s'\nThis digit is not valid in base %d\n(base 2 to base 62)",
char[i], base
))
}
num <- num + digit * power
power <- power * base^(-1)
}
return(num)
}
## Principal function ----
to_decimal <- function(char,
base,
decimal_places) {
is_char_well_formed <- is_well_formed(char)
if (!is_char_well_formed) {
stop(sprintf(
"Invalid expression: '%s'",
char
))
}
# Handle char with -
char_abs <- sub("-", "", char)
# Extract integer and fractional part
char_split <- strsplit(char_abs, r"(\.)")[[1]]
int <- char_split[1]
frac <- char_split[2]
# Integer part
int_part <- to_decimal_int_part(int,
base)
# Fractional part
if (!is.na(frac)) {
frac_part <- to_decimal_frac_part(frac,
base)
}
# Mergin integer and fractional part
if (is.na(frac_part)) {
result <- int_part
} else {
result <- int_part + frac_part
}
# Add minus sign if needed
start_with_minus <- startsWith(char, "-")
if (start_with_minus) {
result <- -result
}
# Control the number of decimal places to show
result <- formatC(result,
decimal_places,
format = "f")
return(result)
}
### Check ----
# It may generate
# imprecisions during the conversion process
# for the parameter decimal places
to_decimal("C4B3.3A9D",
base = 14,
decimal_places = 5)[1] "33869.26892"H.2 Non uniqueness of positional notation representation
Sometimes a number can be represented in 2 ways. For example in base \(10\) the number \(0.5\) can also be represented as \(0.4999\ldots\). In that case according to Definition H.1:
\((0.5)_{10} = 0*10^0 + 5*10^{-1} + 0*10^{-2} + 0*10^{-3} + 0*10^{-4} + \cdots\)
\((0.4999\ldots)_{10} = 0*10^0 + 4*10^{-1} + 9*10^{-2} + 9*10^{-3} + 9*10^{-4} + \cdots\)
Therefore \((0.5)_{10}\) has also 2 representations in another base. For example in base \(2\) we have that \((0.5)_{10}\) or \((0.4999\ldots)_{10}\) can be represented as:
- \((0.1000\ldots)_{2}\)
- \((0.0111\ldots)_{2}\)