4

Possible Duplicate:
How to know the repeating decimal in a fraction?

1/3 is different by 3/10. 0.33333 != 0.3

So 1/3 will be 0.3 (with a line above number three)

1/12 = 0.833333 = 0.083 (with a line above number three)

1/13 = 0.076923076923 = 0.|076923|

Those lines represent the repeating part.

I plan to have this model in a class. I'm a bit lost on this situation. I just need some ideas to know determine the repeating value. Thanks.

Community
  • 1
  • 1
Darf Zon
  • 6,268
  • 20
  • 90
  • 149
  • 1
    Basically, emulate long division. Keep track of every long division remainder. If you encounter a remainder you have seen before, the sequence since you saw that remainder is the repeating value. – cheeken Jul 02 '12 at 14:58
  • Although it is duplicate, no one ever mentions about cycle finding algorithm in the duplicate question, though. – nhahtdh Jul 02 '12 at 15:09

2 Answers2

5

Cycle detection algorithm is the answer. You can use Floyd's cycle detection algorithm or Brent's cycle detection algorithm.

The function to plug into those algorithms is the function to produce the next digit of the quotient.

nhahtdh
  • 55,989
  • 15
  • 126
  • 162
4

At each step, divide, floor, take the remainder, multiply that by ten, repeat until you get the same number.

For example, for 1/81:

1/81 = 0 with remainder 1       0
10/81 = 0 with remainder 10     0.0
100/81 = 1 with remainder 19    0.01
190/81 = 2 with remainder 28    0.012
280/81 = 3 with remainder 37    0.0123
...
10/81 = 0 with remainder 10; saw this already.
0.|012345679|

Here's a sample implementation:

private static string GetRepeatingPart(int n, int d) {
    var seen = new HashSet<int>();
    var result = new StringBuilder();

    n = (n % d) * 10;

    while(true) {
        int p = n / d;
        n = (n % d) * 10;

        if(seen.Contains(n)) {
            return result.ToString();
        }

        result.Append(p);
        seen.Add(n);
    }
}
Ry-
  • 218,210
  • 55
  • 464
  • 476
  • This is also a correct method, with space complexity of O(lambda + mu) and lower hidden constant for time complexity, compared to O(1) space and higher hidden constant for time complexity of cycle finding algorithm. – nhahtdh Jul 02 '12 at 15:07