Calculating the length of a decimal expansion in constant time

81 Views Asked by At

Is there a way to calculate the length of a decimal expansion as a result of a division operation in constant time?

$\frac{1}{256} = 0.00390625$ therefore the expansion length is $8$.

$\frac{1}{357} = 0.002801120448179271708683473389355742296918767507$ therefore the decimal expansion repeats every $48$ places.

Can these be calculated in constant time?

1

There are 1 best solutions below

0
On

Case 1: $n$ has the form $2^{m_2}5^{m_5}$

The decimal expansion of $1/n$ has finitely many figures iff natural number $n$ has no prime divisors other than 2 or 5. (Without loss of generality, we may assume that the expansion does not end in $9999\ldots$ because $0.\bar9=1$ etc.)

Let $\operatorname{ord}_pn$ denote to which order a prime number $p$ divides $n$. Then:

$1/n$ in decimal expansion has exactly $d(n) = \max(\operatorname{ord}_2n, \operatorname{ord}_5n)$ decimal places after the decimal point.

For example, $1/800 = 0.00125$ has 5 figures because 2 divides to order 5 and 5 divides to order 2, and $5 = max(5,2)$.

Lets assume that we have $n$ represented in some binary form, i.e. in some base which is a power of two. Then computing $\operatorname{ord}_2$ can be performed by counting the trailing zero bits. This costs up to $\log_2 n$ operations (and even more because to count the zero-bits, you need a variable which might require up to $\log_2\log_2 n$ bits, thus costs $\log_2 n\cdot \log_2 \log_2 n$.

To determine the order of 5 assume using trial division which can be done fast as 5 is small, but requires to look at all digits of $n$. The result is a number of order $n/5$, then $n/5^2$ etc. Hence if $n$ is of order $10^k$, the costs are for $k$ digits, then $k-\log_{10}5$ digits, then $k-2\log_{10}5$ etc, which is of order $k^2$, thus costs order of $\log_{10}^2(n)$.

Case 2: $\gcd(n,10) = 1$

For the periodic case, you have to find the smallest natural number $m$ such that $n\mid 10^m-1$. Then $m$ is the period.

For example, $7\mid 999999$ such that $m=6$ for $1/7$ because no smaller $m$ does. And in fact, $1/7=0.\bar142857$.

No idea how to compute that efficiently. The condition means that $10^m=1\bmod n$. You would factor $n$ into its prime decomposition to determine Euler's totient $\varphi(n)$, because you know that

$$ 10^{\varphi(n)} =1 \bmod n $$ Then divide out prime factors of $\varphi(n)$ from the exponent to find a minimal $m\mid \varphi(n)$ such that $10^m=1\bmod n$.

This costs at least a factorization of $n$ (and one of $\varphi(n)$ which has same costs). So this is going to be expensive when you want to determine the period of $1/n$ for a number with, say, 100 digits.

Case 3: General Case

Left to you, but presumably it won't be cheaper than case 2... Thus at least sub-exponential due to factorization of $n$.

Example: $n=357$

$n=357$ is case 2 and factors as $n=3\cdot7\cdot17$, hence

$$ \varphi(n) = 2\cdot6\cdot16 = 192 = 2^6\cdot3 $$ and thus the period divides 192. According to Fermat's little theorem, $10^{192} = 1 \bmod 357$.

Now $10^{\varphi/3}=256\bmod357$, therefore we must keep factor 3 and the period has a prime factor of 3. Then compute the power to which 2 may be divided out of $\varphi$:

$10^{\varphi/2^1}=1\bmod 357$

$10^{\varphi/2^2}=1\bmod 357$

$10^{\varphi/2^3}=169 \bmod 357$

Thus

  • The maximal power of 2 that can be divided out of $\varphi$ is $2^2$.

  • The maximal power of 3 that can be divided out of $\varphi$ is $3^0$.

Hence, the period of $1/357$ is $\varphi/(2^2\cdot3^0) = 192/2^2 = 48$.