Egyptian division: Difference between revisions
no edit summary
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
No edit summary |
||
| (23 intermediate revisions by 16 users not shown) | |||
Line 310:
;Related tasks:
:* [[Egyptian_fractions|Egyptian fractions]]
:* [[Ethiopian_multiplication|Ethiopian multiplication]]
;References:
Line 319:
{{trans|Python}}
<
assert(divisor != 0)
V (pwrs, dbls) = ([1], [divisor])
Line 336:
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))</
{{out}}
Line 344:
=={{header|Action!}}==
<
PROC EgyptianDivision(CARD dividend,divisor Answer POINTER res)
Line 382:
EgyptianDivision(dividend,divisor,res)
PrintF("%U / %U = %U reminder %U",dividend,divisor,res.result,res.reminder)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Egyptian_division.png Screenshot from Atari 8-bit computer]
Line 391:
=={{header|Ada}}==
<syntaxhighlight lang="ada">
with Ada.Text_IO;
Line 422:
Ada.Text_IO.put_line ("Quotient="&q'Img & " Remainder="&r'img);
end Egyptian_Division;
</syntaxhighlight>
{{Out}}
<pre>Quotient= 17 Remainder= 2</pre>
=={{header|ALGOL 68}}==
<
# 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 #
Line 464:
egyptian division( 580, 34, quotient, remainder );
print( ( "580 divided by 34 is: ", whole( quotient, 0 ), " remainder: ", whole( remainder, 0 ), newline ) )
END</
{{out}}
<pre>
Line 473:
Unfold to derive successively doubled rows, fold to sum quotient and derive remainder
<
-- eqyptianQuotRem :: Int -> Int -> (Int, Int)
Line 565:
end tell
return xs
end unfoldr</
{{Out}}
<pre>{17, 2}</pre>
Line 571:
=={{header|Arturo}}==
<
ensure -> and? dividend >= 0
divisor > 0
Line 607:
[quotient, remainder]: egyptianDiv dividend divisor
print [dividend "divided by" divisor "is" quotient "with remainder" remainder]</
{{out}}
Line 614:
=={{header|AutoHotkey}}==
<
divisor := 34
Line 635:
obj.pop() ; remove current row
}
MsgBox % divident "/" divisor " = " answer ( divident-accumulator > 0 ? " r" divident-accumulator : "")</
Outputs:<pre>580/34 = 17 r2</pre>
=={{header|
==={{header|ANSI BASIC}}===
{{trans|QBasic}} But the arrays are subscripted from 0.
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">
100 REM Egyptian division
110 DIM Table(0 TO 31, 0 TO 1)
120 LET Dividend = 580
130 LET Divisor = 34
140 REM ** Division
150 LET I = 0
160 LET Table(I, 0) = 1
170 LET Table(I, 1) = Divisor
180 DO WHILE Table(I, 1) < Dividend
190 LET I = I + 1
200 LET Table(I, 0) = Table(I - 1, 0) * 2
210 LET Table(I, 1) = Table(I - 1, 1) * 2
220 LOOP
230 LET I = I - 1
240 LET Answer = Table(I, 0)
250 LET Accumulator = Table(I, 1)
260 DO WHILE I > 0
270 LET I = I - 1
280 IF Table(I, 1) + Accumulator <= Dividend THEN
290 LET Answer = Answer + Table(I, 0)
300 LET Accumulator = Accumulator + Table(I, 1)
310 END IF
320 LOOP
330 REM ** Results
340 PRINT Dividend; "divided by"; Divisor; "using Egytian division";
350 PRINT " returns"; Answer; "remainder"; Dividend - Accumulator
360 END
</syntaxhighlight>
{{out}}
<pre>
580 divided by 34 using Egytian division returns 17 remainder 2
</pre>
==={{header|Applesoft BASIC}}===
The [[#MSX_BASIC|MSX BASIC]] solution works without any changes.
==={{header|BaCon}}===
<syntaxhighlight lang="c">'---Ported from the c code example to BaCon by bigbass
'==================================================================================
Line 701 ⟶ 740:
EGYPTIAN_DIVISION(580,34,0)
EGYPTIAN_DIVISION(580,34,1)</syntaxhighlight>
==={{header|BASIC256}}===
<syntaxhighlight lang="vb">arraybase 1
dim table(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 while
i = i - 1
answer = table[i, 1]
accumulator = table[i, 2]
while i > 1
i = i - 1
if table[i, 2]+ accumulator <= dividend then
answer = answer + table[i, 1]
accumulator = accumulator + table[i, 2]
end if
end while
print string(dividend); " divided by "; string(divisor); " using Egytian division";
print " returns "; string(answer); " mod(ulus) "; string(dividend-accumulator)</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Chipmunk Basic}}===
{{trans|QBasic}}
{{works with|Chipmunk Basic|3.6.4}}
{{works with|QBasic}}
<syntaxhighlight lang="vbnet">100 dim table(32,2)
110 let dividend = 580
120 let divisor = 34
130 let i = 1
140 let table(i,1) = 1
150 let table(i,2) = divisor
160 do while table(i,2) < dividend
170 let i = i+1
180 let table(i,1) = table(i-1,1)*2
190 let table(i,2) = table(i-1,2)*2
200 loop
210 let i = i-1
220 let answer = table(i,1)
230 let accumulator = table(i,2)
240 do while i > 1
250 let i = i-1
260 if table(i,2)+accumulator <= dividend then
270 let answer = answer+table(i,1)
280 let accumulator = accumulator+table(i,2)
290 endif
300 loop
310 print str$(dividend);" divided by ";str$(divisor);" using Egytian division";
320 print " returns ";str$(answer);" mod(ulus) ";str$(dividend-accumulator)
330 end</syntaxhighlight>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' 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</syntaxhighlight>
{{out}}
<pre>580 divided by 34 using Egytian division returns 17 mod(ulus) 2</pre>
==={{header|GW-BASIC}}===
{{trans|QBasic}}
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
{{works with|Chipmunk Basic}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">100 CLS
110 DIM T(32,2)
120 LET A = 580
130 LET B = 34
140 LET I = 1
150 LET T(I,1) = 1
160 LET T(I,2) = B
170 WHILE T(I,2) < A
180 LET I = I+1
190 LET T(I,1) = T(I-1,1)*2
200 LET T(I,2) = T(I-1,2)*2
210 WEND
220 LET I = I-1
230 LET R = T(I,1)
240 LET S = T(I,2)
250 WHILE I > 1
260 LET I = I-1
270 IF T(I,2)+S <= A THEN LET R = R+T(I,1): LET S = S+T(I,2)
280 WEND
290 PRINT STR$(A);" divided by ";STR$(B);" using Egytian division";
300 PRINT " returns ";STR$(R);" mod(ulus) ";STR$(A-S)
310 END</syntaxhighlight>
==={{header|Just BASIC}}===
Same code as [[#QBasic|QBasic]]
==={{header|Minimal BASIC}}===
{{trans|ANSI BASIC}}
{{works with|BASICA}}
{{works with|Commodore BASIC|3.5}}
{{works with|MSX BASIC|2.1}}
<syntaxhighlight lang="basic">
10 REM Egyptian division
20 DIM T(31,1)
30 REM D1 - dividend; D2 - divisor
40 LET D1 = 580
50 LET D2 = 34
60 REM ** Division
70 LET I = 0
80 LET T(I,0) = 1
90 LET T(I,1) = D2
100 IF T(I,1) >= D1 THEN 160
110 LET I = I+1
120 LET T(I,0) = T(I-1,0)*2
130 LET T(I,1) = T(I-1,1)*2
140 GOTO 100
150 REM A - answer; C - accumulator
160 LET I = I-1
170 LET A = T(I,0)
180 LET C = T(I,1)
190 IF I <= 0 THEN 250
200 LET I = I-1
210 IF T(I,1)+C > D1 THEN 190
220 LET A = A+T(I,0)
230 LET C = C+T(I,1)
240 GOTO 190
250 REM ** Results
260 PRINT D1; "divided by"; D2;
270 PRINT "using Egyptian division";
280 PRINT " returns"; A; "remainder"; D1-C
290 END
</syntaxhighlight>
{{out}}
<pre>
580 divided by 34 using Egyptian division returns 17 remainder 2
</pre>
==={{header|MSX Basic}}===
{{works with|MSX BASIC|any}}
{{works with|Applesoft BASIC}}
{{works with|GW-BASIC}}
{{works with|Chipmunk Basic}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">110 DIM T(32,2)
120 A = 580
130 B = 34
140 I = 1
150 T(I,1) = 1
160 T(I,2) = B
170 IF T(I,2) < A THEN I = I+1 : T(I,1) = T(I-1,1)*2 : T(I,2) = T(I-1,2)*2
180 IF T(I,2) >= A THEN GOTO 200
190 GOTO 170
200 I = I-1
210 R = T(I,1)
220 S = T(I,2)
230 IF I > 1 THEN I = I-1 : IF T(I,2)+S <= A THEN R = R+T(I,1): S = S+T(I,2)
240 IF I <= 1 THEN GOTO 260
250 GOTO 230
260 PRINT STR$(A);" divided by ";STR$(B);" using Egytian division";
270 PRINT " returns ";STR$(R);" mod(ulus) ";STR$(A-S)
280 END</syntaxhighlight>
==={{header|PureBasic}}===
<syntaxhighlight lang="PureBasic">OpenConsole()
Dim table.i(32, 2)
dividend.i = 580
divisor.i = 34
i.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:
answer = answer + table(i, 1)
accumulator = accumulator + table(i, 2)
EndIf
Wend
Print(Str(dividend) + " divided by " + Str(divisor) + " using Egytian division")
PrintN(" returns " + Str(answer) + " mod(ulus) " + Str(dividend-accumulator))
Input()
CloseConsole()</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
{{works with|Run BASIC}}
{{works with|Just BASIC}}
{{works with|Liberty BASIC}}
<syntaxhighlight lang="qbasic">DIM table(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
WEND
i = i - 1
answer = table(i, 1)
accumulator = table(i, 2)
WHILE i > 1
i = i - 1
IF table(i, 2) + accumulator <= dividend THEN
answer = answer + table(i, 1)
accumulator = 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)</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Run BASIC}}===
Same code as [[#QBasic|QBasic]]
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">DIM table(32, 2)
LET dividend = 580
LET divisor = 34
LET i = 1
LET table(i, 1) = 1
LET table(i, 2) = divisor
DO WHILE table(i, 2) < dividend
LET i = i+1
LET table(i, 1) = table(i-1, 1)*2
LET table(i, 2) = table(i-1, 2)*2
LOOP
LET i = i-1
LET answer = table(i, 1)
LET accumulator = table(i, 2)
DO WHILE i > 1
LET i = i-1
IF table(i, 2)+accumulator <= dividend THEN
LET answer = answer+table(i, 1)
LET accumulator = accumulator+table(i, 2)
END IF
LOOP
PRINT STR$(dividend); " divided by "; STR$(divisor); " using Egytian division";
PRINT " returns "; STR$(answer); " mod(ulus) "; STR$(dividend-accumulator)
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Visual Basic .NET}}===
{{trans|D}}
<syntaxhighlight lang="vbnet">Module Module1
Function EgyptianDivision(dividend As ULong, divisor As ULong, ByRef remainder As ULong) As ULong
Const SIZE = 64
Dim powers(SIZE) As ULong
Dim doublings(SIZE) As ULong
Dim i = 0
While i < SIZE
powers(i) = 1 << i
doublings(i) = divisor << i
If doublings(i) > dividend Then
Exit While
End If
i = i + 1
End While
Dim answer As ULong = 0
Dim accumulator As ULong = 0
i = i - 1
While i >= 0
If accumulator + doublings(i) <= dividend Then
accumulator += doublings(i)
answer += powers(i)
End If
i = i - 1
End While
remainder = dividend - accumulator
Return answer
End Function
Sub Main(args As String())
If args.Length < 2 Then
Dim name = Reflection.Assembly.GetEntryAssembly().Location
Console.Error.WriteLine("Usage: {0} dividend divisor", IO.Path.GetFileNameWithoutExtension(name))
Return
End If
Dim dividend = CULng(args(0))
Dim divisor = CULng(args(1))
Dim remainder As ULong
Dim ans = EgyptianDivision(dividend, divisor, remainder)
Console.WriteLine("{0} / {1} = {2} rem {3}", dividend, divisor, ans, remainder)
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>580 / 34 = 17 rem 2</pre>
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "Egyptian division"
VERSION "0.0000"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
DIM T[32,2]
A = 580
B = 34
I = 1
T[I,1] = 1
T[I,2] = B
DO WHILE T[I,2] < A
INC I
T[I,1] = T[I-1,1]*2
T[I,2] = T[I-1,2]*2
LOOP
DEC I
R = T[I,1]
S = T[I,2]
DO WHILE I > 1
DEC I
IF T[I,2]+S <= A THEN
R = R+T[I,1]
S = S+T[I,2]
END IF
LOOP
PRINT A;" divided by";B;" using Egytian division";
PRINT " returns";R;" mod(ulus)"; A-S
END FUNCTION
END PROGRAM</syntaxhighlight>
==={{header|Yabasic}}===
<syntaxhighlight lang="vb">dim table(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
wend
i = i - 1
answer = table(i, 1)
accumulator = table(i, 2)
while i > 1
i = i - 1
if table(i, 2)+ accumulator <= dividend then
answer = answer + table(i, 1)
accumulator = accumulator + table(i, 2)
fi
wend
print str$(dividend), " divided by ", str$(divisor), " using Egytian division";
print " returns ", str$(answer), " mod(ulus) ", str$(dividend-accumulator)</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|C}}==
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>
Line 757 ⟶ 1,217:
go(580, 32);
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
<
using System;
using System.Collections;
Line 914 ⟶ 1,374:
}
}
</syntaxhighlight>
{{out| Program Input and Output : Instead of bold and strikeout text format, numbers are represented in different color}}
<pre>
Line 950 ⟶ 1,410:
=={{header|C++}}==
{{trans|C}}
<
#include <iostream>
Line 1,007 ⟶ 1,467:
return 0;
}</
{{out}}
<pre>580 / 34 = 17 remainder 2</pre>
Line 1,013 ⟶ 1,473:
=={{header|Common Lisp}}==
<
(defun egyptian-division (dividend divisor)
(let* ((doublings (reverse (loop for n = divisor then (* 2 n)
Line 1,030 ⟶ 1,490:
do (incf answer p)
(incf accumulator d))))
</syntaxhighlight>
{{out}}
Line 1,040 ⟶ 1,500:
=={{header|D}}==
<syntaxhighlight lang="d">
import std.stdio;
Line 1,099 ⟶ 1,559:
assert(remainder == 2);
}
</syntaxhighlight>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
Line 1,105 ⟶ 1,565:
{{libheader| System.Console}}Thanks for JensBorrisholt [https://github.com/JensBorrisholt/DelphiConsole].
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Egyptian_division;
Line 1,254 ⟶ 1,714:
Console.Write('Press any key to continue . . . ');
Console.ReadKey(true);
end.</
{{out}}<pre>
Line 1,284 ⟶ 1,744:
Press any key to continue . . .</pre>
=={{header|EasyLang}}==
{{trans|Phix}}
<syntaxhighlight>
proc egyptdiv a b . .
p2 = 1
dbl = b
while dbl <= a
p2s[] &= p2
dbls[] &= dbl
dbl *= 2
p2 *= 2
.
for i = len p2s[] downto 1
if acc + dbls[i] <= a
acc += dbls[i]
ans += p2s[i]
.
.
print a & " / " & b & " = " & ans & " R " & abs (acc - a)
.
egyptdiv 580 34
</syntaxhighlight>
=={{header|Erlang}}==
<
-export([ediv/2]).
Line 1,301 ⟶ 1,784:
accumulate(N, [T|Ts], [D|Ds], Q, C) when (C + D) =< N -> accumulate(N, Ts, Ds, Q+T, C+D);
accumulate(N, [_|Ts], [_|Ds], Q, C) -> accumulate(N, Ts, Ds, Q, C).
</syntaxhighlight>
{{out}}
<pre>
Line 1,309 ⟶ 1,792:
=={{header|F_Sharp|F#}}==
<
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)
</syntaxhighlight>
Which may be used:
<
let (n,g) = egyptianDivision 580 34
printfn "580 divided by 34 is %d remainder %d" g n
</syntaxhighlight>
{{out}}
<pre>
Line 1,326 ⟶ 1,809:
=={{header|Factor}}==
{{works with|Factor|0.98}}
<
IN: rosetta-code.egyptian-division
Line 1,344 ⟶ 1,827:
} 2cleave ;
580 34 ediv "580 divided by 34 is %d remainder %d\n" printf</
{{out}}
<pre>
Line 1,351 ⟶ 1,834:
=={{header|Forth}}==
<syntaxhighlight lang="forth">
variable tab-end
Line 1,375 ⟶ 1,858:
: .egypt ( m n -- )
cr 2dup swap . ." divided by " . ." is " e/mod swap . ." remainder " . ;
</syntaxhighlight>
{{Out}}
<pre>
Line 1,381 ⟶ 1,864:
580 divided by 34 is 17 remainder 2 ok
</pre>
=={{header|Go}}==
{{trans|Kotlin}}
<
import "fmt"
Line 1,469 ⟶ 1,909:
quotient, remainder := egyptianDivide(dividend, divisor)
fmt.Println(dividend, "divided by", divisor, "is", quotient, "with remainder", remainder)
}</
{{out}}
Line 1,478 ⟶ 1,918:
=={{header|Groovy}}==
{{trans|Java}}
<
/**
* Runs the method and divides 580 by 34
Line 1,521 ⟶ 1,961:
println(String.format("%d, remainder %d", answer, dividend - accumulator))
}
}</
{{out}}
<pre>17, remainder 2</pre>
Line 1,527 ⟶ 1,967:
=={{header|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.
<
egyptianQuotRem :: Integer -> Integer -> (Integer, Integer)
Line 1,540 ⟶ 1,980:
main :: IO ()
main = print $ egyptianQuotRem 580 34</
{{Out}}
<pre>(17,2)</pre>
Line 1,546 ⟶ 1,986:
We can make the process of calculation more visible by adding a trace layer:
<
import Debug.Trace (trace)
Line 1,577 ⟶ 2,017:
main :: IO ()
main = print $ egyptianQuotRem 580 34</
{{Out}}
<pre>Number pair unfolded to series of doubling rows:
Line 1,591 ⟶ 2,031:
Another approach, using lazy lists and foldr:
<
powers = doublings 1
Line 1,602 ⟶ 2,042:
main :: IO ()
main = print $ egy 580 34</
{{Out}}
<pre>17</pre>
Line 1,610 ⟶ 2,050:
Implementation:
<
ansacc=: 1 }. (] + [ * {.@[ >: {:@:+)/@([,.doublings)
egydiv=: (0,[)+1 _1*ansacc</
Task example:
<
1 34
2 68
Line 1,625 ⟶ 2,065:
17 578
580 egydiv 34
17 2</
Notes:
Line 1,634 ⟶ 2,074:
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
Line 1,687 ⟶ 2,127:
}
</syntaxhighlight>
{{Out}}
<pre>17, remainder 2</pre>
Line 1,693 ⟶ 2,133:
=={{header|JavaScript}}==
===ES6===
<
'use strict';
Line 1,781 ⟶ 2,221:
// MAIN ---
return main();
})();</
{{Out}}
<pre>[17,2]</pre>
=={{header|
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq, and with fq.'''
<syntaxhighlight lang=jq>
def egyptianDivide($dividend; $divisor):
if ($dividend < 0 or $divisor <= 0) then "egyptianDivide: invalid argument(s)" | error
elif ($dividend < $divisor) then [0, $dividend]
else
{ powersOfTwo: [1],
doublings: [$divisor],
doubling: (2 * $divisor)
}
| until(.doubling > $dividend;
.powersOfTwo += [.powersOfTwo[-1]*2]
| .doublings += [.doubling]
| .doubling *= 2 )
| .answer = 0
| .accumulator = 0
| .i = (.doublings|length)-1
| until( .i < 0 or .accumulator == $dividend;
if (.accumulator + .doublings[.i] <= $dividend)
then .accumulator += .doublings[.i]
| .answer += .powersOfTwo[.i]
else .
end
| .i += -1)
| [.answer, $dividend - .accumulator]
end;
def task($dividend; $divisor):
egyptianDivide($dividend; $divisor)
| "\($dividend) ÷ \($divisor) = \(.[0]) with remainder \(.[1]).";
task(580; 34)
</syntaxhighlight>
{{output}}
<pre>
580 ÷ 34 = 17 with remainder 2.
</pre>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight lang="julia">function egyptian_divrem(dividend, divisor)
answer = accumulator = 0
function row(powers_of2, doublings)
if dividend > doublings
row(2powers_of2, 2doublings)
if accumulator + doublings ≤ dividend
answer += powers_of2
accumulator += doublings
end
end
end
row(1, divisor)
end
egyptian_divrem(580, 34)</syntaxhighlight>
{{out}}
<pre>
=={{header|Kotlin}}==
<
data class DivMod(val quotient: Int, val remainder: Int)
Line 1,860 ⟶ 2,322:
val (quotient, remainder) = egyptianDivide(dividend, divisor)
println("$dividend divided by $divisor is $quotient with remainder $remainder")
}</
{{out}}
Line 1,866 ⟶ 2,328:
580 divided by 34 is 17 with remainder 2
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def doublings
{def doublings.loop
{lambda {:a :c}
{if {> {A.get 1 {A.last :c}} :a}
then {A.sublast! :c}
else {doublings.loop
:a
{A.addlast! {A.new {* 2 {A.get 0 {A.last :c}}}
{* 2 {A.get 1 {A.last :c}}}} :c}} }}}
{lambda {:a :b}
{doublings.loop :a {A.new {A.new 1 :b}}} }}
-> doublings
divide
-> {def divide
{def divide.loop
{lambda {:a :b :table :last :i}
{if {< {+ :last {A.get 1 {A.get :i :table}}} :a}
then {A.new {+ {* {A.get 0 {A.last :table}} 1} 1}
{- :a {+ :last {A.get 1 {A.get :i :table}}}}}
else {divide.loop :a :b :table :last {- :i 1} }}}}
{lambda {:a :b}
{let { {:a :a} {:b :b}
{:table {doublings :a :b}}
} {divide.loop :a :b :table
{A.get 1 {A.last :table}}
{- {A.length :table} 1} }}}}
{divide 580 34}
-> [17,2] // 580 = 17*34+2
{divide 100 3}
-> [33,1] // 100 = 3*33+1
{divide 7 2}
-> [3,1] // 7 = 2*3+1
</syntaxhighlight>
=={{header|Lua}}==
{{trans|Python}}
<
local pwrs, dbls = {1}, {divisor}
while dbls[#dbls] <= dividend do
Line 1,889 ⟶ 2,391:
local i, j = 580, 34
local d, m = egyptian_divmod(i, j)
print(i.." divided by "..j.." using the Egyptian method is "..d.." remainder "..m)</
{{out}}
<pre>580 divided by 34 using the Egyptian method is 17 remainder 2</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
EgyptianDivide[dividend_, divisor_] := Module[{table, i, answer, accumulator},
table = {{1, divisor}};
Line 1,915 ⟶ 2,417:
{answer, dividend - accumulator}
]
EgyptianDivide[580, 34]</
{{out}}
<pre>{17, 2}</pre>
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,ReadChar;
Line 1,962 ⟶ 2,464:
ReadChar
END EgyptianDivision.</
=={{header|Nim}}==
<
func egyptianDivision(dividend, divisor: int): tuple[quotient, remainder: int] =
Line 1,995 ⟶ 2,497:
let divisor = 34
var (quotient, remainder) = egyptianDivision(dividend, divisor)
echo fmt"{dividend} divided by {divisor} is {quotient} with remainder {remainder}"</
{{out}}
<pre>
580 divided by 34 is 17 with remainder 2
</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let egypt_div x y =
let rec table p d lst =
if d > x
then lst
else table (p + p) (d + d) ((p, d) :: lst)
in
let consider (q, a) (p, d) =
if a + d > x
then q, a
else q + p, a + d
in
List.fold_left consider (0, 0) (table 1 y [])</syntaxhighlight>
{{out}}
<pre>
# egypt_div 580 34 ;;
- : int * int = (17, 578)
</pre>
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
myrow(powers_of2, doublings) =
{
if (dividend > doublings,
myrow(2 * powers_of2, 2 * doublings);
if (accumulator + doublings <= dividend,
answer += powers_of2;
accumulator += doublings;
);
);
};
egyptian_divrem(dividend, divisor) =
{
local(answer, accumulator, row);
answer = 0;
accumulator = 0;
myrow(1, divisor);
[answer, dividend - accumulator];
}
divisor=34;
dividend=580;
print1(egyptian_divrem(dividend, divisor));
</syntaxhighlight>
{{out}}
<pre>
[17, 2]
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<
my($dividend, $divisor) = @_;
die "Invalid divisor" if $divisor <= 0;
Line 2,022 ⟶ 2,576:
my($n,$d) = @$_;
printf "Egyption divmod %s %% %s = %s remainder %s\n", $n, $d, egyptian_divmod( $n, $d )
}</
{{out}}
<pre>Egyption divmod 580 % 34 = 17 remainder 2
Line 2,029 ⟶ 2,583:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">egyptian_division</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">dividend</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span>
Line 2,051 ⟶ 2,605:
<span style="color: #000000;">egyptian_division</span><span style="color: #0000FF;">(</span><span style="color: #000000;">580</span><span style="color: #0000FF;">,</span><span style="color: #000000;">34</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 2,058 ⟶ 2,612:
=={{header|PicoLisp}}==
<
(de divmod (Dend Disor)
Line 2,085 ⟶ 2,639:
(let (A (rand 1 1000) B (rand 1 A))
(test (divmod A B) (egyptian A B)) ) )
(println (egyptian 580 34))</
{{out}}
Line 2,092 ⟶ 2,646:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<
powers2_multiples(Dividend, [1], Powers, [Divisor], Multiples),
accumulate(Dividend, Powers, Multiples, 0, Quotient, 0, Acc),
Line 2,123 ⟶ 2,677:
main:-
test_egyptian_divide(580, 34).</
{{out}}
Line 2,132 ⟶ 2,686:
=={{header|Python}}==
===Idiomatic=== <!-- When compared to a Haskell translation -->
<
def egyptian_divmod(dividend, divisor):
Line 2,154 ⟶ 2,708:
i, j = 580, 34
print(f'{i} divided by {j} using the Egyption method is %i remainder %i'
% egyptian_divmod(i, j))</
'''Sample output'''
Line 2,168 ⟶ 2,722:
{{Trans|Haskell}}
<
from functools import reduce
Line 2,251 ⟶ 2,805:
# MAIN ----------------------------------------------------
if __name__ == '__main__':
main()</
{{Out}}
<pre>(17, 2)</pre>
Line 2,257 ⟶ 2,811:
=={{header|Quackery}}==
<
[ $ "Cannot divide by zero."
fail ]
Line 2,296 ⟶ 2,850:
say "." ] is task ( n n --> )
580 34 task</
{{out}}
<pre>580 divided by 34 is 17 remainder 2.</pre>
=={{header|R}}==
<syntaxhighlight lang="r">Egyptian_division <- function(num, den){
pow2 = 0
row = 1
Table = data.frame(powers_of_2 = 2^pow2,
doubling = den)
while(Table$doubling[nrow(Table)] < num){
row = row + 1
pow2 = pow2 + 1
Table[row, 1] <- 2^pow2
Table[row, 2] <- 2^pow2 * den
}
Table <- Table[-nrow(Table),]
#print(Table) to see the table
answer <- 0
accumulator <- 0
for (i in nrow(Table):1) {
if (accumulator + Table$doubling[i] <= num) {
accumulator <- accumulator + Table$doubling[i]
answer <- answer + Table$powers_of_2[i]
}
}
remainder = abs(accumulator - num)
message(paste0("Answer is ", answer, ", remainder ", remainder))
}
Egyptian_division(580, 34)
Egyptian_division(300, 2)
</syntaxhighlight>
{{out}}
<pre>
Answer is 17, remainder 2
Answer is 150, remainder 0
</pre>
=={{header|Racket}}==
<
(define (quotient/remainder-egyptian dividend divisor (trace? #f))
Line 2,343 ⟶ 2,943:
(module+ main
(quotient/remainder-egyptian 580 34 #t))</
{{out}}
Line 2,367 ⟶ 2,967:
===Normal version===
Only works with positive real numbers, not negative or complex.
<syntaxhighlight lang="raku"
my $accumulator = 0;
([1, $divisor], { [.[0] + .[0], .[1] + .[1]] } … ^ *.[1] > $dividend)
Line 2,378 ⟶ 2,978:
printf "%s divmod %s = %s remainder %s\n",
$n, $d, |egyptian-divmod( $n, $d )
}</
{{out}}
<pre>580 divmod 34 = 17 remainder 2
Line 2,387 ⟶ 2,987:
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 [https://www.google.com/get/noto/help/install/ installing] Googles free [https://
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.
<syntaxhighlight lang="raku"
sub infix:<𓂽> { $^𓃠 + $^𓃟 }
sub infix:<𓂻> { $^𓃲 - $^𓆊 }
Line 2,412 ⟶ 3,012:
printf "%s divmod %s = %s remainder %s =OR= %s 𓅓 %s = %s remainder %s\n",
𓃾, 𓆙, |(𓃾 𓅓 𓆙), (𓃾, 𓆙, |(𓃾 𓅓 𓆙))».&𓁶;
}</
{{out}}
Line 2,421 ⟶ 3,021:
=={{header|REXX}}==
Only addition and subtraction is used in this version of the Egyptian division method.
<
numeric digits 1000 /*support gihugic numbers & be gung-ho.*/
parse arg n d . /*obtain optional arguments from the CL*/
Line 2,444 ⟶ 3,044:
ans= ans + pow.s /*calculate the (newer) running answer.*/
end /*s*/
return ans num-acc /*return the answer and the remainder. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,455 ⟶ 3,055:
=={{header|Ring}}==
<
load "stdlib.ring"
Line 2,485 ⟶ 3,085:
see string(dividend) + " divided by " + string(divisor) + " using egytian division" + nl
see " returns " + string(answer) + " mod(ulus) " + string(dividend-accumulator)
</syntaxhighlight>
Output:
<pre>
Line 2,493 ⟶ 3,093:
=={{header|Ruby}}==
<
table = [[1, divisor]]
table << table.last.map{|e| e*2} while table.last.first * 2 <= dividend
Line 2,507 ⟶ 3,107:
puts "Quotient = %s Remainder = %s" % egyptian_divmod(580, 34)
</syntaxhighlight>
{{out}}
<pre>Quotient = 17 Remainder = 2
Line 2,513 ⟶ 3,113:
=={{header|Rust}}==
<
let dividend = dividend as u64;
let divisor = divisor as u64;
Line 2,538 ⟶ 3,138:
let (div, rem) = egyptian_divide(580, 34);
println!("580 divided by 34 is {} remainder {}", div, rem);
}</
{{out}}
<pre>580 divided by 34 is 17 remainder 2</pre>
Line 2,544 ⟶ 3,144:
=={{header|Scala}}==
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/sYSdo9u/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/3yry7OurSQS72xNMK0GMEg Scastie (remote JVM)].
<
private def divide(dividend: Int, divisor: Int): Unit = {
Line 2,572 ⟶ 3,172:
divide(580, 34)
}</
=={{header|Sidef}}==
{{trans|Ruby}}
<
var table = [[1, divisor]]
table << table[-1].map{|e| 2*e } while (2*table[-1][0] <= dividend)
Line 2,590 ⟶ 3,190:
}
say ("Quotient = %s Remainder = %s" % egyptian_divmod(580, 34))</
{{out}}
<pre>
Line 2,598 ⟶ 3,198:
=={{header|Swift}}==
<
@inlinable
public func egyptianDivide(by divisor: Self) -> (quo: Self, rem: Self) {
Line 2,631 ⟶ 3,231:
print("\(dividend) divided by \(divisor) = \(quo) rem \(rem)")
</syntaxhighlight>
{{out}}
Line 2,638 ⟶ 3,238:
=={{header|Tailspin}}==
<
templates egyptianDivision
def dividend: $(1);
Line 2,655 ⟶ 3,255:
end egyptianDivision
[580"1", 34"1"] -> egyptianDivision -> 'Quotient: $.answer; Remainder: $: 580"1" - $.accumulator;' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>Quotient: 17"1" Remainder: 2"1"</pre>
=={{header|VBA}}==
<
Private Type MyTable
Line 2,717 ⟶ 3,317:
Divise.Quotient = a.answer
Divise.Remainder = Deg.Dividend - a.accumulator
End Function</
{{out}}
<pre>Quotient = 17 Remainder = 2</pre>
=={{header|
{{trans|
<syntaxhighlight lang="v (vlang)">fn egyptian_divide(dividend int, divisor int) ?(int, int) {
}
if dividend < divisor {
}
mut powers_of_two := [1]
mut doublings := [divisor]
mut doubling := divisor
for {
doubling *= 2
if doubling > dividend {
break
}
l := powers_of_two.len
powers_of_two << powers_of_two[l-1]*2
doublings << doubling
}
mut answer := 0
mut accumulator := 0
for i := doublings.len - 1; i >= 0; i-- {
if accumulator+doublings[i] <= dividend {
accumulator += doublings[i]
answer += powers_of_two[i]
if accumulator == dividend {
break
}
}
}
return answer, dividend - accumulator
}
fn main() {
dividend := 580
divisor := 34
quotient, remainder := egyptian_divide(dividend, divisor)?
println("$dividend divided by $divisor is $quotient with remainder $remainder")
}</syntaxhighlight>
{{out}}
<pre>
580 divided by 34 is 17 with remainder 2
</pre>
=={{header|Wren}}==
{{trans|Go}}
<
if (dividend < 0 || divisor <= 0) Fiber.abort("Invalid argument(s).")
if (dividend < divisor) return [0, dividend]
Line 2,803 ⟶ 3,398:
var divisor = 34
var res = egyptianDivide.call(dividend, divisor)
System.print("%(dividend) ÷ %(divisor) = %(res[0]) with remainder %(res[1]).")</
{{out}}
Line 2,809 ⟶ 3,404:
580 ÷ 34 = 17 with remainder 2.
</pre>
=={{header|XPL0}}==
{{trans|Wren}}
<syntaxhighlight lang "XPL0">include xpllib; \for Print
proc EgyptianDivide(Dividend, Divisor, AddrQuotient, AddrRemainder);
int Dividend, Divisor, AddrQuotient, AddrRemainder;
int PowersOfTwo(100), Doublings(100), Doubling, Accumulator, I;
[if Dividend < Divisor then
[AddrQuotient(0):= 0; AddrRemainder(0):= Dividend; return];
PowersOfTwo(0):= 1; Doublings(0):= Divisor; Doubling:= Divisor; I:= 1;
loop [Doubling:= Doubling*2;
if Doubling > Dividend then quit;
PowersOfTwo(I):= PowersOfTwo(I-1)*2;
Doublings(I):= Doubling;
I:= I+1;
];
AddrQuotient(0):= 0; Accumulator:= 0;
for I:= I-1 downto 0 do
[if Accumulator + Doublings(I) <= Dividend then
[Accumulator:= Accumulator + Doublings(I);
AddrQuotient(0):= AddrQuotient(0) + PowersOfTwo(I);
if Accumulator = Dividend then I:= 0;
];
];
AddrRemainder(0):= Dividend - Accumulator;
];
int Dividend, Divisor, Quotient, Remainder;
[Dividend:= 580; Divisor:= 34;
EgyptianDivide(Dividend, Divisor, @Quotient, @Remainder);
Print("%d / %d = %d with remainder %d.\n", Dividend, Divisor, Quotient, Remainder);
]</syntaxhighlight>
{{out}}
<pre>
580 / 34 = 17 with remainder 2.
</pre>
=={{header|Zig}}==
{{trans|C}}
<syntaxhighlight lang="zig">const std = @import("std");
pub fn egyptianDivision(dividend: u64, divisor: u64) [2]u64 {
const SIZE = 64;
var powers = [_]u64{0} ** SIZE;
var doublings = [_]u64{0} ** SIZE;
var i: u64 = 0;
while (i < SIZE) {
powers[i] = std.math.shl(u64, 1, i);
doublings[i] = std.math.shl(u64, divisor, i);
if (doublings[i] > dividend) {
break;
}
i += 1;
}
var accumulator: u64 = 0;
var answer: u64 = 0;
i -= 1;
while (i >= 0) {
if (accumulator + doublings[i] <= dividend) {
accumulator += doublings[i];
answer += powers[i];
}
if (i > 0) {
i -= 1;
} else {
break;
}
}
var remainder = dividend - accumulator;
return .{ answer, remainder };
}
test "Expect 10, 0 from egyptianDivision(20, 2)" {
var output = egyptianDivision(20, 2);
try std.testing.expect(output[0] == 10);
try std.testing.expect(output[1] == 0);
}
test "Expect 580 divided by 34 is 17 and the remainder is 2" {
var output = egyptianDivision(580, 34);
try std.testing.expect(output[0] == 17);
try std.testing.expect(output[1] == 2);
}
pub fn main() !void {
var result = egyptianDivision(20, 2);
std.debug.print("20 divided by 2 is {} with remainder {}\n", .{ result[0], result[1] });
}
</syntaxhighlight>
{{out}}
<pre>20 divided by 2 is 10 with remainder 0</pre>
=={{header|zkl}}==
<
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 });
Line 2,819 ⟶ 3,509:
}
return(accumulator,dividend);
}</
<
println("%d %% %d = %s".fmt(dividend,divisor,egyptianDivmod(dividend,divisor)));
}</
{{out}}
<pre>
| |||