Maximum number of fractional decimal digits required for exact division

elementary-number-theoryrational numbers

I am interested in understanding the maximum number of fractional decimal digits required for exact division.

The Java BigDecimal implementation states (and implements):

If the quotient this/divisor has a terminating decimal
expansion, the expansion can have no more than
(a.precision() + ceil(10*b.precision)/3)
digits.

There is a typo/parenthesis error in the Java BigDecimal source comment.
It should read

(a.precision() + ceil(10*b.precision/3))

In this context precision is used as in computer representations of floating point numbers (e.g. IEEE Standard for Floating-Point Arithmetic 754-2008). It can be thought of as the number of digits in the significand/coefficient/mantissa s when a terminating decimal is written in base 10 scientific notation s * 10e where s has been normalized to remove all leading and trailing zeros.

Here is a snippet of the code in question:

            /*
             * If the quotient this/divisor has a terminating decimal
             * expansion, the expansion can have no more than
             * (a.precision() + ceil(10*b.precision)/3) digits.
             * Therefore, create a MathContext object with this
             * precision and do a divide with the UNNECESSARY rounding
             * mode.
             */
            MathContext mc = new MathContext( (int)Math.min(this.precision() +
                                                            (long)Math.ceil(10.0*divisor.precision()/3.0),
                                                            Integer.MAX_VALUE),
                                              RoundingMode.UNNECESSARY);
            BigDecimal quotient;
            try {
                quotient = this.divide(divisor, mc);
            } catch (ArithmeticException e) {
                throw new ArithmeticException("Non-terminating decimal expansion; " +
                                              "no exact representable decimal result.");
            }

This links to the BigDecimal source code:
https://github.com/frohoff/jdk8u-dev-jdk/blob/da0da73ab82ed714dc5be94acd2f0d00fbdfe2e9/src/share/classes/java/math/BigDecimal.java#L1674

I found a reference to Java BigDecimal in the answer provided by @siefca to
How to estimate the number of decimal places required for a division?
but, there is no explanation as to how it is derived.

Q: How is this formula for the maximum number of digits in an exact decimal division derived?

Best Answer

To keep the formulas a little more concise, let $n$ be the precision of the numerator, $d$ the precision of the denominator. The formula in the BigDecimal implementation that bounds the precision of the quotient can then be written $$ n + \left\lceil \frac{10d}{3} \right\rceil.$$

Note that the denominator can be multiplied by a power of $10$ to produce an integer. That integer can have only factors of some power of $2$ and some power of $5$, since otherwise we get a non-terminating decimal fraction, which is an error. Moreover, if we can pair up any factor of $2$ with any factor of $5$, they form a factor of $10,$ which does not contribute to the precision of the number. So the denominator is either $2^x \times 10^y$ or $5^x \times 10^y$ or simply $10^y$ for some positive integer $x$ and some integer $y$. (By allowing $y$ to be negative, we also account for any decimal fraction in the original denominator.)

Denominators of the form $10^y$ lead to quotients with $n$ digits of precision, so that case is dealt with easily.

Now note that each of the $x$ factors of $2$ in $2^x \times 10^y$ or $5$ in $5^x \times 10^y$ adds exactly one digit of precision (and no more) on the right-hand end of the numerator during division:

\begin{align} \frac{9999}{2} &= 4999.5 & \frac{9999}{5} &= 1999.8 \\ \frac{9999}{2^2} &= 2499.75 & \frac{9999}{5^2} &= \phantom{0}399.96 \\ \frac{9999}{2^3} &= 1249.875 & \frac{9999}{5^3} &= \phantom{00}79.992 \end{align}

So an upper bound on the number of digits of the quotient is simply $n + x.$

But the formula assumes we know $d,$ not $x.$ What is the upper bound of $x$ in terms of a known value of $d$? It's simply the exponent of the largest power of either $2$ or $5$ that you can write with $d$ digits of precision. But the exponent of that power of $2$ will always be greater than the exponent of that power of $5$. So the question is really just what power of $2$ can be written with $d$ digits of precision.

In general, for $x > 0,$ to write $2^x$ takes $d = \lceil x\log_{10}(2) \rceil = x\log_{10}(2) + f$ digits, where $0\leq f < 1.$ Solving for $x,$

$$ x = \frac{d - f}{\log_{10}(2)} \leq \frac{d}{\log_{10}(2)} < \frac{d}{0.3} = \frac{10d}{3} \leq \left\lceil\frac{10d}{3} \right\rceil $$ since $\log_{10}(2) > 0.3.$ And so $n + x \leq n + \left\lceil {10d/3} \right\rceil,$ and since $n + x$ is an upper bound on the precision of the quotient, so is $n + \left\lceil {10d/3} \right\rceil.$ That proves the correctness of the formula.

But the formula is not a particularly tight upper bound on the precision of the quotient. There is the substitution of $0.3$ for $\log_{10}$, which hardly ever will make a difference except for very large denominators (and not much difference then). There is also the fact that since $x \leq {d/\log_{10}(2)}$ and $x$ is an integer, by definition $x \leq \left\lfloor {d/\log_{10}(2)} \right\rfloor.$ And since $d/\log_{10}(2)$ is never an integer, that means the formula always gives an answer at least $1$ greater than required. Since $\log_{10}(2) > 0.301,$ a slightly tighter bound would be

$$ n + \left\lfloor \frac{d}{0.301} \right\rfloor.$$

But even that is not what makes the BigDecimal formula such a loose bound. A larger effect is due to the fact that when you repeatedly divide a number by $2,$ every third or fourth division removes one digit of precision from the left side of the number. It turns out that instead of adding $x$ digits of precision to the numerator by dividing it by $2^x,$ we add something more like $0.7 x$ digits of precision.

Another way to think about this is that dividing by $2^x$ is the same as multiplying by $5^x$ and then dividing by $10^x.$ Dividing by $10^x$ doesn't change the precision, but the multiplication by $5^x$ potentially adds as many digits of precision as the precision of $5^x,$ which is $\lceil x\log_{10}(5) \rceil.$ Since $x \leq \left\lfloor {d/\log_{10}(2)} \right\rfloor,$ this means the precision of the quotient can be at most

$$ n + \left\lceil\left\lfloor\frac{d}{\log_{10}(2)}\right\rfloor \log_{10}(5)\right\rceil \leq n + \left\lceil\frac{\log_{10}(5)}{\log_{10}(2)}d \right\rceil \leq n + \left\lceil 2.322 d \right\rceil. $$

So an alternative formulation is that there are at most $n + \left\lceil 2.322 d \right\rceil$ digits in the quotient. This grows slower than the formula that was used.

Related Question