3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Jim
    Jun 1, 2016 at 13:51
0
$\begingroup$

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 $

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .