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, 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 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)