Numerical Methods – Best Way to Compute Decimal Representation of Fraction

numerical methods

Say you are given a fraction, e.g. $\frac{1}{37}$. What is the best way to compute its decimal notation given an arbitrary precision?

Is there a better way than to use a numerical algorithm, e.g. Newton's method? Is this what your calculator does in the background? And how about the other way around?

Best Answer

1

To compute the decimal notation to "infinite" precision, you can use only integer arithmetic, keeping remainders — the way you would do it with pencil and paper. For instance, to find $1/37$:

  • $\lfloor 1/37 \rfloor = 0$, so put down "$0.$" and "bring down" a $0$: that is, update your current dividend (an archaic word for the number you're dividing by $37$) to $10 = 10(1 - 0\cdot 37)$.
  • $\lfloor 10/37 \rfloor = 0$, so put down $0$ and update your dividend to $100 = 10(10 - 0\cdot 37)$.
  • $\lfloor 100/37 \rfloor = 2$, so put down $2$ and update your dividend to $10(100 - 2\cdot37) = 260$

And so on. When you see some dividend repeat, you can stop because you know that from then on, the process will proceed the same way it did the last time you saw that dividend: you have found the periodic part of the decimal expansion. Because after each step the dividend is updated to 10 times a remainder modulo 37, there are only 37 possible remainders; you will always get a repeat after at most 37 steps.

2

The above is not what normal calculators (and floating-point calculations on a computer) do. They are built not for arbitrary precision, but for fixed precision. They also don't distinguish between rational and irrational numbers for floating-point computation. Different division methods are used (see Wikipedia), including the naive division algorithm, Newton's method, multiplication by the reciprocal (computed either with a specialized routine or even possibly a lookup table), Hensel lifting, etc. (See e.g. sigfpe's post on division by 7 using 2-adic numbers.) Something like Newton's method, optimized for the word size of the calculator/computer, is preferred. BTW, numbers are usually stored in mantissa-exponent form, as a pair of binary integers $(s,e)$ denoting the number $1.s \times 2^e$. (For instance $37.0$ which is $100101.0$ in binary may be stored as the pair $(00101,5)$.)

3

Given the decimal expansion of a number, to write it as a fraction is easy if you know that it is exact. For instance if you know that a number is exactly $0.453$, then it is $453/1000$. But usually with fixed precision you know the decimal expansion only approximately: given $0.333333333$, what you want is probably $1/3$ rather than $333333333/1000000000$. For this, the best tool is continued fractions. For instance, $1/37 = 0.\overline{027}$ but if you have $0.02702703$ instead, its continued fraction gives the sequence of convergents $0$, $1/36$, $1/37$, $245700/9090899$, $737101/27272734$, $982801/36363633$, $2702703/100000000$, and you can use your judgment to decide that $1/37$ is probably what you want.

Related Question