longdivision.py

from __future__ import division
def division(n, d):
    '''
    find integers q, r such that
       d * q + r = n
       0 <= r < d
    '''
    assert n >= 0
    assert d > 0
    q, r = 0, n
    assert n == (d * q) + r ## invariant!!
    print('dividend = (divisor * quotient) + remainder')
    print('%d == (%d * %d) + %d' % (n,d,q,r))
    while r >= d:
        k, m = 0, 0
        def biggest_digit(n, c):
            assert n >= 0
            s = str(n)
            return int(s[:1 + c]), 10 ** (len(s) - c - 1)
        for c in range(len(str(r))):
            k, m = biggest_digit(r, c)
            k = (k // d)
            if k > 0:
                break
        print('increase quotient by (%d * %d).' % (k, m))
        print('decrease remainder by (%d * (%d * %d)).' % (d, k, m))
        print('%d == (%d * (%d + (%d * %d))) + (%d - (%d * %d * %d))' % (n,d,q,k,m,r,d,k,m))
        q, r = q + k * m, r - (d * k * m)
        assert n == d * q + r
        print('%d == (%d * %d) + %d' % (n,d,q,r))
    print('\nquotient = %d, remainder = %d\n' % (q, r))
division(923, 5)