Egyptian division

From Rosetta Code
Task
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.
References


Ada[edit]

 
with Ada.Text_IO;
 
procedure Egyptian_Division is
 
procedure Divide (a : Natural; b : Positive; q, r : out Natural) is
doublings : array (0..31) of Natural; -- The natural type holds values < 2^32 so no need going beyond
m, sum, last_index_touched : Natural := 0;
begin
for i in doublings'Range loop
m := b * 2**i;
exit when m > a ;
doublings (i) := m;
last_index_touched := i;
end loop;
q := 0;
for i in reverse doublings'First .. last_index_touched loop
m := sum + doublings (i);
if m <= a then
sum := m;
q := q + 2**i;
end if;
end loop;
r := a -sum;
end Divide;
 
q, r : Natural;
begin
Divide (580,34, q, r);
Ada.Text_IO.put_line ("Quotient="&q'Img & " Remainder="&r'img);
end Egyptian_Division;
 
Output:
Quotient= 17 Remainder= 2

ALGOL 68[edit]

BEGIN
# performs Egyptian division of dividend by divisor, setting quotient and remainder #
# this uses 32 bit numbers, so a table of 32 powers of 2 should be sufficient #
# ( divisors > 2^30 will probably overflow - this is not checked here ) #
PROC egyptian division = ( INT dividend, divisor, REF INT quotient, remainder )VOID:
BEGIN
[ 1 : 32 ]INT powers of 2, doublings;
# initialise the powers of 2 and doublings tables #
powers of 2[ 1 ] := 1;
doublings [ 1 ] := divisor;
INT table pos := 1;
WHILE table pos +:= 1;
powers of 2[ table pos ] := powers of 2[ table pos - 1 ] * 2;
doublings [ table pos ] := doublings [ table pos - 1 ] * 2;
doublings[ table pos ] <= dividend
DO
SKIP
OD;
# construct the accumulator and answer #
INT accumulator := 0, answer := 0;
WHILE table pos >=1
DO
IF ( accumulator + doublings[ table pos ] ) <= dividend
THEN
accumulator +:= doublings [ table pos ];
answer +:= powers of 2[ table pos ]
FI;
table pos -:= 1
OD;
quotient := answer;
remainder := ABS ( accumulator - dividend )
END # egyptian division # ;
 
# task test case #
INT quotient, remainder;
egyptian division( 580, 34, quotient, remainder );
print( ( "580 divided by 34 is: ", whole( quotient, 0 ), " remainder: ", whole( remainder, 0 ), newline ) )
END
Output:
580 divided by 34 is: 17 remainder: 2

AppleScript[edit]

Unfold to derive rows, fold to sum quotient and derive remainder

-- 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
Output:
{17, 2}

C[edit]

 
#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);
}
 

D[edit]

 
import std.stdio;
 
version(unittest) {
// empty
} else {
int main(string[] args) {
import std.conv;
 
if (args.length < 3) {
stderr.writeln("Usage: ", args[0], " dividend divisor");
return 1;
}
 
ulong dividend = to!ulong(args[1]);
ulong divisor = to!ulong(args[2]);
ulong remainder;
 
auto ans = egyptian_division(dividend, divisor, remainder);
writeln(dividend, " / ", divisor, " = ", ans, " rem ", remainder);
 
return 0;
}
}
 
ulong egyptian_division(ulong dividend, ulong divisor, out ulong remainder) {
enum SIZE = 64;
ulong[SIZE] powers;
ulong[SIZE] doublings;
int i;
 
for (; i<SIZE; ++i) {
powers[i] = 1 << i;
doublings[i] = divisor << i;
if (doublings[i] > dividend) {
break;
}
}
 
ulong answer;
ulong accumulator;
 
for (i=i-1; i>=0; --i) {
if (accumulator + doublings[i] <= dividend) {
accumulator += doublings[i];
answer += powers[i];
}
}
 
remainder = dividend - accumulator;
return answer;
}
 
unittest {
ulong remainder;
 
assert(egyptian_division(580UL, 34UL, remainder) == 17UL);
assert(remainder == 2);
}
 

F#[edit]

// 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)
 

Which may be used:

 
let (n,g) = egyptianDivision 580 34
printfn "580 divided by 34 is %d remainder %d" g n
 
Output:
580 divided by 34 is 17 remainder 2

FreeBASIC[edit]

' version 09-08-2017
' compile with: fbc -s console
 
Data 580, 34
 
Dim As UInteger dividend, divisor, answer, accumulator, i
ReDim As UInteger table(1 To 32, 1 To 2)
 
Read dividend, divisor
 
i = 1
table(i, 1) = 1 : table(i, 2) = divisor
 
While table(i, 2) < dividend
i += 1
table(i, 1) = table(i -1, 1) * 2
table(i, 2) = table(i -1, 2) * 2
Wend
 
i -= 1
answer = table(i, 1)
accumulator = table(i, 2)
 
While i > 1
i -= 1
If table(i,2)+ accumulator <= dividend Then
answer += table(i, 1)
accumulator += table(i, 2)
End If
Wend
 
Print Str(dividend); " divided by "; Str(divisor); " using Egytian division";
Print " returns "; Str(answer); " mod(ulus) "; Str(dividend-accumulator)
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
580 divided by 34 using Egytian division returns 17 mod(ulus) 2

Haskell[edit]

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.

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
Output:
(17,2)

We can make the process of calculation more visible by adding a trace layer:

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
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)

Another approach, using lazy lists and foldr:

doublings = iterate (* 2)
 
powers = doublings 1
 
k n (u, v) (ans, acc) =
if v + ans <= n
then (v + ans, u + acc)
else (ans, acc)
 
egy n = snd . foldr (k n) (0, 0) . zip powers . takeWhile (<= n) . doublings
 
main :: IO ()
main = print $ egy 580 34
Output:
17

J[edit]

Implementation:

doublings=:_1 }. (+:@]^:(> {:)^:a: (,~ 1:))
ansacc=: 1 }. (] + [ * {[email protected][ >: {:@:+)/@([,.doublings)
egydiv=: (0,[)+1 _1*ansacc

Task example:

   580 doublings 34
1 34
2 68
4 136
8 272
16 544
580 ansacc 34
17 578
580 egydiv 34
17 2

Notes: pre When building the doublings table, we don't actually know we've exceeded our numerator until we are done. This would result in an excess row, so we have to explicitly not include that excess row in our doublings result.

Our "fold" is actually not directly on the result of doublings - for our fold, we add another column where every value is the numerator. This conveniently makes it available for comparison at every stage of the fold and seems a more concise approach than creating a closure. (We do not include this extra value in our ansacc result, of course.)

Java[edit]

 
import java.util.ArrayList;
import java.util.List;
 
public class EgyptianDivision {
 
/**
* Runs the method and divides 580 by 34
*
* @param args not used
*/

public static void main(String[] args) {
 
divide(580, 34);
 
}
 
/**
* Divides <code>dividend</code> by <code>divisor</code> using the Egyptian Division-Algorithm and prints the
* result to the console
*
* @param dividend
* @param divisor
*/

public static void divide(int dividend, int divisor) {
 
List<Integer> powersOf2 = new ArrayList<>();
List<Integer> doublings = new ArrayList<>();
 
//populate the powersof2- and doublings-columns
int line = 0;
while ((Math.pow(2, line) * divisor) <= dividend) { //<- could also be done with a for-loop
int powerOf2 = (int) Math.pow(2, line);
powersOf2.add(powerOf2);
doublings.add(powerOf2 * divisor);
line++;
}
 
int answer = 0;
int accumulator = 0;
 
//Consider the rows in reverse order of their construction (from back to front of the List<>s)
for (int i = powersOf2.size() - 1; i >= 0; i--) {
if (accumulator + doublings.get(i) <= dividend) {
accumulator += doublings.get(i);
answer += powersOf2.get(i);
}
}
 
System.out.println(String.format("%d, remainder %d", answer, dividend - accumulator));
}
}
 
 
Output:
17, remainder 2

JavaScript[edit]

ES6[edit]

(() => {
'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)
);
})();
Output:
[17,2]

Julia[edit]

Works with: Julia version 0.6
function egyptiandivision(dividend::Int, divisor::Int)
N = 64
powers = Vector{Int}(N)
doublings = Vector{Int}(N)
 
ind = 0
for i in 0:N-1
powers[i+1] = 1 << i
doublings[i+1] = divisor << i
if doublings[i+1] > dividend ind = i-1; break end
end
 
ans = acc = 0
for i in ind:-1:0
if acc + doublings[i+1] ≤ dividend
acc += doublings[i+1]
ans += powers[i+1]
end
end
 
return ans, dividend - acc
end
 
q, r = egyptiandivision(580, 34)
println("580 ÷ 34 = $q (remains $r)")
 
using Base.Test
 
@testset "Equivalence to divrem builtin function" begin
for x in rand(1:100, 100), y in rand(1:100, 10)
@test egyptiandivision(x, y) == divrem(x, y)
end
end
Output:
580 ÷ 34 = 17 (remains 2)
Test Summary:                          | Pass  Total
Equivalence to divrem builtin function | 1000   1000

Kotlin[edit]

// version 1.1.4
 
data class DivMod(val quotient: Int, val remainder: Int)
 
fun egyptianDivide(dividend: Int, divisor: Int): DivMod {
require (dividend >= 0 && divisor > 0)
if (dividend < divisor) return DivMod(0, dividend)
val powersOfTwo = mutableListOf(1)
val doublings = mutableListOf(divisor)
var doubling = divisor
while (true) {
doubling *= 2
if (doubling > dividend) break
powersOfTwo.add(powersOfTwo[powersOfTwo.lastIndex] * 2)
doublings.add(doubling)
}
var answer = 0
var accumulator = 0
for (i in doublings.size - 1 downTo 0) {
if (accumulator + doublings[i] <= dividend) {
accumulator += doublings[i]
answer += powersOfTwo[i]
if (accumulator == dividend) break
}
}
return DivMod(answer, dividend - accumulator)
}
 
fun main(args: Array<String>) {
val dividend = 580
val divisor = 34
val (quotient, remainder) = egyptianDivide(dividend, divisor)
println("$dividend divided by $divisor is $quotient with remainder $remainder")
}
Output:
580 divided by 34 is 17 with remainder 2

Perl 6[edit]

Works with: Rakudo version 2017.07

Normal version[edit]

Only works with positive real numbers, not negative or complex.

sub egyptian-divmod (Real $dividend is copy where * >= 0, Real $divisor where * > 0) {
my $accumulator = 0;
([1, $divisor], { [.[0] + .[0], .[1] + .[1]] }^ *.[1] > $dividend)
.reverse.map: { $dividend -= .[1], $accumulator += .[0] if $dividend >= .[1] }
$accumulator, $dividend;
}
 
#TESTING
for 580,34, 578,34, 7532795332300578,235117 -> $n, $d {
printf "%s divmod %s = %s remainder %s\n",
$n, $d, |egyptian-divmod( $n, $d )
}
Output:
580 divmod 34 = 17 remainder 2
578 divmod 34 = 17 remainder 0
7532795332300578 divmod 235117 = 32038497141 remainder 81

More "Egyptian" version[edit]

As a preceding version was determined to be "let's just say ... not Egyptian" we submit an alternate which is hopefully more "Egyptian". Now only handles positive Integers up to 10 million, mostly due to limitations on Egyptian notation for numbers.

Note: if the below is just a mass of "unknown glyph" boxes, try installing Googles free Noto Sans Egyptian Hieroglyphs font.

This is intended to be humorous and should not be regarded as good (or even sane) programming practice. That being said, 𓂽 & 𓂻 really are the ancient Egyptian symbols for addition and subtraction, and the Egyptian number notation is as accurate as possible. Everything else owes more to whimsy than rigor.

my (\𓄤, \𓄊, \𓎆, \𓄰) = (0, 1, 10, 10e7);
sub infix:<𓂽> { $^𓃠 + $^𓃟 }
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 "%s divmod %s = %s remainder %s =OR= %s 𓅓 %s = %s remainder %s\n",
𓃾, 𓆙, |(𓃾 𓅓 𓆙), (𓃾, 𓆙, |(𓃾 𓅓 𓆙))».&𓁶;
}
Output:
580 divmod 34 = 17 remainder 2 =OR= 𓍦𓎍 𓅓 𓎐𓏽 = 𓎆𓐀 remainder 𓏻
578 divmod 34 = 17 remainder 0 =OR= 𓍦𓎌𓐁 𓅓 𓎐𓏽 = 𓎆𓐀 remainder 𓄤
2300578 divmod 23517 = 97 remainder 19429 =OR= 𓁨𓁨𓆐𓆐𓆐𓍦𓎌𓐁 𓅓 𓂮𓆾𓍦𓎆𓐀 = 𓎎𓐀 remainder 𓂭𓇄𓍥𓎏𓐂

PicoLisp[edit]

(seed (in "/dev/urandom" (rd 8)))
 
(de divmod (Dend Disor)
(cons (/ Dend Disor) (% Dend Disor)) )
(de egyptian (Dend Disor)
(let
(P 0
D Disor
S
(make
(while (>= Dend (setq @@ (+ D D)))
(yoke
(cons
(** 2 (swap 'P (inc P)))
(swap 'D @@) ) ) ) )
P (** 2 P) )
(mapc
'((L)
(and
(>= Dend (+ D (cdr L)))
(inc 'P (car L))
(inc 'D (cdr L)) ) )
S )
(cons P (abs (- Dend D))) ) )
(for N 1000
(let (A (rand 1 1000) B (rand 1 A))
(test (divmod A B) (egyptian A B)) ) )
(println (egyptian 580 34))
Output:
(17 . 2)

Python[edit]

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))

Sample output

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

Racket[edit]

#lang racket
 
(define (quotient/remainder-egyptian dividend divisor (trace? #f))
(define table
(for*/list ((power_of_2 (sequence-map (curry expt 2) (in-naturals)))
(doubling (in-value (* divisor power_of_2)))
#:break (> doubling dividend))
(list power_of_2 doubling)))
 
(when trace?
(displayln "Table\npow_2\tdoubling")
(for ((row table)) (printf "~a\t~a~%" (first row) (second row))))
 
(define-values (answer accumulator)
(for*/fold ((answer 0) (accumulator 0))
((row (reverse table))
(acc′ (in-value (+ accumulator (second row)))))
(when trace? (printf "row:~a\tans/acc:~a ~a\t" row answer accumulator))
(cond
[(<= acc′ dividend)
(define ans′ (+ answer (first row)))
(when trace? (printf "~a <= ~a -> ans′/acc′:~a ~a~%" acc′ dividend ans′ acc′))
(values ans′ acc′)]
[else
(when trace? (printf "~a > ~a [----]~%" acc′ dividend))
(values answer accumulator)])))
 
(values answer (- dividend accumulator)))
 
(module+ test
(require rackunit)
(let-values (([q r] (quotient/remainder-egyptian 580 34)))
(check-equal? q 17)
(check-equal? r 2))
 
(let-values (([q r] (quotient/remainder-egyptian 192 3)))
(check-equal? q 64)
(check-equal? r 0)))
 
(module+ main
(quotient/remainder-egyptian 580 34 #t))
Output:
Table
pow_2	doubling
1	34
2	68
4	136
8	272
16	544
row:(16 544)	ans/acc:0 0	544 <= 580 -> ans′/acc′:16 544
row:(8 272)	ans/acc:16 544	816 > 580 [----]
row:(4 136)	ans/acc:16 544	680 > 580 [----]
row:(2 68)	ans/acc:16 544	612 > 580 [----]
row:(1 34)	ans/acc:16 544	578 <= 580 -> ans′/acc′:17 578
17
2

REXX[edit]

Only addition and subtraction is used in this version of the Egyptian division method.

/*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 Egyptina Division function*/
parse var result q r /*extract the quotient & the 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 until 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 /*#*/
acc=0; ans=0 /*initialize accumulator & answer to 0 */
do s=# by -1 for # /* [↓] process the table "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. */
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

Ring[edit]

 
load "stdlib.ring"
 
table = newlist(32, 2)
dividend = 580
divisor = 34
 
i = 1
table[i][1] = 1
table[i][2] = divisor
 
while table[i] [2] < dividend
i = i + 1
table[i][1] = table[i -1] [1] * 2
table[i][2] = table[i -1] [2] * 2
end
i = i - 1
answer = table[i][1]
accumulator = table[i][2]
 
while i > 1
i = i - 1
if table[i][2]+ accumulator <= dividend
answer = answer + table[i][1]
accumulator = accumulator + table[i][2]
ok
end
 
see string(dividend) + " divided by " + string(divisor) + " using egytian division" + nl
see " returns " + string(answer) + " mod(ulus) " + string(dividend-accumulator)
 

Output:

580 divided by 34 using egytian division
returns 17 mod(ulus) 2

Ruby[edit]

def egyptian_divmod(dividend, divisor)
table = [[1, divisor]]
table << table.last.map{|e| e*2} while table.last.first * 2 <= dividend
answer, accumulator = 0, 0
table.reverse_each do |pow, double|
if accumulator + double <= dividend
accumulator += double
answer += pow
end
end
[answer, dividend - accumulator]
end
 
puts "Quotient = %s Remainder = %s" % egyptian_divmod(580, 34)
 
Output:
Quotient = 17 Remainder = 2

zkl[edit]

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);
}
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)));
}
Output:
580 % 34 = L(17,2)
580 % 17 = L(34,2)
578 % 34 = L(17,0)
7532795332300578 % 235117 = L(32038497141,81)