Skip to content

Instantly share code, notes, and snippets.

@israelst
Created March 15, 2012 03:29
Show Gist options
  • Save israelst/2041698 to your computer and use it in GitHub Desktop.
Save israelst/2041698 to your computer and use it in GitHub Desktop.
Division, Papadimitriou Book
# this one comes from the book
def divide(x, y)
return {:q => 0, :r => 0} if x==0
result = divide(x/2, y)
result[:q] *= 2
result[:r] *= 2
result[:r] += 1 if x.odd?
if result[:r] >= y
result[:r] -= y
result[:q] += 1
end
result
end
# this one is worse
def divide2(x, y)
result = {:q => 0, :r => 0}
while x >= y
x -= y
result[:q] += 1
end
result[:r] = x
result
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment