[Math] How to estimate the number of decimal places required for a division

rational numbers

Given two decimal numbers, is it possible to estimate the number of decimal places required to fit the result of their division? Provided that the division yields a finite number of decimals, of course.

For example:

  • 1234.5678 / 2 = 617.2839, 4 decimal places required
  • 1234.5678 / 4 = 308.64195, 5 decimal places required
  • 1234.5678 / 8 = 154.320975, 6 decimal places required
  • 1234.5678 / 6.4 = 192.90121875, 8 decimal places required

By estimate, I don't necessarily need the exact number of decimals in the result, but a number of decimals at least equal to the required amount, so that it is guaranteed that the result fits.

What I've tried

I was able to roughly solve my problem using rational numbers & prime factorization, but this is very compute expensive. Here are the steps:

  • Take the original division: 1234.5678 / 6.4
  • Convert it to a rational number: 12345678 / 64000
  • Simplify this fraction using the GCD of the two numbers: 6172839 / 32000
  • Take the denominator: 32000
  • Compute the factors of 2 and 5 by dividing successively by these two numbers:
    32000= 28 * 53
  • (if it is found at this step that the number has other factors than 2 and 5, then stop here: the division yields an infinite number of digits)
  • Take the maximum of the two exponents: max(8,3) = 8
  • ⇒ 8 decimal places is enough to fit the result of the division.

How I came to the conclusion above

Out of all the prime numbers, only dividing by 2 and 5 yields a finite number of digits.

Each division by 10 extends the scale of the decimal number by 1 digit.
Each combination of 2 and 5 yields a 10, so an extra digit.

In 2x * 5y, there are min(x,y) times 10.

Now each division by 2 or 5 can potentially (although not always) require an extra digit. So I will carefully add an extra digit for each remaining 2 or 5 factor:

Maximum required digits = min(x,y) + (x - min(x,y)) + (y - min(x,y))

Which simplifies to: x + y - min(x,y)

Which further simplifies to max(x,y).

I feel like my approach, although it works, is overly complex. The direct consequence on my software is the slowness of the algorithm.

Is there a more straightforward approach to estimating the number of decimal places required for the result of the division to fit?

Note that I've read this question: Number of decimal places to be considered in division but it didn't help.

Best Answer

Have you tried calculating the maximum precision needed to reserve a place for the result?

Look how Java's BigDecimal does that:

https://github.com/frohoff/jdk8u-dev-jdk/blob/da0da73ab82ed714dc5be94acd2f0d00fbdfe2e9/src/share/classes/java/math/BigDecimal.java#L1674

Then the non-terminating numbers will cause an overflow of this area, so just check for this corner case during calculation and if that will happen, you can be sure it cannot be precisely expressed as decimal number.

Related Question