Algorithm for detecting repeating decimals?

问题:

Is there an algorithm for figuring out the following things?

1. If the result of a division is a repeating decimal (in binary).
2. If it repeats, at what digit (represented as a power of 2) does the repetition start?
3. What digits repeat?

Some examples:

1/2 = 1/10 = 0.1 // 1 = false, 2 = N/A, 3 = N/A, 4 = N/A
1/3 = 1/11 = 0.010101... // 1 = true, 2 = -2, 3 = 10
2/3 = 10/11 = 0.101010... // 1 = true, 2 = -1, 3 = 10
4/3 = 100/11 = 1.010101... // 1 = true, 2 = 0, 3 = 10
1/5 = 1/101 = 0.001100110011... // 1 = true, 2 = -3, 3 = 1100

Is there a way to do this? Efficiency is a big concern. A description of the algorithm would be preferred over code, but I'll take what answer I can get.

It's also worth noting that the base isn't a big deal; I can convert the algorithm over to binary (or if it's in, say base 256 to use chars for ease, I could just use that). I say this because if you're explaining it might be easier for you to explain in base 10 :).

回答1:

To find the repeating pattern, just keep track of the values you use along the line:

1/5 = 1/101:

1 < 101 => 0
(decimal separator here)
10 < 101 => 0
100 < 101 => 0
1000 >= 101 => 1

  1000 - 101 = 11

110 >= 101 => 1

  110 - 101 = 1

10 -> match

As you reach the same value as you had at the second bit, the process will just repeat from that point producing the same bit pattern over and over. You have the pattern "0011" repeating from the second bit (first after decimal separator).

If you want the pattern to start with a "1", you can just rotate it until it matches that condition:

"0011" from the second bit
"0110" from the third bit
"1100" from the fourth bit

Edit:
Example in C#:

void FindPattern(int n1, int n2) {
   int digit = -1;
   while (n1 >= n2) {
      n2 <<= 1;
      digit++;
   }
   Dictionary<int, int> states = new Dictionary<int, int>();
   bool found = false;
   while (n1 > 0 || digit >= 0) {
      if (digit == -1) Console.Write('.');
      n1 <<= 1;
      if (states.ContainsKey(n1)) {
         Console.WriteLine(digit >= 0 ? new String('0', digit + 1) : String.Empty);
         Console.WriteLine("Repeat from digit {0} length {1}.", states[n1], states[n1] - digit);
         found = true;
         break;
      }
      states.Add(n1, digit);
      if (n1 < n2) {
         Console.Write('0');
      } else {
         Console.Write('1');
         n1 -= n2;
      }
      digit--;
   }
   if (!found) {
      Console.WriteLine();
      Console.WriteLine("No repeat.");
   }
}

Called with your examples it outputs:

.1
No repeat.
.01
Repeat from digit -1 length 2.
.10
Repeat from digit -1 length 2.
1.0
Repeat from digit 0 length 2.
.0011
Repeat from digit -1 length 4.

回答2:

1. if the divisor is not a power of 2 (in general, contains prime factors not shared with the base of representation)
2. repeat cycle length will be driven by the largest prime factor of the dividend (but not connected with the length of the representation of that factor -- see 1/7 in decimal), but the first cycle length may differ from the repeat unit (e.g. 11/28 = 1/4+1/7 in decimal).
3. the actual cycle will depend on the numerator.

回答3:

I can give a hint - repeating decimals in base ten are all fraction with the denominator having at least one prime factors other than two and five. If the denominator contains no prime factors two or five, they can always be represented with a denominator of all nines. Then the nominator is the repeating part and the number of nines is the length of the repeating part.

3     _
- = 0.3
9

1   142857     ______
- = ------ = 0.142857
7   999999

If there are prime factors two or five in the denominator, the repeating part starts not at the first position.

17    17        ______
-- = ----- = 0.4857142
35   5 * 7

But I cannot remember how to derive the non-repeating part and its length.

This seem to translate well to base two. Only fraction with a power of two denominator are non-repeating. This can be easily checked by asserting that only a single bit in the denominator is set.

1/2 =   1/10   = 0.1
1/4 =   1/100  = 0.01
3/4 =  11/100  = 0.11
5/8 = 101/1000 = 0.101

All fraction with odd denominators should be repeating and the pattern and its length can be obtained by expressing the fraction with a denominator in the form 2^n-1.

                                                     __
 1/3            =  1/(2^2-1) =        1/11       = 0.01
                                                     __
 2/3            =  2/(2^2-1) =       10/11       = 0.10
                       __
 4/3  => 1 + 1/3 =>  1.01
                       __
10/3  => 3 + 1/3 => 11.01
                                                     ____
 1/5  =   3/15  =  3/(2^4-1) =       11/1111     = 0.0011
                                                     ________
11/17 = 165/255 = 11/(2^8-1) = 10100101/11111111 = 0.10100101

As for base ten, I cannot tell how to handle denominators containing but not being a power of two - for example 12 = 3 * 2^2.

回答4:

First of all, one of your examples is wrong. The repeating part of 1/5 is 0011 rather than 1100, and it begins at the very beginning of the fractional part.

A repeating decimal is something like:

a/b = c + d(2-n + 2-n-k + 2-n-2k + ...)
    = c + 2-n * d / (1 - 2-k)

in which n and d are what you want.

For example,

1/10(dec) = 1/1010(bin) = 0.0001100110011... // 1 = true, 2 = -1, 3 = 0011

could be represented by the formula with

a = 1, b = 10(dec), c = 0, d = 0.0011(bin), n = 1, k = 4;
(1 - 2-k) = 0.1111

Therefore, 1/10 = 0.1 * 0.0011/0.1111. The key part of a repeating decimal representation is generated by dividing by (2n - 1) or its any multiple of 2. So you can either find a way to express your denominator as such (like building constant tables), or do a big number division (which is relatively slow) and find the loop. There's no quick way to do this.

回答5:

Check out decimal expansion, and specifically about the period of a fraction.

回答6:

You can do a long division, noting the remainders. The structure of the remainders will give you the structure of any rational decimal:

1. the last remainder is zero: it is a decimal without any repeating part
2. the first and the last remainder are equal: the decimal is repeating right after the dot
3. the distance between the first and the first remainder equal to the last are the non-repeating digits, the remainder is the repeating part

In general the distances will give you the amount of digits for each part.

You can see this algorithm coded in C++ in the method decompose() here.

Try 228142/62265, it has a period of 1776 digits!