Repeating period in binary conversion

Question

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?

Answer 1

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

Answer 2

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 $