Problem Statement

Egyptian division is a method of dividing integers using addition and doubling that is similar to the algorithm of Ethiopian multiplication Algorithm: Given two numbers where the dividend is to be divided by the divisor:

Example: 580 / 34 Table creation: Initialization of sums: Considering table rows, bottom-up: When a row is considered it is shown crossed out if it is not accumulated, or bold if the row causes summations. So 580 divided by 34 using the Egyptian method is 17 remainder (578 - 580) or 2.

The task is to create a function that does Egyptian division. The function should closely follow the description above in using a list/array of powers of two, and another of doublings.

Let's start with the solution:

F egyptian_divmod(dividend, divisor)
   assert(divisor != 0)
   V (pwrs, dbls) = ([1], [divisor])
   L dbls.last <= dividend
      pwrs.append(pwrs.last * 2)
      dbls.append(pwrs.last * divisor)
   V (ans, accum) = (0, 0)
   L(pwr, dbl) zip(pwrs[((len)-2 ..).step(-1)], dbls[((len)-2 ..).step(-1)])
      I accum + dbl <= dividend
         accum += dbl
         ans += pwr
   R (ans, abs(accum - dividend))

L(i, j) cart_product(0.<13, 1..12)
   assert(egyptian_divmod(i, j) == divmod(i, j))
V (i, j) = (580, 34)
V (d, m) = egyptian_divmod(i, j)
print(‘#. divided by #. using the Egyption method is #. remainder #.’.format(i, j, d, m))