Best way of computing the decimal representation of a fraction with an arbitrary precision?

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?

-
Well, as the number is rational, its decimal expansion is eventually periodic, so you can simply compute it using the division algorithm until the digits start repeating. As soon as you're there, you know the decimal expansion to arbitrary precision. (as in the maybe more familiar $1/6$ or $1/7$, for example). – t.b. Jun 22 '11 at 9:44
What do you mean by "the other way around"? – ShreevatsaR Jun 22 '11 at 9:53
@ Theo: you are right. Is that also the way a calculator works in the background? And I guess that is also the fact for irrational numbers? @ ShreevatsaR: An algorithm that takes a decimal number and returns the equivalent fraction. – user12205 Jun 22 '11 at 10:15
@Theo: BTW, about memory: using the "baby steps giant steps" / "tortoise and hare" / "Floyd's cycle-finding algorithm" (the "rho" idea as in the Pollard rho algorithm), you can avoid the need for O(n) memory (where n is the denominator) and do it in O(1) memory, at the cost of possibly printing the periodic part more than once. – ShreevatsaR Jun 22 '11 at 11:06
@Theo: Oh, it's a simple idea; that's why it is rediscovered and has so many names. :-) Basically, to find the period $n$ of a eventually periodic sequence $x, f(x), f(f(x))$…, you can keep two values advancing through the sequence one step and two steps at a time respectively. Then you are guaranteed that within $n$ steps once the "slower" value enters the periodic part, they will meet again — the faster value gains on the slower value by one step each time — and when the two values are equal you know the period has been found. – ShreevatsaR Jun 22 '11 at 11:22

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.

-
Very nice answer, thank you! One link I'd like to add is the Wikipedia article on digital division since it contains a few promising references and seems quite readable itself. – t.b. Jun 22 '11 at 11:01
@Theo: Thanks, added the link you suggested and fixed the stub! – ShreevatsaR Jun 22 '11 at 11:11