Egyptian division

func egyptian_divmod(dividend, divisor) {
  var table = [[1, divisor]]
  table << table[-1].map{|e| 2*e } while (2*table[-1][0] <= dividend)
  var (answer, accumulator) = (0, 0)
  table.reverse.each { |pair|
    var (pow, double) = pair...
    if (accumulator + double <= dividend) {
      accumulator += double
      answer += pow
    }
  }
  return (answer, dividend - accumulator)
}

say ("Quotient = %s Remainder = %s" % egyptian_divmod(580, 34))

Output:

Quotient = 17 Remainder = 2

Last updated