0
$\begingroup$

I have the number 0.625. If I need to convert it into binary form, I can multiply by two:

0.625 * 2 = 1.25 / 1
0.25 * 2 = 0.5 / 0
0.5 * 2 = 1.0 / 1

So the result is 0.62510=0.1012

I'm trying to understand how this algorithm works. The initial form is: $$ x_1\cdot2^{-1} + x_2\cdot2^{-2} + x_3\cdot2^{-3} = 0.625 $$ I can factor out 2-1, so the I'll have: $$ 2^{-1}\cdot(x_1\cdot2^0 + x_2\cdot2^{-1} + x_3\cdot2^{-2}) = 0.625 $$ From here: $$ x_1\cdot2^0 + x_2\cdot2^{-1} + x_3\cdot2^{-2} = 1.25 $$ Now, what logic should I use to tell that x1 is 1 here?

$\endgroup$
  • $\begingroup$ Think of running the algorithm on a binary fraction. It obviously works then! $\endgroup$ – almagest May 12 '16 at 9:29
  • $\begingroup$ @almagest, sorry, didn't understand your comment. Do you mind clarifying? $\endgroup$ – Max Koretskyi May 12 '16 at 10:26
  • $\begingroup$ If you take a binary fraction like $0.101$, the repeatedly multiplying by 2 in the same way as for the fraction $0.625$ generates $1,0,1$. $\endgroup$ – almagest May 12 '16 at 10:33
  • $\begingroup$ yeah, thanks, my question was specifically about understing why x1 equals to 1 in the equation $\endgroup$ – Max Koretskyi May 12 '16 at 10:35
1
$\begingroup$

You know all of the $x_i$s are either $0$ or $1$. You also, hopefully know that the infinite sum $$ (2^{-1} + 2^{-2} + 2^{-3} + \cdots) = 1 $$ so in your final equation we have $$ x_1\cdot 2^0 + \underbrace{x_2\cdot 2^{-1}+x_3\cdot 2^{-2}}_{\text{ at most }1} = 1.25 $$ Since the right-hand side is larger than $1$, the $x_1\cdot 2^0$ term must be nonzero -- and the only way to do that when $x_1$ is either $0$ or $1$ is to make $x_1=1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ great, thanks, that's a good explanation. Do you know if that's what defines the algorithm? Or maybe there are other better explanations? $\endgroup$ – Max Koretskyi May 12 '16 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.