How many digits does a given fraction have in decimal form?

Question

This question came to me when considering implementing my own bignum library (more formally called an arbitrary-precision arithmetic library), while considering memory and cpu optimizations. If one can programmatically determine the number of digits which the result of some operation will have, then they can allocate the required space without having to clean up unused memory after the fact, thus using less overall memory and time. Anyway, my use for the question has little to do with the question itself, so I'll move on.

My question is relatively simple. Given some number $\frac ab$ where $a$ and $b$ are integers, can we determine the number of digits that number will have, or, in the case of repeating decimals, the number of digits after just one period or repetition? And, more useful in my case, can we do this for an arbitrary base/radix, say base $\beta$?

Answer 1

The decimal for a rational number $\frac ab$ ($\gcd(a,b)=1$) is terminating or recurring, and any terminating recurring decimal is equal to a rational number. If $b=2^e\cdot 5^f$, and $\max\{e,f\}=m$, then the decimal terminates after $m$ digits. If $b=2^e\cdot 5^f\cdot B$, where $B>1$, $\gcd(B,10)=1$, and $n$ is the order of $10\pmod B$, then the decimal contains $m$ non-recurring and $n$ recurring digits.

For base $\beta$, write $b=uB$ with $B$ the greates divisor of $b$ prime with $\beta$. Let $m$ be the smallest power of $\beta$ such that $u\mid \beta^m$ and $n$ be the order of $\beta$ modulo $B$. Then the base $\beta$ expansion of $\frac ab$ contains $m$ non-recurring and $n$ recurring digits.

Let $a,b$ be positive integers, $\gcd(a,b)=1$, $\beta$ be a base $\beta\geq 2$.

If $b$ divides a power of $\beta$, then $\frac ab$ has terminatig $\beta$-expansion. More precilsey, if $\beta^m=ub$ then $$\frac ab=\frac{au}{\beta^m}=q+\frac r{\beta^m}$$ with non-negative integers $r,q$, $r<\beta^m$ and $\frac r{\beta^m}$ has $\beta$-expansion with at most $m$ digits. If $m$ is the small power, then $\frac r{\beta^m}$ has $\beta$-expansion with exactly $m$ digits.

Now let $B>1$ the greatest divisor of $b$ prime with $\beta$ and let $b=uB$. Then $u$ divides a power of $\beta$, say $\beta^m=uv$. Let $n$ be the order of $\beta$ modulo $B$ so that $\beta^n-1=wB$. Then $$\frac ab=\frac{avw}{\beta^m(\beta^n-1)}$$ Consider $$\frac{avw}{\beta^n-1}=q+\frac r{\beta^n-1}$$ with $q,r$ non-negative integers and $r<\beta^n-1$. Then $\frac r{\beta^n-1}$ has recurring $\beta$-expansion with $n$ digits. For $r=\sum_{i=1}^n d_i\beta^{n-i}$ with digits $d_i$ (that's $0\leq d_i<\beta$), hence \begin{align*} \frac r{\beta^n-1} &=\frac 1{\beta^n-1}\sum_{i=1}^n d_i\beta^{n-i}\\ &=\frac 1{1-\beta^{-n}}\sum_{i=1}^n d_i\beta^{-i}\\ &=\sum_{j=0}^{+\infty}\beta^{-jn}\sum_{i=1}^n d_i\beta^{-i}\\ &=\sum_{j=0}^{+\infty}\sum_{i=1}^n d_i\beta^{-i-jn} \end{align*} which gives the required recuring $\beta$-expansion. The division by $\beta^m$ gives $m$ non-reccuring digits, thus proving our assertion.