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 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 test(a, b):
    if b != 0:
        assert divmod(a, b) == divmod_fast(a, b)

for a in xrange(-100,100):
    for b in xrange(-100, 100):
        test(a, b)

test_values = [
    (231312313, 123525)
]

for a, b in test_values:
    assert divmod(a, b) == divmod_pos(a, b)