Implementing long division while checking for repeating decimals

user_11864893 0
Viewed 407

I have a function that takes an integer 'num' and returns any repeating digits in 1 / num. To do this, it takes advantage of a trick in long division. If you keep track of intermediate divisions and see the same division repeat itself, you know that the digits from the first time that division appeared to the previous division are the repeating digits in the decimal. I know this isn't explained well, but here's an example.

Try to run the following code.

def divide_with_repetition_check(num):
    """Determines 1 / num through long division one digit at a time. The function also checks for 
    repetition, and if there is any, 
    returns the repeating digits. 

    It would be better to separate the division functionality out into a generator, and then use 
    next() to yield each digit 
    and result combo to check for repetition in a separate function. 

    For now, this is how it will remain.

    Args:
        num (int): Denominator for divison

    Returns:
        string: Repeating digits converted to a string
    """
    dividend = 1
    zero_count = 0
    intermediate_divisions = []
    repeating_digits = ""

    result = dividend // num 

    while dividend:
        if (num, result) in intermediate_divisions:
            index = intermediate_divisions.index((num, result))
            for i in range(index, len(intermediate_divisions)):
                repeating_digits += str(intermediate_divisions[i][1])
            break
        if result == 0:
            zero_count += 1
        intermediate_divisions.append((num, result))
        dividend = (
            dividend % num * 10 
        )  # This is equivalent to "bringing down the zero" in long divison
        result = dividend // num
    return repeating_digits


num = 7
repeating_digits = divide_with_repetition_check(num)
print(repeating_digits)

For the purposes of this example, I will show a repeating decimal by putting the repeating digits in brackets. So if 1/3 = 0.3333333333333333..... I would write 0.(3).

With num set to 7, the script prints '142857' since 1/7 = 0.(142857). If you set num to 2, the script prints nothing since 1/2 = 0.5 which contains no repeating decimals.

The problem comes in when you set num to something like 14. 1/14 = 0.0(714285). There is a leading zero here, and the script determines that the zero is the repeating digit and prints '0' instead of '7142285' as it should.

This same issue arises for numbers with a leading zero in the decimal but with no repetition. For example, set num to 16.

Any help is greatly appreciated.

math algorithm python
3 Answers

The pattern repeats when the (dividend, result) pair repeats, not when the (num, result) pair repeats. So that is what you should store:

while dividend:
        if (dividend, result) in intermediate_divisions:
            index = intermediate_divisions.index((dividend, result))
            for i in range(index, len(intermediate_divisions)):
                repeating_digits += str(intermediate_divisions[i][1])
            break
        if result == 0:
            zero_count += 1
        intermediate_divisions.append((dividend, result))
        dividend = (
            dividend % num * 10
        )  # This is equivalent to "bringing down the zero" in long divison
        result = dividend // num

Also, you can make it a bit more pythonic by returning it this way:

if (dividend, result) in intermediate_divisions:
            index = intermediate_divisions.index((dividend, result))
            return ''.join((str(x[1]) for x in intermediate_divisions[index:]))
        if result == 0:
            zero_count += 1
...
user_3731510

An algorithm to yield the digits would be:

def division_digits(n):
    ''' digits of 1/n '''
    numerator = 1
    while True:
        yield (numerator * 10) // n
        numerator = (numerator * 10) % n

Here, the internal state is numerator, and you can see that when we have the same numerator a second time, the output will start being periodic.

def divide_with_repetition_check(n):
    ''' digits of 1/n detecting the periodic part '''
    numerator = 1
    digits = []
    mem = {}
    period_start = None
    while True:
        if numerator in mem:
            period_start = mem[numerator]
            break
        mem[numerator] = len(digits)
        digits.append((numerator * 10) // n)
        numerator = (numerator * 10) % n
    prefix = ''.join(f'{d}' for d in digits[:period_start])
    period = ''.join(f'{d}' for d in digits[period_start:])
    return f'0.{prefix}({period})'

Some examples:

> divide_with_repetition_check(56)
'0.017(857142)'
> divide_with_repetition_check(16)
'0.0625(0)'

Remark that for 16, the periodic part is a single 0. This is not a bug, this is how you write 1/16 = 0.062500000000....

user_116412780

Thanks for sharing this cool question! In case you want to consider alternatives, here is an answer using recursion:

floors = []
numerators = []

def divide_repeats(den, num=1):
    if num < den:
        num *= 10
    if num in numerators:
        return "".join(floors[numerators.index(num):])
    else:
        rem = num % den
        if rem == 0:
            return
        division = num // den
        floors.append(str(division))
        numerators.append(num)
        return divide_repeats(den, num=rem)

This seems to be working when tested against the table here. The output is a single string per your post, but you could also print a list, or return both the non-repeated and repeated decimals, etc.

In:
print(divide_repeats(7))
print(divide_repeats(14))
print(divide_repeats(49))
print(divide_repeats(5))

Out:
142857
714285
020408163265306122448979591836734693877551
None
user_133869790
Related