views:

923

answers:

5

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 :).

+6  A: 
  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.
Steve Gilham
+1 Thank you for your comment. This gives me some insight into the problem. Particularly the idea that cycle length and the actual cycle are driven by different factors is important. I knew that would be important for storing the cycle but I didn't consider that it might be important for calculating the cycle. However, I still don't see how to calculate the information.
Imagist
+3  A: 

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

Nick D
+1 Thank you for your post. This helped me understand the problem.
Imagist
+3  A: 

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.

Daniel Brückner
+1 By this logic then, in base 2, repeating decimals are fractions with denominators having prime factors other than 2 (I knew this). I didn't know that if they had a prime factor 1 it started somewhere other than the first position (that's helpful information!).
Imagist
+4  A: 

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.

forcey
+1 for your technical input. However Guffa's method seems pretty effective and seems like it will be linear in relation to the length of the number, which is fast enough given that this will probably be used most often with smaller numbers. While this allows me to support arbitrary-precision floating point operations, the real purpose is to keep base 10 numbers precise (i.e. in most languages 1.1 base 10 comes out 1.100000001 or somesuch because of repeating decimals).
Imagist
Actually there are better ways given your purpose: you can keep rational numbers in fraction form instead of expanding them, or you can simply do the math in base 10. Processing repeating decimals is not quite easy as I would imagine. :)
forcey
+1  A: 

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.
Guffa
im not sure if this solves his problem because some fractions repeat after a certain number of digits for example 5/6 = .8333333. so under your model it would use the 8 to find a repetition.
@letseatunch: 5/6 = 101/110 = 0.11010101010101010... If you run FindPattern(5,6) it will find the pattern repeating from digit -2 with the length 2.
Guffa
It took me a little while to understand your code because I don't know C# very well, but I think this is exactly for what I was looking. I'm writing this in C++ and the number storage isn't exactly that way, but it should be easy enough to port this over. Thank you very much for your help!
Imagist
+1 and accepted. :)
Imagist