The 3 flavors of division.

division.py

#!/usr/bin/env python3
import functools
import gmpy2

# assuming 8-bit math

# all functions are written to take any input, and produce signed output

def make_unsigned(v):
    return v & 0xff

def make_signed(v):
    return make_unsigned(v + 0x80) - 0x80

def udivmod(n, d):
    n = make_unsigned(n)
    d = make_unsigned(d)
    q = n // d
    r = n % d
    return make_signed(q), make_signed(r)

def ndivmod(n, d):
    n = make_signed(n)
    d = make_signed(d)
    n_negative = n < 0
    d_negative = d < 0
    n = abs(n)
    d = abs(d)

    q = n // d
    r = n % d

    # alternatively: if n_negative != d_negative: ...
    if d_negative:
        q = -q
    if n_negative:
        q = -q
        r = -r

    if r != 0: assert n_negative == (r < 0)
    assert (q, r) == (make_signed(q), make_signed(r))
    return q, r

def ddivmod(n, d):
    n = make_signed(n)
    d = make_signed(d)
    n_negative = n < 0
    d_negative = d < 0
    orig_d = d
    n = abs(n)
    d = abs(d)

    q = n // d
    r = n % d

    # alternatively: if n_negative != d_negative: ...
    if d_negative:
        q = -q
    if n_negative:
        q = -q
        r = -r

    # everything above this is identical to ndivmod, but we remember orig_d
    # this branch could be merged with the alternate above
    if n_negative != d_negative:
        if r:
            q -= 1
            r += orig_d
    if r != 0: assert d_negative == (r < 0)
    assert (q, r) == (make_signed(q), make_signed(r))
    return q, r


def check_invariant(f):
    for n in range(-128, 127+1):
        for d in range(-128, 127+1):
            if d == 0 or (n == -128 and d == -1):
                # no requirements
                continue
            q, r = f(n, d)
            assert make_signed(d*q + r) == n, (f, n, d, q, r)
            if f is udivmod:
                # hack: this invariant requires the "actual" denominator
                d = make_unsigned(d)
            assert -abs(d) < r < abs(d), (f, n, d, q, r)

def make_assert_same(f, *gs):
    @functools.wraps(f)
    def merged(*args):
        rv = f(*args)
        for g in gs:
            assert rv == g(*args), (f, g, args, rv)
        return rv
    return merged

def main():
    check_invariant(udivmod)
    # C now mandates this one
    check_invariant(make_assert_same(ndivmod, gmpy2.t_divmod))
    # but Python chose this one
    check_invariant(make_assert_same(ddivmod, divmod, gmpy2.f_divmod))
    print('Sanity check passed!')

if __name__ == '__main__':
    main()