How to Calculate Recurring Digits?

Question

Given two integers a and b, how would I go about calculating the repeating decimal of a / b? This can be in any language; whatever it's easiest for you to express it in.

Answer 1

You can calculate the decimal representation of a / b using the long-division algorithm you learned at school, as Mark Ransom said. To calculate each successive digit, divide the current dividend (numerator or remainder) by b, and find the next dividend as the remainder multiplied by 10 ("bringing down a 0"). When a remainder is the same as some previous remainder, it means that the digits from then on will repeat as well, so you can note this fact and stop.

Note the potential for an optimisation here: the remainders you get when dividing by b are in the range 0 to b-1, so as you keep only distinct nonzero remainders, you don't have to search through your list of previous remainders to see if something repeats. So the algorithm can be made to take constant time per division step, and O(b) space is enough. Just keep track of what digit position each remainder first occurred at.

(This argument, BTW, is also a mathematical proof that the recurring part can be at most b-1 digits long: e.g. 1/7=0.(142857) has a recurring part of 6 digits, and 1/17 = 0.(0588235294117647) has a recurring part of 16 digits. The length always divides b-1, actually.)

Here's Python code for doing this, which runs in O(b) time.

def divide(a, b):
  '''Returns the decimal representation of the fraction a / b in three parts:
  integer part, non-recurring fractional part, and recurring part.'''
  assert b > 0
  integer = a // b
  remainder = a % b
  seen = {remainder: 0}  # Holds position where each remainder was first seen.
  digits = []
  while(True):  # Loop executed at most b times (as remainders must be distinct)
    remainder *= 10
    digits.append(remainder // b)
    remainder = remainder % b
    if remainder in seen:  # Digits have begun to recur.
      where = seen[remainder]
      return (integer, digits[:where], digits[where:])
    else:
      seen[remainder] = len(digits)

# Some examples.
for a, b in [(5,4), (1,6), (17,7), (22,11), (100,17)]:
  (i, f, r) = divide(a, b)
  print "%d/%d = %d.%s(%s)" % (a, b, i, ''.join(map(str, f)),''.join(map(str,r)))
# Output:
# 5/4 = 1.25(0)
# 1/6 = 0.1(6)
# 17/7 = 2.(428571)
# 22/11 = 2.(0)
# 100/17 = 5.(8823529411764705)

You can also use an array (a list in Python) of size b instead of a dictionary, which will be slightly faster (not in terms of asymptotics, but in the constant factor).

Answer 2

You can do it with long division. Calculate a single digit at a time and subtract to get a remainder, which you multiply by 10 to get the numerator for the next step. When this new numerator matches one of the previous numerators, you know you're going to repeat from that point forward. You just need to keep a stack of previous numerators and search through it at each iteration.