How to tell if a fraction can be finitely represented in binary (or any other base)

If you found this post, something has gone wrong, it should be accessible by a direct link only (like unlisted youtube videos).

I would like to apologize to all professional mathematicians reading this for my clumsy approach to explaining the subject. I really am doing my best.

It is often said that one cannot represent numbers like $0.1$ by binary floating point numbers. That is, of course, true (assuming positional notation is implied, otherwise it is as simple as $\frac{1}{1010_2}$ ). Unfortunately, in most cases, the advice ends here. Sometimes, there’s an example included, first to show that the process is correct:

$\centering \def\arraystretch{1.5} \begin{tabular}{ c | c c } $\textbf{0}.5$ & $0.25$ & $\times 2$ \\ $\textbf{1}.0$ & $0.5$ & $\times 2$ \\ -- & $0.0$ & \\ \end{tabular}$

$\centering $0.25_{10} = 0.01_2$$

It is then followed by the aforementioned impossible example, or a variation thereof:

$\centering \def\arraystretch{1.5} \begin{tabular}{ c | c c } $\textbf{0}.2$ & $0.1$ & $\times 2$ \\ $\textbf{0}.4$ & $\textbf{0.2}$ & $\times 2$ \\ $\textbf{0}.8$ & $0.4$ & $\times 2$ \\ $\textbf{1}.6$ & $0.8$ & $\times 2$ \\ $\textbf{1}.2$ & $0.6$ & $\times 2$ \\ $\textbf{0}.4$ & $\textbf{0.2}$ & $\times 2$ \\ \vdots & \vdots & \vdots \\ \end{tabular}$

$0.1_{10} = 0.0(0011)\hdots_2$

This explanation is rather flimsy: sure, we can see that this method failed to achieve the wanted result, but does it prove anything? It would be much better to understand the rules governing it.

For this reason, one should remember how the positional notation works. Let’s suppose there is a number $abc.de$ base $n$ , where $a$ , $b$ , $c$ , $d$ and $e$ are digits (in base $n$ , each digit has an integer value between $0$ and $n-1$ , inclusive). The value of a number encoded this way is a sum of its digits, each multiplied by power of $n$ respective to it’s position:

$\centering \def\arraystretch{1.5} \begin{tabular}{ c | c | c | c | c | c } $n^{2}$ & $n^{1}$ & $n^{0}$ & & $n^{-1}$ & $n^{-2}$ \\ \hline $a$ & $b$ & $c$ & $.$ & $d$ & $e$ \\ \end{tabular}$

In other words:

$abc.de_n = a \cdot n^2 + b \cdot n^1 + c \cdot n^0 + d \cdot n^{-1} + e \cdot n^{-2}$

From here we can easily posit that $abc.de_n = \frac{abcde_n}{n^2}$ . It is important, because not only are all combinations of five digit numbers represented by this, but also it is clear that there is no possible five-or-less digit numerator that would not be represented by one of combinations.

In more general terms, any finite integer $i$ has finite positional base $n$ representation $\frac{i}{n^m}$ for any integer $m$ .

With this fact in mind, it is easy to check any fraction for a finite representation in base $n$ : after reducing it to the lowest terms, one should check the prime factors of the denominator. If they are a subset of set of $n$ ‘s prime factors then it is possible to transform the fraction to the form of $\frac{i}{n^m}$ and therefore this fraction has a finite base $n$ representation.

For example, in base $12$ (prime factors: $2$ (twice) and $3$ ) both $\frac{1}{3}$ and $\frac{1}{4}$ can be represented without any loss of precision, the values being $0.4_{12}$ and $0.3_{12}$ respectively. The representation of $\frac{1}{5}$ is infinite, on the other hand: $0.(2497)\hdots_{12}$ .

This is because one can trivially transform them to the aformentioned $\frac{i}{n^m}$ form. In case of $\frac{1}{3}$ :

$\frac{1}{3} \cdot \frac{4}{4} = \frac{4}{12} = \frac{4}{12^1} = 0.4_{12}$

As for $\frac{1}{5}$ it is not possible to transform it to the yearned form, because $5$ is not a prime factor of $12^m$ for any positive integer $m$ .

Leave a Reply Cancel reply