0
$\begingroup$

I am having trouble to get the intuition behind the following approach: We take the fraction point (say: .642) and continuously multiply by 2, taking whatever ends up right of the point as our next number (either 0 or 1) after the fixed point in the binary number. Then we take whatever is left after the decimal point and repeat.

$\endgroup$
  • 2
    $\begingroup$ Have you tried working through an example to see what happens? I'd suggest picking a simpler number: say, 0.75, or something like that. And then try a few more examples and see if you can start to spot a pattern. $\endgroup$ – D.W. Feb 3 '17 at 22:44
  • $\begingroup$ This seems somewhat more appropriate for math.se. $\endgroup$ – Yuval Filmus Feb 3 '17 at 22:53
2
$\begingroup$

Let $x$ be the real number you wish to convert. We will assume without loss of generality that $0 \le x < 1$. Form the Dedekind-completeness of the order on $\mathbb{R}$, it follows that $x$ can be (almost) uniquely written as

$$ x = \sum_{h=1}^{\infty} 2^{-h} \alpha_h $$

where $a_h \in \{ 0, 1\}$ for all $h$. Now observe that:

$$ 2x = \sum_{h=1}^{\infty} 2^{-h+1} \alpha_h = \alpha_1 +\sum_{h=1}^{\infty} 2^{-h} \alpha_{h+1} $$

where the rightmost sum is nonnegative and less than $1$. Multiplying by $2$, therefore, allowed us to discover a single binary digit of $x$, namely $\alpha_1$. The same procedure can be iterated to yield as many digits as you wish.

$\endgroup$
0
$\begingroup$

Complementing quicksort's answer.

Your implementation will take a decimal number and convert to it's $(0.d_0d_1\ldots d_n \ldots)_2$ binary representation. Your example would work like this:

Step 1: \begin{align*} x_0 &= 0.624\\ 2 \times x_0 &= 1.284 \end{align*} Is $2 \times x_0 \geq 1$? If so, $d_0 = 1$, otherwise $d_0 = 0$.

Step 2: \begin{align*} x_{1} &= 2\times x_0 - d_0\\ x_1 &= 0.284\\ 2 \times x_1 &= 0.568 \end{align*} Is $2 \times x_1 \geq 1$? If so, $d_1 = 1$, otherwise $d_1 = 0$.

Step 3: \begin{align*} x_{2} &= 2\times x_1 - d_1\\ x_2 &= 0.568\\ 2 \times x_2 &= 1.136 \end{align*} Is $2 \times x_2 \geq 1$? If so, $d_2 = 1$, otherwise $d_2 = 0$.

And so on...

As you can see this looks like a loop, you may want to try to implement it in your favorite programming language. Notice, however, that some finite decimal representations may have infinite representation in binary.

$\endgroup$

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.