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:
- Start the construction of a table of two columns:
powers_of_2, anddoublings; 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. - Create the second row with columns of 2 (i.e 2^1), and 2 * divisor in order.
- Continue with successive i’th rows of 2^i and 2^i * divisor.
- Stop adding rows, and keep only those rows, where 2^i * divisor is less than or equal to the dividend.
- We now assemble two separate sums that both start as zero, called here answer and accumulator
- Consider each row of the table, in the reverse order of its construction.
- 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.
- 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 | ||
| 16 | 544 | ||
| 16 | 544 |
| powers_of_2 | doublings | answer | accumulator |
|---|---|---|---|
| 1 | 34 | ||
| 2 | 68 | ||
| 16 | 544 | ||
| 16 | 544 |
| powers_of_2 | doublings | answer | accumulator |
|---|---|---|---|
| 1 | 34 | ||
| 16 | 544 | ||
| 16 | 544 |
| powers_of_2 | doublings | answer | accumulator |
|---|---|---|---|
| 1 | 34 | 17 | 578 |
| 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.
- References
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>
- include <stdio.h>
- include <stdlib.h>
- include <stdint.h>
- 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>
F#
<lang fsharp>// A function to perform Egyptian Division: Nigel Galloway August 11th., 2017 let egyptianDivision N G =
let rec fn n g = seq{yield (n,g); yield! fn (n+n) (g+g)}
Seq.foldBack (fun (n,i) (g,e)->if (i<g) then ((g-i),(e+n)) else (g,e)) (fn 1 G |> Seq.takeWhile(fun (_,g)->g<=N)) (N,0)
</lang> Which may be used: <lang fsharp> let (n,g) = egyptianDivision 584 34 printfn "584 divided by 34 is %d remainder %d" g n </lang>
- Output:
584 divided by 34 is 17 remainder 6
Haskell
Deriving division from (+) and (-) by unfolding from a seed pair (1, divisor) up to a series of successively doubling pairs, and then refolding that series of 'two column rows' back down to a (quotient, remainder) pair, using (0, dividend) as the initial accumulator value. In other words, taking the divisor as a unit, and deriving the binary composition of the dividend in terms of that unit. <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)
We can make the process of calculation more visible by adding a trace layer:
<lang Haskell>import Data.List (unfoldr) import Debug.Trace (trace)
egyptianQuotRem :: Int -> Int -> (Int, Int) egyptianQuotRem m n =
let rows =
unfoldr
(\(i, x) ->
if x > m
then Nothing
else Just ((i, x), (i + i, x + x)))
(1, n)
in trace
(unlines
[ "Number pair unfolded to series of doubling rows:"
, show rows
, "\nRows refolded down to (quot, rem):"
, show (0, m)
])
foldr
(\(i, x) (q, r) ->
if x < r
then trace
(concat
["(+", show i, ", -", show x, ") -> rem ", show (r - x)])
(q + i, r - x)
else (q, r))
(0, m)
rows
main :: IO () main = print $ egyptianQuotRem 580 34</lang>
- Output:
Number pair unfolded to series of doubling rows: [(1,34),(2,68),(4,136),(8,272),(16,544)] Rows refolded down to (quot, rem): (0,580) (+16, -544) -> rem 36 (+1, -34) -> rem 2 (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
"Not Egyptian"
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;
}
- 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
More "Egyptian" version
As the preceding version was determined to be "let's just say ... not Egyptian" we submit a alternate which is hopefully more Egyptian. Now only handles positive Integers up to 10 million.
Note: if the below is just a mass of "unknown glyph" boxes, try installing Googles free Noto Sans Egyptian Hieroglyphs font <lang perl6>my (\𓄤,\𓄊,\𓎆 ,\𓄰 ) = (0,1,10,10e7); sub infix:<𓂽> { $^𓃠 + $^𓃟 } sub infix:<𓂻> { $^𓃲 - $^𓆊 } sub 𓁶 (Int \𓆉) {
my \𓁢 = [« 𓏺 𓏻 𓏼 𓏽 𓏾 𓏿 𓐀 𓐁 𓐂»], [« 𓎆 𓎏 𓎐 𓎑 𓎊 𓎋 𓎌 𓎍 𓎎»],
[« 𓍢 𓍣 𓍤 𓍥 𓍦 𓍧 𓍨 𓍩 𓍪»], [« 𓆼 𓆽 𓆾 𓆿 𓇀 𓇁 𓇂 𓇃 𓇄»],
[« 𓂭 𓂮 𓂯 𓂰 𓂱 𓂲 𓂳 𓂴 𓂵»], ['𓆐' Xx ^𓎆], ['𓁨' Xx ^𓎆];
[~] (𓆉.polymod(𓎆 xx *).map( { 𓁢[$++;$_] } ).reverse) || '𓄤'
}
sub infix:<𓀨> (Int $𓂀 is copy where 𓄤 <= * < 𓄰, Int \𓌳 where 𓄤 < * < 𓄰) {
my $𓎦 = 𓄤;
([𓄊,𓌳], {[ .[𓄤] 𓂽 .[𓄤], .[𓄊] 𓂽 .[𓄊] ]} … ^ *.[𓄊] > $𓂀)
.reverse.map: { $𓂀 𓂻= .[𓄊], $𓎦 𓂽= .[𓄤] if $𓂀 >= .[𓄊] }
$𓎦, $𓂀;
}
- TESTING
for 580,34, 578,34, 2300578,23517 -> \𓃾, \𓆙 {
printf "Egyption divmod %s %% %s = %s remainder %s =OR= %s 𓀨 %s = %s remainder %s\n",
𓃾, 𓆙, |(𓃾 𓀨 𓆙), (𓃾, 𓆙, |(𓃾 𓀨 𓆙))».&𓁶;
}</lang>
- Output:
Egyption divmod 580 % 34 = 17 remainder 2 =OR= 𓍦𓎍 𓀨 𓎐𓏽 = 𓎆𓐀 remainder 𓏻 Egyption divmod 578 % 34 = 17 remainder 0 =OR= 𓍦𓎌𓐁 𓀨 𓎐𓏽 = 𓎆𓐀 remainder 𓄤 Egyption divmod 2300578 % 23517 = 97 remainder 19429 =OR= 𓁨𓁨𓆐𓆐𓆐𓍦𓎌𓐁 𓀨 𓂮𓆾𓍦𓎆𓐀 = 𓎎𓐀 remainder 𓂭𓇄𓍥𓎏𓐂
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)
- 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)
- 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
REXX
Only addition and subtraction is used in this version of the Egyptian division method. <lang rexx>/*REXX program performs division on positive integers using the Egyptian division method*/ numeric digits 1000 /*support gihugic numbers & be gung-ho.*/ parse arg n d . /*obtain optional arguments from the CL*/ if d== | d=="," then do; n=580; d=34; end /*Not specified? Then use the defaults*/ call EgyptDiv n, d /*invoke the Egyptian Division function*/ parse var result q r . /*extract the quotient and remainder. */ say n ' divided by ' d " is " q ' with a remainder of ' r exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ EgyptDiv: procedure; parse arg num,dem /*obtain the numerator and denominator.*/
p=1; t=dem /*initialize the double & power values.*/
do #=1 while t<=num /*construct the power & doubling lists.*/
pow.#=p; p=p + p /*build power entry; bump power value.*/
dbl.#=t; t=t + t /* " doubling " ; " doubling val.*/
end /*#*/
#=#-1 /*adjust the number of steps used. */
acc=0; ans=0 /*initialize accumulator & answer to 0 */
do s=# by -1 for # /* [↓] process the table in backwards.*/
sum=acc + dbl.s /*compute the sum (to be used for test)*/
if sum>num then iterate /*Is sum to big? Then ignore this step*/
acc=sum /*use the "new" sum for the accumulator*/
ans=ans + pow.s /*calculate the (newer) running answer.*/
end /*s*/
return ans num-acc /*return the answer and the remainder. */</lang>
- output when using the default inputs:
580 divided by 34 is 17 with a remainder of 2
- output when using the input of: 9876543210111222333444555666777888999 13579
9876543210111222333444555666777888999 divided by 13579 is 727339510281406755537562093436769 with a remainder of 2748
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)