Why does my algorithm for converting fractional decimal to binary does not work?

Question

For example, to convert $0.25$ to binary. Using this algorithm it gives the correct result $0.01$:

1. Multiply by two
2. take decimal as the digit
3. take the fraction as the starting point for the next step
4. repeat until you either get to 0 or a periodic number
5. read the number starting from the top - the first result is the first digit after the comma

Trying to understand why all this with the multiplying by two actually works, I do this: $$0.25=0.01=\frac{1}{2}(0+\frac{1}{2}(1+\frac{1}{2}*0))$$ So, the multiplying by two comes from dividing by $\frac{1}{2}$. But when I do the multiplying by two I cannot get the numbers in the brackets. This is what I get: $$0.25=0.5*\frac{1}{2}+0$$$$0.5=1*\frac{1}{2}+0$$$$1=2*\frac{1}{2}+0$$Can someone show me how to do that or point me if I make a mistake somewhere?

Answer 1

Cosider that $0 < x < 1$ and in base $10$, $x = 0.abcde....$ and in base $2$ $x = 0.uvwz......$ and let $2x = h.ijklmn.....$

Now $x \ge \frac 12 \iff a \ge 5\iff 2x \ge 1 \iff u = 1 \iff h = 1$.

And $x < \frac 12 \iff a < 5\iff 2x < 1 \iff u= 0 \iff h=0$.

So $u = h$ and that is why you can do this for the first decimal.

Now we get rid of the first digit $h$ (you weren't do doing that) and we let $y = 0.ijklm...$

Now if $x \ge \frac 12$ then $y = 0.ijklmn....2*(x -\frac 12)$. And if $x < \frac 12$ then $y = 0.ijklmn = 2*x$ and $0 \le y < 1$. Let $x' = x - \frac 12$ if $x \ge \frac 12$ or let $x' = x$ if $x < \frac 12$. Either way, $y = 2x'$.

And now let $2y = \alpha.\beta\gamma....$

Now $x' \ge \frac 14 \iff y \ge \frac 12 \iff 2y \ge 1 \iff i \ge 5 \iff v = 1\iff \alpha = 1$. And this is only if $\frac 14 \le x < \frac 12$ or $\frac 34 \le x < 1$

And $x < \frac 14 \iff y < \frac 12 \iff 2y < 1 \iff i < 5 \iff v=0 \iff \alpha =0$. And this is only if $0 < x < \frac 14$ or $\frac 12 \le x < \frac 34$.

Either way $\alpha = v$ and that is why we can get the second digit.

Inductively we can carry that on forever (or until we hit $0$).

==== old=====

There are two things you are supposed to keep track of the binary decimal, which starts at $0.$ and the base $10$ decimal.

Watch:

A: $0. = 0$ B: $0.25$.

Multiply the B by 2:

A: $0. = 0$ B: $0.5 $

Take the digit from B and put it on A: The digit is $0$.

A: $0.0 = 0$ B: $0.5$ (that doesn't look like much but the A has gotten one digit longer)

Take the fraction left in A as your new starting point of A. The fraction part is $0.5$.

A: $0.0 = 0$ B: $0.5$.

Multiple by 2:

A: $0.0 = 0$ B: $1.0$

Take the digit from B and put it on A: The digit is $1$.

A: $0.01 = \frac 14$ B: $0.0$ (But this time the $1$ goes from the $B$ to the $A$. And notice the B is reduced).

Take the fraction left in A as your new starting point of A. The fraction part is $.0$.

A: $0.01 = \frac 14$ B:$0.0$.

3)repeat until you either get to 0 or a periodic number.

We've reached $0$. We are done.

Let's do a more illuminating example:

A: $0.$ B: $0.375$

A: $0.$ B: $0.75$ (Double the B)

A: $0.0$ B: $0.75$ (Move the $0$ to the A)

A: $0.0$ B: $1.50$(Double the B).

A: $0.01$ B: $.50$(Move the $0$ to the A)

A: $0.01$ B: $1.0$(Double the B)

A: $0.011$ B: $.0$.(Move the $1$ to the A)

We've reached zero so we stop.

Basically with have $0.375 = 0.375$

$0.75 = 0.375*2 = 0.375*2 - 0$

$1.5 = 0.375*4 - 0*2$

$.5 = 0.375*4 - 0*2 - 1$

$1.0 = 0.375*8 - 0*4 - 1*2$

$.0 = 0.375*8-0*4 - 1*2 - 1$

So $0.375*8 = 0*4 + 1*2 + 1$

$0.375 = \frac {0*4 + 1*2+1}{8} = \frac 02 + \frac 14 + \frac 18$.

This works because way place a $1$ on the decimal if and only if what we have left is greater than $\frac 12$. But the important part is if it is we then remove that half and have double what is left.

"Trying to understand why all this with the multiplying by two actually works, I do this: "

$0.25=0.01=\frac{1}{2}(0+\frac{1}{2}(1+\frac{1}{2}*0))$

Nothing wrong with that.

$0.375 = 0.011 = \frac 12(0 +\frac 12(1 + \frac 12(1)))$

Answer 2

The following is the algorithm I think you described. Step 2 seemed unclear to me, so I have rephrased it below.

Start with $0.25_\mathrm{ten}$ (the subscript reminds us which base the number is in). To start out with, the binary number is $0_\mathrm{two}.$

1. Multiply by two

Now you have $0.5_\mathrm{ten}.$

2. take [the ones digit] as the [next] digit [of the result]

The ones digit of $0.5_\mathrm{ten}$ is $0.$ The first digit of the result is therefore $0.$

3. take the fraction as the starting point for the next step

The fractional part of $0.5_\mathrm{ten}$ is $0.5_\mathrm{ten}.$

4. repeat until you either get to 0 or a periodic number

So, step 1 again, you had $0.5_\mathrm{ten}$ from the previous step, multiplied by two gives you $1.0_\mathrm{ten}.$

Step 2 again, the ones digit of $1.0_\mathrm{ten}$ is $1.$ The next digit of the result is therefore $1.$

Step 3 again, the fractional part of $1.0_\mathrm{ten}$ is $0.$

But now we have gotten a $0,$ so we stop repeating.

5. read the number starting from the top - the first result is the first digit after the [decimal point]

The first time we did step 2 the result was $0,$ so the first digit after the decimal point is $0.$ The next result was $1,$ so the next digit is $1.$ Therefore: $$ 0.25_\mathrm{ten} = .01_\mathrm{two}.$$

---

To put it another way, you start with this: $$0.25_\mathrm{ten} = \tfrac14 = 0 + \tfrac12(0+\tfrac12(1+\tfrac12(0 + \cdots))).$$ Discard the integer part (which is zero in this example, initially): $$ \tfrac14 = \tfrac12(0+\tfrac12(1+\tfrac12(0 + \cdots))).$$

Multiply by two: $$ \tfrac12 = 0+\tfrac12(1+\tfrac12(0 + \cdots)).$$ The integer part, $0,$ is a digit of your output. Discard it from the input: $$ \tfrac12 = \tfrac12(1+\tfrac12(0 + \cdots)).$$

Multiply by two: $$ 1 = 1+\tfrac12(0 + \cdots).$$ The integer part, $1,$ is a digit of your output. Discard it from the input: $$ 0 = \tfrac12(0 + \cdots).$$

And now we see that continuing will just produce $0$ again and again, so the non-zero output is just $.01_\mathrm{two}.$

---

As for why this works, it's because every time you multiply a number by $2,$ you shift its binary representation one digit to the left, so one by one the fractional binary digits move into the ones place. And it works no matter what base the input is written in, or even if the input is not written as a base-$b$ fraction at all, because a number is the same number no matter how you write it. We double the input, the integer part of the input gives us a binary digit, we remove that integer part from the input and double the remaining fractional part, we get another binary digit, etc.

Let's try it with $\frac13$ written in various formats: base two, base ten, and an exact rational number. We take the input; we double it, then split the doubled number into an integer part and a fractional part; the integer part becomes output and the fractional part becomes input for the next cycle of doubling, integer part, fractional part. $$ \begin{array}{lllllllll} \mathbf{step} &\ & \mathbf{binary} &\ & \mathbf{decimal} &\ & \mathbf{rational} &\ & \mathbf{output} \\ \mathrm{input} && 0.010101\ldots && 0.33333\ldots && \frac13 \\ \mathrm{double} && 0.101010\ldots && 0.66666\ldots && \frac23 \\ \mathrm{integer\ part} && 0 && 0 && 0 && 0 \\ \mathrm{fractional\ part} && 0.101010\ldots && 0.66666\ldots && \frac23 \\ \mathrm{double} && 1.010101\ldots && 1.33333\ldots && \frac43 = 1+\frac13 \\ \mathrm{integer\ part} && 1 && 1 && 1 && 1 \\ \mathrm{fractional\ part} && 0.010101\ldots && 0.33333\ldots && \frac13 \\ \end{array} $$ So the first two digits are $0,$ then $1,$ and after taking the fractional part on the last line we see we have the same thing we started with, so the cycle repeats $0, 1, 0, 1,$ as long as we follow the algorithm.

In all three input columns (binary, decimal, rational) we are simply doing numeric operations on numbers, but we can see from the binary column that indeed these operations are picking off the digits of the binary representation one at a time. No matter what format you use for the input, it's always the same sequence of digits in the output, so you convert the input (whatever it is) to the digits of its binary representation.

Answer 3

Long division works in any base. If you pay attention, you can spot the periodicities in the expansion. So sharpen your Miss Wormwood pencil and check it out.

Example: I will obtain the binary expansion of 1/3 this way.

0.010 ----------------- 11 ) 1.00000000000 11 --- 100 11 ---- 1 You can see that the binary expansion of $1/3$ is $.0101010101010....$