# Repeating period in binary conversion

A common algorithm for converting a decimal number that is between 0 and 1 to binary is to multiply by 2 and record the integer part of the result. Then, you subtract that integer from the result and repeat the process.

Example = $${0.1}_{10} = \frac{1}{10}$$

Result = $${0.0 0011 0011 0011...}_2$$

Is there any simple way to tell the maximum repeating period of a binary fraction obtained using that conversion algorithm?

A number that has a finite decimal notation with $k$ digits after the decimal point is a fraction with denominator $10^k$. Multiplying by $2$ $k$ times cancels the $k$ factors of $2$ and makes the denominator $5^k$. The period of the repeating $b$-ary representation of a fraction with denominator $d$ is the order of $b$ modulo $d$. Since $2$ is a primitive root modulo $5$, and if $b$ is a primitive root modulo $p$ then it is a primite root modulo all powers $p^k$ unless $b^{p-1}\equiv1\bmod p^2$ (I don't know how to prove that, I just found it on Wikipedia), $2$ is a primitive root modulo $5^k$ for all $k$, so its order modulo $5^k$ is $\phi\left(5^k\right)$, where $\phi$ is Euler's totient function that counts the number of numbers coprime to its argument. Since $\phi\left(5^k\right)=4\cdot5^{k-1}$, a number that has a finite decimal notation with $k$ digits after the decimal point has period $4\cdot5^{k-1}$ in binary notation. In your example, $k=1$ and the period is $4\cdot5^{1-1}=4$.

• Thanks, @joriki. I had a worse bound, $10^k$ which was from just watching the multiplications and keeping track of the remainders. There were k digits in the original fraction, and there could not be more than k in the repeated multiplications. There are $10^k$ permutations of those digits.
– Jim
Jun 1, 2016 at 13:51

It is possible by checking the denominator of input decimal fraction $${0.1}_{10} = \frac{1}{10}$$

Here denominator is $$10 = 2*5 = 2^1*5 = 2^t*q$$

so

• preperiod t = 1
• period = $$\phi(q) = \phi(5) = 4$$

Here $$phi$$ is Euler's totient function

One can check that:

$${0.1}_{10} = {0.0(0011)}_2$$