Algorithm for creating binary rational numbers

Question

I read here an algorithm to convert a decimal rational number to binary by multiplications by 2, but although it's very simple to carry on, I still haven't managed to explain myself why it works.

Anyway at least I've understood the principle behind the algorithm to convert a decimal integer to binary by successive division by 2. Now I'm asking whether both methods might ever be the same exact algorithm in two different forms, since the multiplication by 2 is just a division by 1/2. But as for the rest of the algorithm? Why does one perform operations on the quotients and the other continuously subtract 1 from the product?

Could anyone give a rather formal proof for these algorithms, and particularly for the one for rational numbers?

Answer 1

A bit of a rambling answer, here's the short answer to the question of why divide vs. multiply to find the digits:

The reason that you divide to get the integer value and multiply to get the fractional value is because you are moving the digits towards the one's place: $2^0$. When the digits are to the left of the decimal (integers) you need to divide by $2$ to move them towards $2^0$ and when the digits are to the right of the decimal (fractions) then you need to multiply by $2$ to bring the digits closer to $2^0$.

Original Answer:

The multiply by $2$ is no different than in elementary school when you're taught how to divide by $10$, $100$, $1000$, etc. by moving the decimal place. Let me do this backwards as an example. Say you are told that the wavelength of green light is $0.000\ 000\ 510$ meters--how many nanometers is this? The conversion is $0.000\ 000\ 510 \text{ meters } * \frac{10^9 \text{ nm}}{1 \text{ meter}}$. So you just multiply by $10^9$ to get the nanometers. This can be done by moving the decimal nine places to the right: first move it three spots: $000.000\ 510$, next move it three more places ($6$ total): $000\ 000.510$, and finally move it three more (total of $9$): $000\ 000\ 510 = 510$ nm.

Converting Fractional Numbers

Finding decimal values for base two is essentially the same. Formally think about what you are trying to do. Let's find the base $2$ form of a value $x$ which we know is positive and less than $1$:

$$ x = n_1 \frac{1}{2} + n_2\frac{1}{2^2} + n_3\frac{1}{2^3} + \dots = \sum_1^\infty a_n \frac{1}{2^n} $$

Finding the base two representation amounts to finding all $a_n$ (most of which will be $0$ if the number is "nice"--which most aren't). If we multiply both sides by $2$ then what do we get?

$$ 2x = n_1 + n_2\frac{1}{2^1} + n_3\frac{1}{2^2} + \dots = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n} $$

Since this is base $2$, $a_1$ must be either $0$ or $1$. Which one it is will be obvious once we multiply $x$ by $2$. For example if we want to find $x = 0.3125$:

$$ 2*0.3125 = 0.625 = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n} $$

$a_1 = 0$ because there is no whole part--we still get a decimal so now we are trying to solve a different problem:

Note: if we were already in binary, the number is $0.0101_2$, so multiplying by two simply shifts the digits towards the one's place: $2_{10}\cdot0.\underline{0}101_{2} = 0\underline{0}.101_{2}$--note the underlined digit, $0$, that we found

$$ 0.625 = \sum_1^\infty b_n\frac{1}{2^n} $$

This is the same as the original problem! Now we are trying to find the binary representation of $0.625$ (this will give the $b_n$'s). But we need to keep in mind that the $b_n$'s represent $a_{n+1}$ from the original problem! So we recurse:

$$ 2*0.625 = 1.25 = b_1 + \sum_1^\infty b_{n+1}\frac{1}{2^n} \rightarrow b_1 = a_2 = 1 \\ 0.25 = \sum_1^\infty b_{n+1}\frac{1}{2^n} = \sum_1^\infty c_{n}\frac{1}{2^n} \\ 2*0.25 = 0.5 = c_1 + \sum_1^\infty c_{n+1}\frac{1}{2^n} \rightarrow c_1 = b_2 = a_3 = 0 \\ 0.5 = \sum_1^\infty c_{n+1}\frac{1}{2^n} = \sum_1^\infty d_{n}\frac{1}{2^n} \\ 2*0.5 = 1 = d_1 + \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_1 = c_2 = b_3 = a_4 = 1 \\ 0 = \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_{n > 1} = c_{n > 2} = b_{n > 3} = a_{n > 4} = 0 $$

So this gives: $0.3125_{10} = 0.0101000\dots_{2}$ or just $0.0101_2$ (which indeed is $0.3125 = \frac{5}{16} = \frac{1}{4} + \frac{1}{16}$).

Converting Integers

Now let's look at converting integers to binary it's essentially the same thing except now you don't have powers of $\frac{1}{2}$, you have powers of $2$:

$$ x = a_0 + a_1*2 + a_2*2^2 + a_3*2^3 + \dots = \sum_0^\infty a_n*2^n = a_0 + \sum_1^\infty a_n*2^n = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n $$

Hopefully that shows why we should divide by $2$. When we divide by $2$ what we are really doing is writing $x = 2\alpha + \beta$, plug that in:

$$ x = 2\alpha_0 + \beta_0 = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n $$

Clearly $a_0 = \beta_0$ and $\alpha_0 = \sum_0^\infty a_{n + 1}*2^n$. So again, we recurse:

$$ \alpha_0 = 2\alpha_1 + \beta_1 = a_1 + 2\sum_0^\infty a_{n + 2}*2^n \rightarrow a_1 = \beta_1 \\ \alpha_1 = 2\alpha_2 + \beta_2 = a_2 + 2*\sum_0^\infty a_{n + 3}*2^n \rightarrow a_2 = \beta_2 \\ \dots $$

So, for instance, we can do $x = 45$:

$$ 45 = 2*22 + 1 \rightarrow a_0 = 1\\ 22 = 2*11 + 0 \rightarrow a_1 = 0\\ 11 = 2*5 + 1 \rightarrow a_2 = 1\\ 5 = 2*2 + 1 \rightarrow a_3 = 1\\ 2 = 2*1 + 0 \rightarrow a_4 = 0\\ 1 = 2*0 + 1 \rightarrow a_5 = 1\\ 0 = 2*0 + 0 \rightarrow a_6 = 0 \\ \dots \\ \text{it repeats--these are the zeros to the left of the integer} $$

So this gives $45_{10} = 0\dots000101101_2$ or just $101101_2$. The way we recursed suggests that we could write:

\begin{align} 45 = & 2*22 + 1 \\ =& 2*\left(2*11 + 0\right) + 1\\ =& 2*\left(2*\left(2*5 + 1\right) + 0\right) + 1\\ =& 2*\left(2*\left(2*\left(2*2 + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*1 + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =&\dots \end{align}

The reason that you divide to get the integer value and multiply to get the fractional value is because you are moving the digits towards the one's place: $2^0$. When the digits are to the left of the decimal (integers) you need to divide by $2$ to move them towards $2^0$ and when the digits are to the right of the decimal (fractions) then you need to multiply by $2$ to bring the digits closer to $2^0$.

Another example: base $3$

Let's say we want to find $45_{10}$ in base $3$. It's the same procedure--divide by $3$:

\begin{align} 45 =& 3*15 + 0 \\ =& 3*\left(3*5 + 0\right) + 0 \\ =& 3*\left(3*\left(3*1 + 2\right) + 0\right) + 0 \\ =& 3*\left(3*\left(3*\left(3*0 + 1\right) + 2\right) + 0\right) + 0 \\ =& 3*\left(3*\left(3*\left(3*\left(3*0 + 0\right) + 1\right) + 2\right) + 0\right) + 0 \\ \end{align}

So now that we are starting to get $0$'s, we know that $45_{10} = 0\dots001200_3 = 1200_3 = 1*3^3 + 2*3^2 = 27 + 18 = 45$

I should probably add

This is part of why we can represent any number as:

$$ x = \sum\limits_{i = -\infty}^{i = +\infty}a_in^i $$

where all $a_i < n$

Answer 2

To represent a rational number $a$ as binary means to write it in the form $$d_n2^n + d_{n-1}2^{n-1} + \ldots + d_02^0 + d_{-1}2^{-1} + \ldots$$ where each of the $d_i$ is either $0$ or $1$. For example, the number $5\frac34$ can be represented as $$\color{darkblue}{1}\cdot 2^2 + \color{darkblue}{0}\cdot 2^1 + \color{darkblue}{1}\cdot 2^0 + \color{darkred}{1}\cdot 2^{-1}+ \color{darkred}{1}\cdot 2^{-2}$$ and we usually abbreviate this to just $$\color{darkblue}{101}.\color{darkred}{11}$$

Note that this does not say anything about how to actually find the digits $d_i$; that is a separate matter. It also does not say anything about how the original number $q$ is represented itself; it could be in decimal or it could be in Roman numerals. it doesn't matter; as long as you can do arithmetic with it and somehow compute the correct set of $d_i$, you have converted the number to binary.

Integers

Suppose we have some integer $q$ and we would like to find the correct set of $d_i$ to represent the number in binary. One algorithm we might use is as follows: We want to write $$q = d_n2^n + d_{n-1}2^{n-1} + \ldots + d_12^1 + d_02^0 \tag{1}$$

and it should be clear that every one of the terms on the right-hand side is even, except possibly the $d_02^0$ term. So if $q$ is even, we must have $d_0=0$, and if $q$ is odd, we must have $d_0=1$. Then $q-d_0$ is even, and $\frac12(q-d_0)$ is a smaller integer. We can write

$$q-d_0 = d_n2^n + d_{n-1}2^{n-1} + \ldots + d_12^1$$

and dividing by 2 we get:

$$q' = \frac12(q-d_0) = d_n2^{n-1} + d_{n-1}2^{n-2} + \ldots + d_12^0.\tag{2}$$

The right-hand expression is in the same form as $(1)$, so is the exact binary expansion of the smaller integer $\frac12(q-d_0)$, which we can call $q'$. Comparing $(1)$ and $(2)$, we see that the binary digits of $q'$ are the same as those of $q$, but with the rightmost one, $d_0$, dropped from the end. So if we could find the binary digits of $q'$, they would be $d_nd_n-1\ldots d_1$ and we could simply append $d_0$ to the end to get the digits of $q$.

Example: $11$

To compute the binary expansion of $q=11$ we first check that $11$ is odd, so $d_0 = 1$, and then calculate $q' = \frac12(11-1) = 5$. The binary expansion of $11$ will be the same as the expansion of $5$, with an extra $1$ on the end.

Repeating the process, we now want to calculate the binary expansion of $q'=5$. This is odd, so $d_1 = 1$ and we take $q'' = \frac12(5-1) = 2$. Then $q''$ is even, so $d_2$ is $0$, and $q''' = \frac12(2-0) = 1$, which is odd so $d_3 = 1$ and $q'''' = \frac12(1-1) = 0$ and we stop. The binary representation of $11$ is $d_3d_2d_1d_0 = 1011$.

Integers with fractions

Suppose we have $$q = d_n2^n + d_{n-1}2^{n-1} + \ldots + d_12^1 + d_02^0 + d_{-1}2^{-1} + \ldots \tag{1}$$

We will work from the left instead of from the right this time.

The sum of the terms except for the first is $d_{n-1}2^{n-1} + \ldots + d_12^1 + d_02^0$ and can be shown to be strictly less than $2^n$. (There is actually an interesting exception to this that we will disregard to keep the discussion simple.) So $d_n=1$ if and only if $q \ge 2^n$, and conversely $d_n=0$ if and only if $q < 2^n$. So we can determine $d_n$ easily just by comparing $q$ with $2^n$.

Having done so, we can calculate $$q' = q - d_n2^n = d_{n-1}2^{n-1} + \ldots + d_12^1 + d_02^0 + d_{-1}2^{-1} + \ldots$$ and repeat the process for $q'$.

Example: $\frac52$

Let's consider the number $q=\frac52$. We guess that $n=3$ and find that $q<2^3=8$, so $d_3 = 0$. We then subtract $d_32^3 = 0$ from $q$ to obtain $q' = \frac52$ and continue. $q'\lt2^2$ so $d_2 = 0$ and $q'' = q' - 0\cdot2^2 = \frac52$ again. But on the next step something more interesting happens: $q'' \ge 2^1$ so $d_1 = 1$ and $q''' = q'' - 1\cdot 2^1 = \frac12$.

Then $q''' < 2^0$ so $d_0 = 0$ and $q^{iv} = q''' - 0\cdot2^0 = \frac12$ again. And $q^{iv} \ge 2^{-1}$ so $d_{-1} = 1$ and $q^v = q^{iv} - 1\cdot2^{-1} = 0$. $q^v=0$, so we can stop. We have calculated that $(d_3, d_2, d_1, d_0, d_{-1}) = (0,0,1,0,1)$, so the binary expansion of $\frac52$ is $0010.1$; we usually drop the leading zeroes and just write $10.1$.

Instead of stopping, we could continue for as many steps as we wanted, calculating more $d_i$, but it is clear that since $q^v=0$, all the following $d_i$ would also be $0$. So we can also say that $10.1000000000000000$ is a binary representation of $\frac52$. This is also correct; binary expansions, like decimal expansions, are not quite unique.

Note that there was no need to have the $\frac52$ written as an ordinary decimal; the only important thing was that we could compare it with the various $2^i$ and that we could do arithmetic on it. if you need it to be decimal to do those things, then yes, you need it to be decimal. But that it a contingent fact about your knowledge of how to calculate, not anything that is required by the algorithm itself. The algorithm finds a binary representation of a number, not of a decimal numeral.

Numbers less than 1

Suppose our number $q$ is between 0 and 1, so that the $d_i$ are all zero when $i\ge 0$. That is, $$q = d_{-1}2^{-1} + d_{-2}2^{-2} + \ldots.$$

Here we could proceed exactly as in the previous section, checking to see if $q\ge 2^{-1}$, then if the remainder $q'\ge 2^{-2}$, and so on.

But we can simplify the arithmetic a little bit. Instead of testing $q\ge\frac12$, we do the equivalent check to see if $2q\ge 1$. If it is, then $d_0 = 1$, and if not then $d_0 = 0$. Algebraically, we would write: $$2q = d_{-1}2^{0} + d_{-2}2^{-1} + \ldots$$ and then $d_{-1} = 1$ if and only if $2q\ge 1$. Having found $d_{-1}$, we can as usual subtract it (from $2q$ this time) and continue checking the remainder $2q-d_{-1}$, using the same method.

Example: $\frac13$

For example, let us find the binary expansion of $q=\frac13$. We see that $2q = \frac23 < 1$, so $d_{-1} = 0$, and $q' = 2q - d_{-1} = \frac23$. Then repeating the process we find $2q' = \frac43 \ge 1,$ so $d_{-2} = 1$ and we calculate $q''= 2q'- d_{-2} = \frac13$. At this point we recognize that we are in a loop and the same calculations will keep producing $0$ and then $1$ over and over. Or put another way, the binary expansion of $q$ starts with a $0$, followed by the binary expansion of $q'$, which starts with a 1 and is followed by the binary expansion of $q$ again. So the complete expansion for $\frac13$ is $.0101010101\ldots$.

Example: $\frac\pi4$

We can apply the same technique for an irrational number, say $q=\frac\pi4$:

$$ \def\no{\text{no}} \def\yes{\text{yes}} \begin{array}{ccc} q & q \ge 1? & d_i \\\hline \frac\pi4 & \no & 0 \\ \frac\pi2 & \yes & 1 \\ \pi-2 & \yes & 1 \\ 2\pi-6 & \no & 0 \\ 4\pi-12 & \no & 0 \\ 8\pi-24 & \yes & 1 \\ 16\pi-50 & \no & 0 \\ \end{array} $$

So the binary expansion of $\frac\pi4$ begins $0.110010$ and continues from there. Notice that again we did not have to represent any of the input numbers in decimal, unless perhaps we needed to do so in order to calculate whether each one was bigger or smaller than 1. (Maybe you use decimal, but I ask the computer, which uses base 256 arithmetic; there is no decimal number anywhere to be seen.)

The only difference between handling a rational and an irrational number is that the procedure will eventually repeat, when applied to a rational number, and if we detect this we can cut if off early. When applied to an irrational number, the procedure will never repeat.

Summary

Each one of these methods starts from the same place: the formula $(1)$ which defines what it means for a sequence of binary digits to be a binary representation for some number $q$. Each one then manipulates the formulas to show how to calculate the particular set of binary digits for a given $q$.