# Converting Rational Numbers Between Different Bases

Nelson Morales

► To cite this version:

Nelson Morales. Converting Rational Numbers Between Different Bases. 2024. hal-04691212

HAL Id: hal-04691212

https://hal.science/hal-04691212v1

Preprint submitted on 7 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Converting Rational Numbers Between Different Bases

Nelson Morales

September 2023

## Abstract

Algorithm to convert rational numbers from any base to any base from 2 to 36 with complete accuracy and discussion on implementations.

## 1 Preliminaries

Rational numbers are all of those numbers that can be expressed as the fraction $\frac{p}{q}$ of two integers, a numerator $p$ and a non-zero denominator $q$. The set of all integers is denoted by $\mathbb{Z}$ and the set of all rationals by $\mathbb{Q}$. In positional notation, the base or radix is generally the amount of unique and weighted digits used to represent numbers. Although there are many positional notations, some of them even use non-integer bases, only integers bases between 2 and 36 will be considered here. Thus the valid digits will be the first $b$ digits in $0, \dots, 9, a, \dots, z$ for a base $b$. Therefore, a rational in base $b$ is usually expressed as $(d_m \dots d_0 \cdot d_{-1} \dots)_b$ where each digit $d_j$ is valid in base $b$. The dot between $d_0$ and $d_{-1}$ is called the radix point. Some rationals do not have finite expansion in a base given; for example, $\frac{1}{3}$ in base 10. A rational could have finite expansion in a base and could also not have in another base; for example, $0.1_{10}$ in base 2. The set of all rationals with finite expansion in base $b$ will be denoted by $\mathbb{Q}_b$.

**Theorem 1.** $\forall x \in \mathbb{Q} \wedge b > 1$,

$$x \in \mathbb{Q}_b \iff \exists n \ge 0 \in \mathbb{Z} : xb^n \in \mathbb{Z} \iff \exists C \in \mathbb{Z} : x = \frac{C}{b^n}.$$

The above theorem determines the algorithm. The proof is left at the end of the article. Some nontrivial examples that could be skipped:

$$\textbf{Example 1.} \quad x \in \mathbb{Q}_2 \implies \exists n : 2^n x \in \mathbb{Z} \implies 10^n x \in \mathbb{Z} \therefore x \in \mathbb{Q}_{10}$$

$$\textbf{Example 2.} \quad k \in \mathbb{Z} \implies \exists n : \frac{1}{2}(2k)^n = 2^{n-1}k^n \in \mathbb{Z} \therefore \frac{1}{2} \in \mathbb{Q}_{2k}$$

$$\textbf{Example 3.} \quad 0.1_{10} \in \mathbb{Q}_2 \implies \exists n : \frac{1}{10}2^n \in \mathbb{Z} \implies 5|2 \therefore 0.1_{10} \notin \mathbb{Q}_2$$

$$\textbf{Example 4.} \quad x \in \mathbb{Q}_2 \wedge b > 1 \implies \exists n : [x]b^n \in \mathbb{Z} \therefore [x] \in \mathbb{Q}_b$$
A machine with finite memory cannot always represent rational numbers with finite expansion. Computers are limited by the amount of memory they have. The double precision floating-point format is the standard way to represent numbers with fractional part nowadays. However, that format implies serious rounding error issues. Under these circumstances, another approach to represent rational numbers is preferable. A rational data type can represent a rational if, and only if, its integer data type is enough big to store each term. Arithmetic operations would be the main trouble with this type since they are prone to integer overflow errors. Conversely, floating-point arithmetic operations are rarely unsafe. The good new is avoiding integer overflow with a ratio type is easier than avoiding rounding issues with a float type.

# 2 Algorithm

This simple algorithm consists in converting the string representation of a rational in base $u$ to the string representation in base $v$. In other words, it is the implementation of the function $f: \mathbb{Q}_u \to \mathbb{Q}_v$. Arithmetic operations cannot clearly be made on strings. Thus the input string must first be converted to fraction in order to later create the output string. This divides the algorithm in two big steps and an intermediate step presented later.

## 2.1 String to Fraction

The string $S$ represents a rational in $\mathbb{Q}_u$. The output fraction has to be a rational in $\mathbb{Q}_v$; hence the denominator has to be $u^n$ where $n$ is the amount of digits read after the radix point.

1: function STOQ(S, u)

2: assert S is valid

3: $k \leftarrow 0$

4: $\frac{a}{b} \leftarrow \frac{0}{1}$

5: if $S_0 = -$ or $S_0 = +$ then

6: $k \leftarrow 1$

7: while $k < |S|$ and $S_k \neq$ . do

8: $a \leftarrow a * u + \text{ctoi}(S_k)$

9: $k \leftarrow k + 1$

10: if $k < |S|$ and $S_k = $ . then

11: $k \leftarrow k + 1$

12: while $k < |S|$ do

13: $b \leftarrow b * u$

14: $a \leftarrow a * u + \text{ctoi}(S_k)$

15: $k \leftarrow k + 1$

16: if $S_0 = -$ then

17: $a \leftarrow -a$

18: return $\frac{a}{b}$
## 2.2 Fraction to String

The input fraction is a rational in $Q_v$; hence the denominator is $v^m$ where $m$ is the amount of digits written before the radix point —trailing zeros are omitted.
The string $S$ has to represent a rational in $Q_v$.

1: **function** QTOS(R, v)

2: $\frac{L}{q} \leftarrow \lfloor R \rfloor$

3: **init** S with size $\lfloor \log_v(p \text{ if } p > q \text{ else } q) \rfloor + 3\rfloor$

4: $k \leftarrow |S| - 1$

5: **while** $q > 1$ **do**

6: $S_k \leftarrow \text{itoc}(p \bmod v)$

7: $p \leftarrow \lfloor p/v \rfloor$

8: $q \leftarrow \lfloor q/v \rfloor$

9: $k \leftarrow k - 1$

10: **if** $k \neq |S| - 1$ **then**

11: $S_k \leftarrow \cdot$

12: $k \leftarrow k - 1$

13: **repeat**

14: $S_k \leftarrow \text{itoc}(p \bmod v)$

15: $p \leftarrow \lfloor p/v \rfloor$

16: $k \leftarrow k - 1$

17: **until** $p = 0$

18: **if** $R < 0$ **then**

19: $S_k \leftarrow -$

20: **return** $S_{k...|S|}$

## 2.3 Fraction to Fraction

The intermediate step is converting the fraction from $Q_u$ to $Q_v$ since previous function will not work properly if $u \neq v$ in most cases. This task is usually impossible; nevertheless, truncating after $\delta \in \mathbb{Z}^+$ fractional digits is admissible.

1: **function** QTOQ(R, v)

2: $\frac{a}{b} \leftarrow \frac{0}{1}$

3: $\frac{L}{q} \leftarrow \lfloor R \rfloor$

4: $a \leftarrow \lfloor p/q \rfloor$

5: $p \leftarrow p \bmod q$

6: **for** $k \leftarrow 1$ **to** $\delta$ **do**

7: **if** $q \le 1$ **then** break

8: $\frac{L}{q} \leftarrow \text{reduce}(\frac{p*v}{q})$

9: $a \leftarrow a * v + \lfloor p/q \rfloor \bmod v$

10: $b \leftarrow b * v$

11: **if** $R < 0$ **then**

12: $a \leftarrow -a$

13: **return** $\frac{a}{b}$
# 3 Implementation

Some programming languages have a `ratio` type by default; Python `Fraction` and Ruby `Rational`, for instance. For those ones without an equivalent type is necessary defining it; for example, `struct { long p; long q; } ratio;` in C or the `std::pair` template in C++. If returning two values is possible, such as in Go, there is no need to define the structure. On the other hand, not all languages have built-in support for arbitrary-precision arithmetic; Python 3 does, Java provides the `abezgerc` class, but others require external dependencies as the GMP library. Handling errors will depend on the language style: assigning the proper value to `errno` in C or throwing the right exception in Java. An input string is valid if it matches the regex pattern `^[+-]?([a-z\d]*\. [a-z\d]+| [a-z\d]+)$`; although `+24.09` is valid, if its base is 6 then an error must be raised.

The functions `ctoi()` and `itoc()` were not defined since they depend on the implementation. They convert string digit representations to binary numbers and vice versa, respectively. The names are close to the classic `atoi()` function. The `reduce()` function simplifies the input fraction and return it —further steps for performance optimization should definitely consider this bottleneck. Finally, The $\delta$ value in `qtoq()` will vary according to requirements.

# 4 Appendix

The proof of Theorem 1.

*Proof.* WLOG $m, n \in \mathbb{Z}^+$

$$x = (\pm d_m \dots d_1 d_{-1} \dots d_{-n})_b = \frac{(\pm d_m \dots d_{-n})_b}{b^n} \iff (\pm d_m \dots d_{-n})_b = xb^n \in \mathbb{Z}$$

$$\text{Let } C = (\pm d_m \dots d_{-n})_b = xb^n \in \mathbb{Z} \text{ be then } x = \frac{C}{b^n}. \quad \square$$

The `qtos()` function hides a pearl: it is possible knowing the string size before building it. The amount of digits a rational $|\frac{a}{b^n}| \ge 1_b$ has in base $b$ is $\lfloor \log_b(|a|) + 1 \rfloor$ and $n+1$ if $|\frac{a}{b^n}| < 1_b$. Extra spaces guarantee that the minus sign and the radix point can fit if necessary —they could be computed though. One space more has to be added if the implementation uses null-terminated strings. For batch processing, nonetheless, a static buffer might improve performance if the input strings do not exceed a certain length.

$$\textbf{Theorem 2.} \quad x = (d_m \dots d_1 d_{-1} \dots d_{-n})_b \ge 1_b \implies m + n = \lfloor \log_b(|xb^n|) + 1 \rfloor$$

*Proof.* Let $s = m + n$ be and $d_{-n} \neq 0$

$$\begin{align*}
& \implies (10\dots0)_b \le xb^n < (\underset{(s+1)-\text{digits}}{10\dots0})_b & \implies b^{s-1} \le xb^n < b^s \\
& \implies s-1 \le \log_b(xb^n) < s & \implies s = \lfloor \log_b(xb^n) \rfloor + 1 \quad \square
\end{align*}$$