division8.py

# binary search division
# aka, long division


def partial_division(divisor, dividend):
    difference = dividend - divisor
    return (0, dividend) if difference < 0 else (1, difference)


def division8(divisor, dividend):
    # divisor should be an unsigned eight bit integer
    # dividend should be an unsigned sixteen bit integer
    # highest eight bits of dividend should be less than divisor
    quotient = 0
    remainder = dividend >> 8
    for shift in reversed(range(8)):
        (partial_quotient, remainder) = partial_division(
            divisor, remainder << 1 & 510 | dividend >> shift & 1,
        )
        quotient = quotient << 1 | partial_quotient
    return (quotient, remainder)


# division8 can be trivially used to divide any two eight-bit integers
# division equation holds true: dividend = quotient * divisor + remainder
# remainder is always less than divisor
# quotient is always the largest possible value

# as an exception, division equation also holds true for division by zero
#   iff highest eight bits of dividend is zero
# remainder is greater than or equal to the divisor
#   iff divisor is zero

# division8 can be chained for larger dividends (e.g. 32 bits)