Division, Papadimitriou Book

division.rb

# 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