Integer Division With Recurring Decimals

I've been doing some programming tests and puzzles while job hunting lately. One quick challenge was quite nice, reminding me a bit of Project Euler questions, and I nerd sniped myself into doing a 2nd pass at it here.

Question

Produce a Python function which takes two integers, numerator and denominator, and returns the result of their division as a decimal fraction in a string. E.g:

divide(1, 4) -> "0.25"

If the decimal places contain an infinite recurring pattern of digits, then enclose the recurring digits in parentheses. E.g:

divide(1, 3) -> "0.(3)"
divide(1, 7) -> "0.(142857)"

Wrong approaches

Evaluating the division using normal floats is going to trip you up in several ways with the limited precision.

For one, a large enough denominator might have a recurring sequence which is longer than the number of decimal places you have available (more on this later), which makes it impossible to detect recurring sequences by examining the division's decimal digits.

Worse, the inherent imprecision of floating point, e.g. if a simple division like 10/3 comes back as 3.3333333333333335, then examining the trailing digits of this looking for recurring digits is going to be problematic.

Using the decimal module does markedly improve precision and control. But infinitely repeating sequences are still going to return results like Decimal(20) / Decimal(3) -> Decimal('6.666666666666666666666666667'), which is going to trip us up.

We can sidestep all these complexities if we see that the question is asking us to perform this division ourselves, longhand. We are going back to elementary school! Wheee!

Better

Let's just do basic division first, ignoring infinite or recurring digits:

def divide(numerator: int, denominator:int) -> str:
    # Accumulate parts of our result here
    results = []
    while True:
        int_part = str(numerator // denominator)
        remainder = numerator % denominator
        numerator = remainder * 10
        results.append(int_part)

        # If there is no remainder, we are done
        if remainder == 0:
            break

        # Add a decimal point after our first integer part
        if len(results) == 1:
            results.append(".")

    return ''.join(results)

The only confusing parts of this are that int_part might contain several digits on the first iteration, but is only ever one decimal digit thereafter. Plus we have to be careful to get the ordering right for our checks to exit the loop, versus appending the decimal point to the output, to avoid weird looking outputs like divide(6, 2) -> "3.".

Trying this out:

>>> divide(1, 4)
'0.25'

It works! But we haven't yet handled infinite decimals, they result in an infinite loop:

>>> divide(1, 3) # Hangs!

Recurring digits

Because we're dividing integers, we cannot get infinitely varying decimal places. If we have an infinite number of decimal places, it must be because of a cycle of one or more recurring digits. To detect such a cycle we have to notice a couple of things.

First, simply seeing a digit in the output which we have seen before is not enough. Looking at the three assignments at the start of the above while-loop, which capture our state:

int_part = str(numerator // denominator)
remainder = numerator % denominator
numerator = remainder * 10

Here, int_part gets the value of each successive decimal digit. However if it takes on the same value as in a previous iteration, the accompanying remainder might be different, and it is the remainder which is used to generate the numerator for the next iteration, and hence generate the sequence of digits after this.

So, as we already knew from common sense, two iterations with the same int_part may go on to produce different sequences of subsequent digits. However, The value of remainder is the only thing which determines the inputs to our next iteration:

• int_part depends on numerator and on denominator (which is constant)
• numerator depends on remainder.

Hence, two iterations might produce different digits, but produce the same remainder, and from that point onwards, they will be in lockstep. If we find two such iterations, then we have detected an infinite recurring cycle of digits.

So, before the loop begins, initialize a dict:

# Remainders seen to date, mapped to their position in the result
remainders = {}

Then inside the loop, after everything else, use our new dict to detect if we have seen the current remainder before:

# If we have seen this remainder before, we are now in exactly the
# same state as then, so we have found a recurring digit sequence.
if remainder in remainders:
    # We have found a cycle of decimal digits! Insert parens into our results,
    # from the last seen position of this remainder, up to the current digit.
    last_pos = remainders[remainder]
    results = (
        results[:last_pos] +
        ["("] +
        results[last_pos:] +
        [")"]
    )
    break
# Remember the position at which we saw this remainder
remainders[remainder] = len(results)

Trying this out:

>>> divide(1, 3)
0.(3)
>>> divide(1, 7)
0.(142857)

OMG it works!

Defensive coding

We're putatively done, but the grumpy old dev in me is uncomfortable leaving that while True in there. By deduction, we always must eventually hit the if <condition>: break to escape from it, so ostensibly it's fine. But if I have a bug in the code or my reasoning, then it might lead to an infinite loop, in some scenario I'm not thinking of. Can we limit the number of iterations in some other, foolproof way? Turns out we can.

We've seen already that a repeated value of remainder means we can break from the loop. Also, notice that remainder, given by:

remainder = numerator % denominator

can only take values from 0 to denominator - 1. So it can have denominator possible values, and this is the maximum number of iterations we will ever need.

Hence, we can safely replace the while(True) with:

for _ in range(denominator):
    ...

Splendid! Much less anxiety-inducing

The source is on github.