Skip to content

Instantly share code, notes, and snippets.

@scvalex
Created March 13, 2010 20:58
Show Gist options
  • Save scvalex/331544 to your computer and use it in GitHub Desktop.
Save scvalex/331544 to your computer and use it in GitHub Desktop.
Binary search division in Python
import sys
def bigmul(a, b):
"""r = a * b
where
r = bidmul(a, b)"""
xs = list(reversed(digits(a)))
ys = list(reversed(digits(b)))
zs = [0 for i in xrange(300)]
for i in xrange(len(ys)):
t = 0
for j in xrange(len(xs)):
zs[i+j] += ys[i] * xs[j] + t
t = zs[i+j] / 10
zs[i+j] %= 10
zs[len(ys)+len(xs)-1] = t
return int("".join([str(d) for d in reversed(zs)]))
def bigdiv(a, b):
"""r = (a / b, a % b)
where
r = bigdiv(a, b)"""
i = 1L
while i < a:
i = bigmul(i, 2)
l = 1
while i > 0:
c = bigmul((l+i), b)
if c <= a:
l += i
i = i / 2
return (l, a - bigmul(l, b))
def digits(n):
"""Returns a list of n's digits."""
r = []
while n > 0:
r.append(n % 10)
n /= 10
r.reverse()
return r
if __name__ == "__main__":
print bigdiv(int(sys.argv[1]), int(sys.argv[2]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment