import sys
from timeit import default_timer as clock

# Fast integer division, based on code from mdickinson, fast_div.py GH #47701

DIV_LIMIT = 1000


def _div2n1n(a, b, n):
    """Divide a 2n-bit nonnegative integer a by an n-bit positive integer
    b, using a recursive divide-and-conquer algorithm.

    Inputs:
      n is a positive integer
      b is a positive integer with exactly n bits
      a is a nonnegative integer such that a < 2**n * b

    Output:
      (q, r) such that a = b*q+r and 0 <= r < b.

    """
    if n <= DIV_LIMIT:
        return divmod(a, b)
    pad = n & 1
    if pad:
        a <<= 1
        b <<= 1
        n += 1
    half_n = n >> 1
    mask = (1 << half_n) - 1
    b1, b2 = b >> half_n, b & mask
    q1, r = _div3n2n(a >> n, (a >> half_n) & mask, b, b1, b2, half_n)
    q2, r = _div3n2n(r, a & mask, b, b1, b2, half_n)
    if pad:
        r >>= 1
    return q1 << half_n | q2, r


def _div3n2n(a12, a3, b, b1, b2, n):
    """Helper function for _div2n1n; not intended to be called directly."""
    if a12 >> n == b1:
        q, r = (1 << n) - 1, a12 - (b1 << n) + b1
    else:
        q, r = _div2n1n(a12, b1, n)
    r = (r << n | a3) - q * b2
    while r < 0:
        q -= 1
        r += b
    return q, r


def _divmod_pos(a, b):
    """Divide a positive integer a by a positive integer b, giving
    quotient and remainder."""
    # Use grade-school algorithm in base 2**n, n = nbits(b)
    n = len(bin(b)) - 2
    mask = (1 << n) - 1
    a_digits = []
    while a:
        a_digits.append(a & mask)
        a >>= n
    r = 0 if a_digits[-1] >= b else a_digits.pop()
    q = 0
    while a_digits:
        q_digit, r = _div2n1n((r << n) + a_digits.pop(), b, n)
        q = (q << n) + q_digit
    return q, r


def divmod_fast(a, b):
    """Asymptotically fast replacement for divmod, for integers."""
    if 0:
        print('divmod_fast', b.bit_length(), file=sys.stderr)
    if b == 0:
        raise ZeroDivisionError
    elif b < 0:
        q, r = divmod_fast(-a, -b)
        return q, -r
    elif a < 0:
        q, r = divmod_fast(~a, b)
        return ~q, b + ~r
    elif a == 0:
        return 0, 0
    else:
        return _divmod_pos(a, b)


def time_division(INT, twiceness=2.0, upto=18):
    fmt = "%10s %12.3f %12.3f %8.2f %8s"
    print(
        "%10s %12s %12s %8s %8s"
        % ("bits", "old time", "new time", "faster", "correct")
    )
    print("-" * 78)
    for i in range(4, upto):
        n = 2**i
        Q = INT(10) ** n
        P = INT(10) ** int(twiceness * n)
        t1 = clock()
        R1 = divmod(P, Q)
        t2 = clock()
        R2 = divmod_fast(P, Q)
        t3 = clock()
        size = Q.bit_length()
        old_time, new_time = t2 - t1, t3 - t2
        faster, correct = old_time / new_time, R2 == R1
        print(fmt % (size, old_time, new_time, faster, correct))


if __name__ == '__main__':
    time_division(int, 1.5, 18)