2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Feel free to add/remove tags. I'm not too certain which tags best apply to this.. $\endgroup$ – Steven Fontaine Oct 29 '17 at 5:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I could use some clarification on this bit. "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." Based on my understanding, this says that the number $\frac{1}{97}$ should have around $10\pmod{97} = 10$ recurring digits. However, $\frac{1}{97}$ has a period of 96. In fact, if I understand this correctly, this says that any number greater than 10 will have a period in the order of 10 (in base 10, of course.) Could you clarify this for me? Thanks. :) $\endgroup$ – Steven Fontaine Oct 29 '17 at 10:18
  • 1
    $\begingroup$ In $\frac 1{97}$ you have to compute the order of $10$ modulo $97$, that's the smallest positive integer $n$ such that $10^n\equiv 1\pmod{97}$. $\endgroup$ – Fabio Lucchini Oct 29 '17 at 10:20
  • $\begingroup$ Ah, I see. That terminology was lost on me haha. Thanks. $\endgroup$ – Steven Fontaine Oct 29 '17 at 10:22
  • $\begingroup$ I've just returned to this after a couple busy weeks and I'm looking at the proof. the line $\frac ab=\frac{au}{\beta^m}=q+\frac r{\beta^m}$ confuses me. Why is $\frac ab=\frac{au}{\beta^m}$? Since $b=u\beta^m$ shouldn't $\frac ab=\frac{a}{u\beta^m}$? Thanks in advance. $\endgroup$ – Steven Fontaine Nov 13 '17 at 13:58
  • $\begingroup$ You are right: I edited a mistake in my answer: we have $\beta^m=ub$ for some $u$ because $b$ divides a power of $\beta$. $\endgroup$ – Fabio Lucchini Nov 13 '17 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.