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

Answer 2

What Mark Ransom said, except for a possibly-important optimisation: note that the remainders you get when dividing by b are in the range 0 to b-1, so only need O(b) space, and you can do it constant time per division step (that is, you don't have to search through your list of previous remainders). 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 six digits, and 1/17 = 0.(0588235294117647) has a recurring part of 16 digits. The length always divides b-1, actually.)

[Edit: Replaced pseudocode with actual Python code.]

def divide(a,b):
    '''a/b in three parts: integer, non-recurring fractional part, and recurring part'''
    assert b>0
    integer = a//b
    r = a%b
    seen = {r: 0} #The position at which the remainder was first seen.
    digits = []
    while(True):  #Loop is executed at most b times.
        r *= 10
        digits.append(r//b)
        r = r%b
        if seen.has_key(r):
            w = seen[r]
            return (integer, digits[:w], digits[w:])
        else:
            seen[r] = len(digits)

#Some examples
for m,n in [(5,4), (1,6), (17,7), (22,11), (100,17)]:
    (i,f,r) = divide(m,n)
    print "%d/%d = %d.%s(%s)" % (m,n,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)

Of course, you can change the output type and all that if you want. The algorithm runs in O(b log b) time, or O(b) if you use an array for seen instead of a dictionary.