Egyptian division

Egyptian division
You are encouraged to solve this task according to the task description, using any language you may know.

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:

1. Start the construction of a table of two columns: powers_of_2, and doublings; by a first row of a 1 (i.e. 2^0) in the first column and 1 times the divisor in the first row second column.
2. Create the second row with columns of 2 (i.e 2^1), and 2 * divisor in order.
3. Continue with successive i’th rows of 2^i and 2^i * divisor.
4. Stop adding rows, and keep only those rows, where 2^i * divisor is less than or equal to the dividend.
5. We now assemble two separate sums that both start as zero, called here answer and accumulator
6. Consider each row of the table, in the reverse order of its construction.
7. If the current value of the accumulator added to the doublings cell would be less than or equal to the dividend then add it to the accumulator, as well as adding the powers_of_2 cell value to the answer.
8. When the first row has been considered as above, then the integer division of dividend by divisor is given by answer.
   (And the remainder is given by the absolute value of accumulator - dividend).

Example: 580 / 34

Table creation:

powers_of_2	doublings
1	34
2	68
4	136
8	272
16	544

Initialization of sums:

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136
8	272
16	544
		0	0

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.

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136
8	272
16	544	16	544

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136
8	272	16	544
16	544

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136	16	544
8	272
16	544

powers_of_2	doublings	answer	accumulator
1	34
2	68	16	544
4	136
8	272
16	544

powers_of_2	doublings	answer	accumulator
1	34	17	578
2	68
4	136
8	272
16	544

Answer

So 580 divided by 34 using the Egyptian method is 17 remainder (578 - 580) or 2.

Task

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.

• Functions should be clear interpretations of the algorithm.
• Use the function to divide 580 by 34 and show the answer here, on this page.

AppleScript

Unfold to derive rows, fold to sum quotient and derive remainder <lang AppleScript>-- EGYPTIAN DIVISION ---------------------------------------------------------

-- egyptianQuotRem :: Int -> Int -> (Int, Int) on egyptianQuotRem(m, n)

   script doubledRows
       script double
           on |λ|(x)
               x + x
           end |λ|
       end script
       
       on |λ|(ix)
           if item 2 of ix > m then
               {nothing:true}
           else
               {just:ix, new:map(double, ix), nothing:false}
           end if
       end |λ|
   end script
   
   set rows to unfoldr(doubledRows, [1, n])
   
   script quotientSum
       on |λ|(ix, qr)
           set {i, x} to ix
           set {q, r} to qr
           
           if x < r then
               {q + i, r - x}
           else
               {q, r}
           end if
       end |λ|
   end script
   
   foldr(quotientSum, {0, m}, rows)

end egyptianQuotRem

-- TEST ---------------------------------------------------------------------- on run

   egyptianQuotRem(580, 34)
   
   --> {17, 2}

end run

-- GENERIC FUNCTIONS --------------------------------------------------------- -- foldr :: (a -> b -> a) -> a -> [b] -> a on foldr(f, startValue, xs)

   tell mReturn(f)
       set v to startValue
       set lng to length of xs
       repeat with i from lng to 1 by -1
           set v to |λ|(item i of xs, v, i, xs)
       end repeat
       return v
   end tell

end foldr

-- map :: (a -> b) -> [a] -> [b] on map(f, xs)

   tell mReturn(f)
       set lng to length of xs
       set lst to {}
       repeat with i from 1 to lng
           set end of lst to |λ|(item i of xs, i, xs)
       end repeat
       return lst
   end tell

end map

-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f)

   if class of f is script then
       f
   else
       script
           property |λ| : f
       end script
   end if

end mReturn

-- unfoldr :: (b -> Maybe (a, b)) -> b -> [a] on unfoldr(f, v)

   set mf to mReturn(f)
   set lst to {}
   set recM to {nothing:false, new:v}
   repeat while (not (nothing of recM))
       set recM to mf's |λ|(new of recM)
       if not nothing of recM then set end of lst to just of recM
   end repeat
   lst

end unfoldr</lang>

Output:

{17, 2}

C

<lang c>

1. include <stdio.h>
2. include <stdlib.h>
3. include <stdint.h>
4. include <assert.h>

uint64_t egyptian_division(uint64_t dividend, uint64_t divisor, uint64_t *remainder) { // remainder is an out parameter, pass NULL if you do not need the remainder

static uint64_t powers[64]; static uint64_t doublings[64];

int i;

for(i = 0; i < 64; i++) { powers[i] = 1 << i; doublings[i] = divisor << i; if(doublings[i] > dividend) break; }

uint64_t answer = 0; uint64_t accumulator = 0;

for(i = i - 1; i >= 0; i--) { // If the current value of the accumulator added to the // doublings cell would be less than or equal to the // dividend then add it to the accumulator if(accumulator + doublings[i] <= dividend) { accumulator += doublings[i]; answer += powers[i]; } }

if(remainder) *remainder = dividend - accumulator; return answer; }

void go(uint64_t a, uint64_t b) { uint64_t x, y; x = egyptian_division(a, b, &y); printf("%llu / %llu = %llu remainder %llu\n", a, b, x, y); assert(a == b * x + y); }

int main(void) { go(580, 32); } </lang>

Haskell

In Haskell we could lazily take the rows we need from an infinite list, <lang Haskell>egyptianQuotRem :: Integral a => a -> a -> (a, a) egyptianQuotRem m n =

 let rows =
       takeWhile (\[_, e] -> e <= m) $
       (([id, (n *)] <*>) . return . (2 ^)) <$> [0 ..]
 in foldr
      (\[i, x] (q, r) ->
          if x < r
            then (q + i, r - x)
            else (q, r))
      (0, m)
      rows

main :: IO () main = print $ egyptianQuotRem 580 34</lang>

Output:

(17,2)

but perhaps it sheds more light on the nature of the calculation to precede the fold with an unfold.

<lang Haskell>import Data.List (unfoldr)

egyptianQuotRem :: Integral a => a -> a -> (a, a) egyptianQuotRem m n =

 let rows =
       unfoldr
         (\(i, x) ->
             if x > m
               then Nothing
               else Just ((i, x), (i + i, x + x)))
         (1, n)
 in foldr
      (\(i, x) (q, r) ->
          if x < r
            then (q + i, r - x)
            else (q, r))
      (0, m)
      rows

main :: IO () main = print $ egyptianQuotRem 580 34</lang>

Output:

(17,2)

JavaScript

ES6

<lang JavaScript>(() => {

   'use strict';

   // EGYPTIAN DIVISION -----------------------------------------------------

   // egyptianQuotRem :: Int -> Int -> (Int, Int)
   const egyptianQuotRem = (m, n) => {
       const rows = unfoldr(
           ix => {
               const v = ix.new
               return v.x > m ? {
                   nothing: true
               } : {
                   just: v,
                   new: {
                       i: v.i * 2,
                       x: v.x * 2
                   }
               }
           }, {
               i: 1,
               x: n
           }
       );
       return foldr(({
           i: i,
           x: x
       }, [q, r]) => x < r ? [q + i, r - x] : [q, r], [0, m], rows);
   };

   // GENERIC FUNCTIONS -----------------------------------------------------

   // flip :: (a -> b -> c) -> b -> a -> c
   const flip = f => (a, b) => f.apply(null, [b, a]);

   // foldr (a -> b -> b) -> b -> [a] -> b
   const foldr = (f, a, xs) => xs.reduceRight(flip(f), a);

   // show :: a -> String
   const show = (...x) =>
       JSON.stringify.apply(
           null, x.length > 1 ? [x[1], null, x[0]] : x
       );

   // unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
   const unfoldr = (mf, v) => {
       let xs = [];
       return (until(
           m => m.nothing,
           m => {
               const m2 = mf(m);
               return (
                   xs = m2.nothing ? xs : xs.concat(m2.just),
                   m2
               );
           }, {
               nothing: false,
               just: v,
               new: v,
           }
       ), xs);
   };

   // until :: (a -> Bool) -> (a -> a) -> a -> a
   const until = (p, f, x) => {
       let v = x;
       while (!p(v)) v = f(v);
       return v;
   };

   // TEST ------------------------------------------------------------------
   return show(
       egyptianQuotRem(580, 34)
   );

})();</lang>

Output:

[17,2]

Perl 6

Works with: Rakudo version 2017.07

Only works with positive real numbers, not negative or complex. <lang perl6>sub egyptian-divmod (Real $dividend is copy where * > 0, Real $divisor where * > 0) {

   my @multiples = map { 2 ** $_ => 2 ** $_ * $divisor }, ^Inf;
   my @table = @multiples[ ^@multiples.first: *.value > $dividend, :k ].reverse;
   my $accumulator = 0;
   @table.map: {$dividend -= .value, $accumulator += .key if $dividend >= .value}
   $accumulator, $dividend;

}

1. TESTING

for 580,34, 578,34, 7532795332300578,235117 -> $n, $d {

   printf "Egyption divmod %s %% %s = %s remainder %s\n",
       $n, $d, |egyptian-divmod( $n, $d )

}</lang>

Output:

Egyption divmod 580 % 34 = 17 remainder 2
Egyption divmod 578 % 34 = 17 remainder 0
Egyption divmod 7532795332300578 % 235117 = 32038497141 remainder 81

Python

<lang python>def egyptian_divmod(dividend, divisor):

   assert divisor != 0
   pwrs, dbls = [1], [divisor]
   while dbls[-1] <= dividend:
       pwrs.append(pwrs[-1] * 2)
       dbls.append(pwrs[-1] * divisor)
   ans, accum = 0, 0
   for pwr, dbl in zip(pwrs[-2::-1], dbls[-2::-1]):
       if accum + dbl <= dividend:
           accum += dbl
           ans += pwr
   return ans, abs(accum - dividend)

1. Test it gives the same results as the divmod built-in

from itertools import product for i, j in product(range(13), range(1, 13)):

       assert egyptian_divmod(i, j) == divmod(i, j)

1. Mandated result

i, j = 580, 34 print(f'{i} divided by {j} using the Egyption method is %i remainder %i'

     % egyptian_divmod(i, j))</lang>

Sample output

580 divided by 34 using the Egyption method is 17 remainder 2

zkl

<lang zkl>fcn egyptianDivmod(dividend,divisor){

  table:=[0..].pump(List, 'wrap(n){	// (2^n,divisor*2^n)
     r:=T( p:=(2).pow(n), s:=divisor*p); (s<=dividend) and r or Void.Stop });
  accumulator:=0;
  foreach p2,d in (table.reverse()){ 
     if(dividend>=d){ accumulator+=p2; dividend-=d; }
  }
  return(accumulator,dividend);

}</lang> <lang zkl>foreach dividend,divisor in (T(T(580,34), T(580,17), T(578,34), T(7532795332300578,235117))){

 println("%d %% %d = %s".fmt(dividend,divisor,egyptianDivmod(dividend,divisor)));

}</lang>

Output:

580 % 34 = L(17,2)
580 % 17 = L(34,2)
578 % 34 = L(17,0)
7532795332300578 % 235117 = L(32038497141,81)