Egyptian division: Difference between revisions
no edit summary
No edit summary |
|||
| (12 intermediate revisions by 8 users not shown) | |||
Line 310:
;Related tasks:
:* [[Egyptian_fractions|Egyptian fractions]]
:* [[Ethiopian_multiplication|Ethiopian multiplication]]
;References:
Line 638:
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}}==
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}}==
<syntaxhighlight lang="erlang">-module(egypt).
Line 1,381 ⟶ 1,864:
580 divided by 34 is 17 remainder 2 ok
</pre>
=={{header|Go}}==
Line 2,081 ⟶ 2,521:
- : 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}}==
Line 2,514 ⟶ 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.
Line 2,847 ⟶ 3,320:
{{out}}
<pre>Quotient = 17 Remainder = 2</pre>
=={{header|V (Vlang)}}==
Line 2,951 ⟶ 3,371:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
if (dividend < 0 || divisor <= 0) Fiber.abort("Invalid argument(s).")
if (dividend < divisor) return [0, dividend]
Line 2,984 ⟶ 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}}==
| |||