# Decimal to Fixed Point Conversion

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.

• 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. – D.W. Feb 3 '17 at 22:44
• This seems somewhat more appropriate for math.se. – Yuval Filmus Feb 3 '17 at 22:53

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.

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$.