How to know the repeating decimal in a fraction?

I already know when a fraction is repeating decimals. Here is the function.

public bool IsRepeatingDecimal
{
    get
    {
        if (Numerator % Denominator == 0)
            return false;

        var primes = MathAlgorithms.Primes(Denominator);

        foreach (int n in primes)
        {
            if (n != 2 && n != 5)
                return true;
        }

        return false;
    }
}

Now, I'm trying to get the repeated number. I'm checking this web site: http://en.wikipedia.org/wiki/Repeating_decimal

public decimal RepeatingDecimal()
{
    if (!IsRepeatingDecimal) throw new InvalidOperationException("The fraction is not producing repeating decimals");

    int digitsToTake;
    switch (Denominator)
    {
        case 3:
        case 9: digitsToTake = 1; break;
        case 11: digitsToTake = 2; break;
        case 13: digitsToTake = 6; break;
        default: digitsToTake = Denominator - 1; break;
    }

    return MathExtensions.TruncateAt((decimal)Numerator / Denominator, digitsToTake);
}

But I really realized, that some numbers has a partial decimal finite and later infinite. For example: 1/28

Do you know a better way to do this? Or an Algorithm?

Solution 1:

A very simple algorithm is this: implement long division. Record every intermediate division you do. As soon as you see a division identical to the one you've done before, you have what's being repeated.

Example: 7/13.

1. 13 goes into   7 0 times with remainder  7; bring down a 0.
2. 13 goes into  70 5 times with remainder  5; bring down a 0.
3. 13 goes into  50 3 times with remainder 11; bring down a 0.
4. 13 goes into 110 8 times with remainder  6; bring down a 0.
5. 13 goes into  60 4 times with remainder  8; bring down a 0.
6. 13 goes into  80 6 times with remainder  2; bring down a 0.
7. 13 goes into  20 1 time  with remainder  7; bring down a 0.
8. We have already seen 13/70 on line 2; so lines 2-7 have the repeating part

The algorithm gives us 538461 as the repeating part. My calculator says 7/13 is 0.538461538. Looks right to me! All that remains are implementation details, or to find a better algorithm!

Solution 2:

If you have a (positive) reduced fraction numerator / denominator, the decimal expansion of the fraction terminates if and only if denominator has no prime factor other than 2 or 5. If it has any other prime factor, the decimal expansion will be periodic. However, the cases where the denominator is divisible by at least one of 2 and 5 and where it isn't give rise to slightly different behaviour. We have three cases:

1. denominator = 2^a * 5^b, then the decimal expansion terminates max {a, b} digits after the decimal point.
2. denominator = 2^a * 5^b * m where m > 1 is not divisible by 2 or by 5, then the fractional part of the decimal expansions consists of two parts, the pre-period of length max {a, b} and the period, whose length is determined by m and independent of the numerator.
3. denominator > 1 is not divisible by 2 or by 5, then the decimal expansion is purely periodic, meaning the period starts immediately after the decimal point.

The treatment of cases 1. and 2. has a common part, let c = max {a, b}, then

numerator / denominator = (numerator * 2^(c-a) * 5^(c-b)) / (10^c * m)

where m = 1 for case 1. Note that one of the factors 2^(c-a) and 5^(c-b) with which we multiply the numerator is 1. Then you get the decimal expansion by expanding

(numerator * 2^(c-a) * 5^(c-b)) / m

and shifting the decimal point c places to the left. In the first case (m = 1) that part is trivial.

The treatment of cases 2. and 3. also has a common part, the calculation of a fraction

n / m

where n and m have no common prime factor (and m > 1). We can write n = q*m + r with 0 <= r < m (division with remainder, r = n % m), q is the integral part of the fraction and rather uninteresting.

Since the fraction was assumed reduced, we have r > 0, so we want to find the expansion of a fraction r / m where 0 < r < m and m is not divisible by 2 or by 5. As mentioned above, such an expansion is purely periodic, so finding the period means finding the complete expansion.

Let's go about finding the period heuristically. So let k be the length of the (shortest) period and p = d_1d1_2...d_k the period. So

r / m = 0.d_1d_2...d_kd_1d_2...d_kd_1...
      = (d_1d_2...d_k)/(10^k) + (d_1d_2...d_k)/(10^(2k)) + (d_1d_2...d_k)/(10^(3k)) + ...
      = p/(10^k) * (1 + 1/(10^k) + 1/(10^(2k)) + 1/(10^(3k)) + ...)

The last term is a geometric series, 1 + q + q^2 + q^3 + ... which, for |q| < 1 has the sum 1/(1-q). In our case, 0 < q = 1/(10^k) < 1, so the sum is 1 / (1 - 1/(10^k)) = 10^k / (10^k-1). Thus we have seen that

r / m = p / (10^k-1)

Since r and m have no common factor, that means there is an s with 10^k - 1 = s*m and p = s*r. If we know k, the length of the period, we can simply find the digits of the period by calculating

p = ((10^k - 1)/m) * r

and padding with leading zeros until we have k digits. (Note: it is that simple only if k is sufficiently small or a big integer type is available. To calculate the period of for example 17/983 with standard fixed-width integer types, use long division as explained by @Patrick87.)

So it remains to find the length of the period. We can revert the reasoning above and find that if m divides 10^u - 1, then we can write

r / m = t/(10^u - 1) = t/(10^u) + t/(10^(2u)) + t/(10^(3u)) + ...
      = 0.t_1t_2...t_ut_1t_2...t_ut_1...

and r/m has a period of length u. So the length of the shortest period is the minimal positive u such that m divides 10^u - 1, or, put another way, the smallest positive u such that 10^u % m == 1.

We can find it in O(m) time with

u = 0;
a = 1;
do {
    ++u;
    a = (10*a) % m;
while(a != 1);

Now, finding the length of the period that way is not more efficient than finding the digits and length of the period together with long division, and for small enough m that is the most efficient method.

int[] long_division(int numerator, int denominator) {
    if (numerator < 1 || numerator >= denominator) throw new IllegalArgumentException("Bad call");
    // now we know 0 < numerator < denominator
    if (denominator % 2 == 0 || denominator % 5 == 0) throw new IllegalArgumentException("Bad denominator");
    // now we know we get a purely periodic expansion
    int[] digits = new int[denominator];
    int k = 0, n = numerator;
    do {
        n *= 10;
        digits[k++] = n / denominator;
        n = n % denominator;
    }while(n != numerator);
    int[] period = new int[k];
    for(n = 0; n < k; ++n) {
        period[n] = digits[n];
    }
    return period;
}

That works as long as 10*(denominator - 1) doesn't overflow, of course int could be a 32-bit or 64-bit integer as needed.

But for large denominators, that is inefficient, one can find the period length and also the period faster by considering the prime factorisation of the denominator. Regarding the period length,

• If the denominator is a prime power, m = p^k, the period length of r/m is a divisor of (p-1) * p^(k-1)
• If a and b are coprime and m = a * b, the period length of r/m is the least common multiple of the period lengths of 1/a and 1/b.

Taken together, the period length of r/m is a divisor of λ(m), where λ is the Carmichael function.

So to find the period length of r/m, find the prime factorisation of m and for all prime power factors p^k, find the period of 1/(p^k) - equivalently, the multiplicative order of 10 modulo p^k, which is known to be a divisor of (p-1) * p^(k-1). Since such numbers haven't many divisors, that is quickly done. Then find the least common multiple of all these.

For the period itself (the digits), if a big integer type is available and the period isn't too long, the formula

p = (10^k - 1)/m * r

is a quick way to compute it. If the period is too long or no big integer type is available, efficiently computing the digits is messier, and off the top of my head I don't remember how exactly that is done.