Repeating Decimals

[Joe Horn]

Wow, you launched me into a delightful revisit to the old PPC days when we wrote programs called "infinite division" which essentially performed long division, outputting as many digits of a division as you asked for. It's easy; to get N digits of A/B you just calculate iquo(A*10^N,B), and if the result is too few digits you just tack on leading zeros.

Now we have to discern how many digits we should ask for. The decimal expansion of every ratio of integers has two parts after the decimal point: a sequence of digits which don't repeat (called the transient) followed by a sequence of digits which repeat (called the repetend). Example: 1/208 = 0.0048076923 with the underlined digits repeating forever. Here's how to determine that the transient is 4 digits long, and the repetend is 6 digits long.

EDIT: STEP ZERO: Fully reduce the fraction, if your machine doesn't automatically do that for you (like RPL machines do). [Thanks to tgray for catching this oversight!]

First, factor out all 2's and 5's like this: 208 = 2^4 * 5^0 * 13. The powers of 2 and 5, as you can see, are 4 and 0. The length of the transient will always be the larger of those two powers (in this case, 4). This can be easily programmed. After factoring out the 2's and 5's, what's left is 13.

Next, find the multiplicative order of 10 (mod 13). It's always 10 because we are using base-10 ("decimal") notation. The 13 is from the previous paragraph. Finding the multiplicative order is not a simple task, but it's been programmed for the HP 50g and the algorithm would be the same on the Prime. The multiplicative order of 10 (mod 13) is 6. That's the length of the repetend.

So now we know that 1/208 consists of 4 non-repeating digits after the decimal point, followed by 6 repeating digits. All we have to do is use "infinite division" to crank out 10 digits of 1/208, and insert a symbol (such as an underscore) after the 4th digit, like this:

"0.0048_076923" which would mean 0.0048 followed by 076923 repeating forever.

Of course, if the repetend length is zero, then the decimal terminates, and the underscore symbol should not be inserted, e.g. 1/40 = 0.025 with no repeating part.

One benefit of using the above method is that it'll work for ANY fraction, no matter how many digits it has or how messy it might be. Anybody have time to code this for the Prime?