Ethiopian multiplication: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added/changed comments, added subroutine fence, added whitespace. -- ~~~~) |
(Added XPL0) |
||
Line 3,478: | Line 3,478: | ||
;pretty small, just 24 bytes </lang> |
;pretty small, just 24 bytes </lang> |
||
=={{header|XPL0}}== |
|||
<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations |
|||
func Halve(N); \Return half of N |
|||
int N; |
|||
return N>>1; |
|||
func Double(N); \Return N doubled |
|||
int N; |
|||
return N<<1; |
|||
func IsEven(N); \Return 'true' if N is an even number |
|||
int N; |
|||
return (N&1)=0; |
|||
func EthiopianMul(A, B); \Multiply A times B using Ethiopian method |
|||
int A, B; |
|||
int I, J, S, Left(100), Right(100); |
|||
[Left(0):= A; Right(0):= B; \1. write numbers to be multiplied |
|||
I:= 1; \2. repeatedly halve number on left |
|||
repeat A:= Halve(A); |
|||
Left(I):= A; I:= I+1; |
|||
until A=1; |
|||
J:= 1; \3. repeatedly double number on right |
|||
repeat B:= Double(B); |
|||
Right(J):= B; J:= J+1; |
|||
until J=I; \stop where left column = 1 |
|||
for J:= 0 to I-1 do \4. discard right value if left is even |
|||
if IsEven(Left(J)) then Right(J):= 0; |
|||
S:= 0; \5. sum remaining values on right |
|||
for J:= 0 to I-1 do |
|||
S:= S + Right(J); |
|||
for J:= 0 to I-1 do \show this insanity |
|||
[IntOut(0, Left(J)); ChOut(0, 9\tab\); IntOut(0, Right(J)); CrLf(0)]; |
|||
Text(0, " -------- |
|||
"); |
|||
return S; \sum = product |
|||
]; |
|||
int Product; |
|||
[Product:= EthiopianMul(17, 34); |
|||
ChOut(0, 9); IntOut(0, Product); CrLf(0); CrLf(0); |
|||
Product:= EthiopianMul(1234, 5678); |
|||
ChOut(0, 9); IntOut(0, Product); CrLf(0); |
|||
]</lang> |
|||
{{out}} |
|||
<pre> |
|||
17 34 |
|||
8 0 |
|||
4 0 |
|||
2 0 |
|||
1 544 |
|||
-------- |
|||
578 |
|||
1234 0 |
|||
617 11356 |
|||
308 0 |
|||
154 0 |
|||
77 90848 |
|||
38 0 |
|||
19 363392 |
|||
9 726784 |
|||
4 0 |
|||
2 0 |
|||
1 5814272 |
|||
-------- |
|||
7006652 |
|||
</pre> |
|||
[[Category:Arithmetic]] |
[[Category:Arithmetic]] |