Ethiopian multiplication
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
A method of multiplying integers using only addition, doubling, and halving.
Method:
- Take two numbers to be multiplied and write them down at the top of two columns.
- In the left-hand column repeatedly halve the last number, discarding any remainders, and write the result below the last in the same column, until you write a value of 1.
- In the right-hand column repeatedly double the last number and write the result below. stop when you add a result in the same row as where the left hand column shows 1.
- Examine the table produced and discard any row where the value in the left column is even.
- Sum the values in the right-hand column that remain to produce the result of multiplying the original two numbers together
For example: 17 × 34
17 34
Halving the first column:
17 34 8 4 2 1
Doubling the second column:
17 34 8 68 4 136 2 272 1 544
Strike-out rows whose first cell is even:
17 34 8 -- 4 --- 2 --- 1 544
Sum the remaining numbers in the right-hand column:
17 34 8 -- 4 --- 2 --- 1 544 ==== 578
So 17 multiplied by 34, by the Ethiopian method is 578.
The task is to define three functions/methods/procedures/subroutines:
- one to halve an integer,
- one to double an integer, and
- one to state if an integer is even.
Use these functions to create a function that does Ethiopian multiplication.
References
- A Night Of Numbers - Go Forth And Multiply (Video)
- Ethiopian multiplication
- Russian Peasant Multiplication
- Programming Praxis: Russian Peasant Multiplication
Ada
<lang Ada>package Ethiopian is
function Multiply(Left, Right : Integer) return Integer;
end Ethiopian;</lang> <lang Ada>package body Ethiopian is
function Is_Even(Item : Integer) return Boolean is begin return Item mod 2 = 0; end Is_Even; function Double(Item : Integer) return Integer is begin return Item * 2; end Double; function Half(Item : Integer) return Integer is begin return Item / 2; end Half; function Multiply(Left, Right : Integer) return Integer is Temp : Integer := 0; Plier : Integer := Left; Plicand : Integer := Right; begin while Plier >= 1 loop if not Is_Even(Plier) then Temp := Temp + Plicand; end if; Plier := Half(Plier); Plicand := Double(Plicand); end loop; return Temp; end Multiply;
end Ethiopian;</lang>
<lang Ada>with Ethiopian; use Ethiopian; with Ada.Text_Io; use Ada.Text_Io;
procedure Ethiopian_Test is
First : Integer := 17; Second : Integer := 34;
begin
Put_Line(Integer'Image(First) & " times " & Integer'Image(Second) & " = " & Integer'Image(Multiply(First, Second)));
end Ethiopian_Test;</lang>
ALGOL 68
<lang algol> PROC halve = (REF INT x)VOID: x := ABS(BIN x SHR 1); PROC doublit = (REF INT x)VOID: x := ABS(BIN x SHL 1); PROC iseven = (#CONST# INT x)BOOL: NOT ODD x;
PROC ethiopian = (INT in plier,
INT in plicand, #CONST# BOOL tutor)INT:
(
INT plier := in plier, plicand := in plicand; INT result:=0; IF tutor THEN printf(($"ethiopian multiplication of "g(0)," by "g(0)l$, plier, plicand)) FI; WHILE plier >= 1 DO IF iseven(plier) THEN IF tutor THEN printf(($" "4d," "6d" struck"l$, plier, plicand)) FI ELSE IF tutor THEN printf(($" "4d," "6d" kept"l$, plier, plicand)) FI; result +:= plicand FI; halve(plier); doublit(plicand) OD; result
);
main: (
printf(($g(0)l$, ethiopian(17, 34, TRUE)))
) </lang> Output:
ethiopian multiplication of 17 by 34 0017 000034 kept 0008 000068 struck 0004 000136 struck 0002 000272 struck 0001 000544 kept 578
AutoHotkey
<lang AutoHotkey>MsgBox % Ethiopian(17, 34) "`n" Ethiopian2(17, 34)
- func definitions
half( x ) { return x >> 1 }
double( x ) { return x << 1 }
isEven( x ) { return x & 1 == 0 }
Ethiopian( a, b ) { r := 0 While (a >= 1) { if !isEven(a) r += b a := half(a) b := double(b) } return r }
- or a recursive function
Ethiopian2( a, b, r = 0 ) { ;omit r param on initial call return a==1 ? r+b : Ethiopian2( half(a), double(b), !isEven(a) ? r+b : r ) }</lang>
AWK
Implemented without the tutor. <lang awk>function halve(x) {
return int(x/2)
}
function double(x) {
return x*2
}
function iseven(x) {
return x%2 == 0
}
function ethiopian(plier, plicand) {
r = 0 while(plier >= 1) { if ( !iseven(plier) ) { r += plicand } plier = halve(plier) plicand = double(plicand) } return r
}
BEGIN {
print ethiopian(17, 34)
}</lang>
C
<lang c>#include <stdio.h>
- include <stdbool.h>
void halve(int *x) { *x >>= 1; } void doublit(int *x) { *x <<= 1; } bool iseven(const int x) { return (x & 1) == 0; }
int ethiopian(int plier, int plicand, const bool tutor) {
int result=0;
if (tutor) printf("ethiopian multiplication of %d by %d\n", plier, plicand); while(plier >= 1) { if ( iseven(plier) ) { if (tutor) printf("%4d %6d struck\n", plier, plicand); } else { if (tutor) printf("%4d %6d kept\n", plier, plicand); result += plicand; } halve(&plier); doublit(&plicand); } return result;
}
int main() {
printf("%d\n", ethiopian(17, 34, true)); return 0;
}</lang>
C++
Using C++ templates, these kind of tasks can be implemented as meta-programs. The program runs at compile time, and the result is statically saved into regularly compiled code. Here is such an implementation without tutor, since there is no mechanism in C++ to output messages during program compilation. <lang cpp> template<int N> struct Half {
enum { Result = N >> 1 };
};
template<int N> struct Double {
enum { Result = N << 1 };
};
template<int N> struct IsEven {
static const bool Result = (N & 1) == 0;
};
template<int Multiplier, int Multiplicand> struct EthiopianMultiplication {
template<bool Cond, int Plier, int RunningTotal> struct AddIfNot { enum { Result = Plier + RunningTotal }; }; template<int Plier, int RunningTotal> struct AddIfNot <true, Plier, RunningTotal> { enum { Result = RunningTotal }; };
template<int Plier, int Plicand, int RunningTotal> struct Loop { enum { Result = Loop<Half<Plier>::Result, Double<Plicand>::Result, AddIfNot<IsEven<Plier>::Result, Plicand, RunningTotal >::Result >::Result }; }; template<int Plicand, int RunningTotal> struct Loop <0, Plicand, RunningTotal> { enum { Result = RunningTotal }; };
enum { Result = Loop<Multiplier, Multiplicand, 0>::Result };
};
- include <iostream>
int main(int, char **) {
std::cout << EthiopianMultiplication<17, 54>::Result << std::endl; return 0;
} </lang>
ColdFusion
Version with as a function of functions:
<lang ColdFusion> <cffunction name="double">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number * 2>
<cfreturn answer>
</cffunction>
<cffunction name="halve">
<cfargument name="number" type="numeric" required="true">
<cfset answer = int(number / 2)>
<cfreturn answer>
</cffunction>
<cffunction name="even">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number mod 2>
<cfreturn answer>
</cffunction>
<cffunction name="ethiopian">
<cfargument name="Number_A" type="numeric" required="true"> <cfargument name="Number_B" type="numeric" required="true"> <cfset Result = 0> <cfloop condition = "Number_A GTE 1"> <cfif even(Number_A) EQ 1> <cfset Result = Result + Number_B> </cfif> <cfset Number_A = halve(Number_A)> <cfset Number_B = double(Number_B)> </cfloop> <cfreturn Result>
</cffunction>
<cfoutput>#ethiopian(17,34)#</cfoutput>
</lang>
Version with display pizza:
<lang ColdFusion> <cfset Number_A = 17> <cfset Number_B = 34> <cfset Result = 0>
<cffunction name="double">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number * 2>
<cfreturn answer>
</cffunction>
<cffunction name="halve">
<cfargument name="number" type="numeric" required="true">
<cfset answer = int(number / 2)>
<cfreturn answer>
</cffunction>
<cffunction name="even">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number mod 2>
<cfreturn answer>
</cffunction>
<cfoutput>
Ethiopian multiplication of #Number_A# and #Number_B#...
#Number_A# | #Number_B# | #Action# |
...equals #Result#
</cfoutput> </lang>
Sample output:
Ethiopian multiplication of 17 and 34... 17 34 Keep 8 68 Strike 4 136 Strike 2 272 Strike 1 544 Keep ...equals 578
Common Lisp
Common Lisp already has evenp
, but all three of halve
, double
, and even-p
are locally defined within ethiopian-multiply
. (Note that the termination condition is (zerop l)
because we terminate 'after' the iteration wherein the left column contains 1, and (halve 1)
is 0.)
<lang lisp>(defun ethiopian-multiply (l r)
(flet ((halve (n) (floor n 2)) (double (n) (* n 2)) (even-p (n) (zerop (mod n 2)))) (do ((product 0 (if (even-p l) product (+ product r))) (l l (halve l)) (r r (double r))) ((zerop l) product))))</lang>
D
<lang d> import std.stdio; int dub(int num) { return num << 1; } int halve(int num) { return num >> 1; } bool isEven(int num) { return !(num & 1); }
int ethiopian(int n1, int n2) {
int ret = 0; while(n1 >= 1) { if (!isEven(n1)) ret += n2; n1 = halve(n1); n2 = dub(n2); } return ret;
}
int main() {
writefln("17 ethiopian 34 is %d", ethiopian(17, 34)); return 0;
} </lang>
E
<lang e>def halve(&x) { x //= 2 } def double(&x) { x *= 2 } def even(x) { return x %% 2 <=> 0 }
def multiply(var a, var b) {
var ab := 0 while (a > 0) { if (!even(a)) { ab += b } halve(&a) double(&b) } return ab
}</lang>
Forth
<lang forth>: e* ( x y -- x*y )
dup 0= if nip exit then over 2* over 2/ recurse swap 1 and if + else nip then ;</lang>
The author of Forth, Chuck Moore, designed a similar primitive into his MISC Forth microprocessors. The +* instruction is a multiply step: it adds S to T if A is odd, then shifts both A and T right one. The idea is that you only need to perform as many of these multiply steps as you have significant bits in the operand. (See his core instruction set for details.)
Fortran
<lang fortran>program EthiopicMult
implicit none
print *, ethiopic(17, 34, .true.)
contains
subroutine halve(v) integer, intent(inout) :: v v = int(v / 2) end subroutine halve
subroutine doublit(v) integer, intent(inout) :: v v = v * 2 end subroutine doublit
function iseven(x) logical :: iseven integer, intent(in) :: x iseven = mod(x, 2) == 0 end function iseven
function ethiopic(multiplier, multiplicand, tutorialized) result(r) integer :: r integer, intent(in) :: multiplier, multiplicand logical, intent(in), optional :: tutorialized
integer :: plier, plicand logical :: tutor
plier = multiplier plicand = multiplicand
if ( .not. present(tutorialized) ) then tutor = .false. else tutor = tutorialized endif
r = 0
if ( tutor ) write(*, '(A, I0, A, I0)') "ethiopian multiplication of ", plier, " by ", plicand
do while(plier >= 1) if ( iseven(plier) ) then if (tutor) write(*, '(I4, " ", I6, A)') plier, plicand, " struck" else if (tutor) write(*, '(I4, " ", I6, A)') plier, plicand, " kept" r = r + plicand endif call halve(plier) call doublit(plicand) end do
end function ethiopic
end program EthiopicMult</lang>
Haskell
<lang haskell>halve x = x `div` 2 double x = x * 2
ethiopicmult :: Integral a => a -> a -> a ethiopicmult x y = ethiopicmult' x y 0 where
ethiopicmult' 0 _ acc = acc ethiopicmult' plier pliand acc | even plier = ethiopicmult' (halve plier) (double pliand) acc | otherwise = ethiopicmult' (halve plier) (double pliand) (acc + pliand)</lang>
Alternately: <lang haskell>ethiopicmult :: Integral a => a -> a -> a ethiopicmult x y = sum [pliand | (plier, pliand) <- rowsNonZero, odd plier]
where rowsNonZero = takeWhile ((/= 0) . fst) rows rows = zip (iterate (`div` 2) x) (iterate (* 2) y)</lang>
Usage example from the interpreter
*Main> ethiopicmult 17 34 578
J
Solution:
double =: 2&* NB. or the primitive +: halve =: %&2 NB. or the primitive -: even =: 2&|
ethiop =: +/@(even@] # (double~ <@#)) (1>.<.@halve)^:a:
Example:
17 ethiop 34 578
Note: this could be implemented more concisely as #.@(*#:), which abides by the letter of the task, but evades its spirit.
Java
<lang java5>import java.util.HashMap; import java.util.Scanner; public class Mult {
public static void main(String[] args){ Scanner sc = new Scanner(System.in); int first = sc.nextInt(); int second = sc.nextInt();
HashMap <Integer, Integer> columns = new HashMap <Integer, Integer>(); columns.put(first, second); do{ first = doubleInt(first); second = halveInt(second); columns.put(first, second); }while(first != 1);
int sum = 0; for(int firstNum:columns.keySet()){ if(!isEven(firstNum)){ sum += columns.get(firstNum); } } System.out.println(sum); }
public static int doubleInt(int doubleMe){ return doubleMe << 1; //shift left }
public static int halveInt(int halveMe){ return halveMe >>> 1; //shift right }
public static boolean isEven(int num){ return num & 1 == 0; }
}</lang> An optimised variant using the three helper functions from the other example. <lang java5>
/** * This method will use ethiopian styled multiplication. * @param a Any non-negative integer. * @param b Any integer. * @result a multiplied by b */ public static int ethiopianMultiply(int a, int b) { if(a==0 || b==0) { return 0; } int result = 0; while(a>=1) { if(!isEven(a)) { result+=b; } b = doubleInt(b); a = halveInt(a); } return result; }
/** * This method is an improved version that will use * ethiopian styled multiplication, but can fully * support negative parameters. * @param a Any integer. * @param b Any integer. * @result a multiplied by b */ public static int ethiopianMultiplyWithImprovement(int a, int b) { if(a==0 || b==0) { return 0; } if(a<0) { a=-a; b=-b; } else if(b>0 && a>b) { int tmp = a; a = b; b = tmp; } int result = 0; while(a>=1) { if(!isEven(a)) { result+=b; } b = doubleInt(b); a = halveInt(a); } return result; }
</lang>
JavaScript
<lang javascript> var eth = {
halve : function ( n ){ return Math.floor(n/2); }, double: function ( n ){ return 2*n; }, isEven: function ( n ){ return n%2 === 0); },
mult: function ( a , b ){ var sum = 0, a = [a], b = [b];
while ( a[0] !== 1 ){ a.unshift( eth.halve( a[0] ) ); b.unshift( eth.double( b[0] ) ); }
for( var i = a.length - 1; i > 0 ; i -= 1 ){
if( !eth.isEven( a[i] ) ){ sum += b[i]; } else { break; } }
return sum + b[0];
} }
// eth.mult(17,34) returns 578 </lang>
Logo
<lang logo> to double :x
output ashift :x 1
end to halve :x
output ashift :x -1
end to even? :x
output equal? 0 bitand 1 :x
end to eproduct :x :y
if :x = 0 [output 0] ifelse even? :x ~ [output eproduct halve :x double :y] ~ [output :y + eproduct halve :x double :y]
end </lang>
Metafont
Implemented without the tutor. <lang metafont>vardef halve(expr x) = floor(x/2) enddef; vardef double(expr x) = x*2 enddef; vardef iseven(expr x) = if (x mod 2) = 0: true else: false fi enddef;
primarydef a ethiopicmult b =
begingroup save r_, plier_, plicand_; plier_ := a; plicand_ := b; r_ := 0; forever: exitif plier_ < 1; if not iseven(plier_): r_ := r_ + plicand_; fi plier_ := halve(plier_); plicand_ := double(plicand_); endfor r_ endgroup
enddef;
show( (17 ethiopicmult 34) ); end</lang>
Modula-3
<lang modula3>MODULE Ethiopian EXPORTS Main;
IMPORT IO, Fmt;
PROCEDURE IsEven(n: INTEGER): BOOLEAN =
BEGIN RETURN n MOD 2 = 0; END IsEven;
PROCEDURE Double(n: INTEGER): INTEGER =
BEGIN RETURN n * 2; END Double;
PROCEDURE Half(n: INTEGER): INTEGER =
BEGIN RETURN n DIV 2; END Half;
PROCEDURE Multiply(a, b: INTEGER): INTEGER =
VAR temp := 0; plier := a; plicand := b; BEGIN WHILE plier >= 1 DO IF NOT IsEven(plier) THEN temp := temp + plicand; END; plier := Half(plier); plicand := Double(plicand); END; RETURN temp; END Multiply;
BEGIN
IO.Put("10 times 5 = " & Fmt.Int(Multiply(10, 5)) & "\n");
END Ethiopian.</lang>
Objective-C
Using class methods except for the generic useful function iseven. <lang objc>#import <stdio.h>
- import <objc/Object.h>
BOOL iseven(int x) {
return (x&1) == 0;
}
@interface EthiopicMult : Object + (int)mult: (int)plier by: (int)plicand; + (int)halve: (int)a; + (int)double: (int)a; @end
@implementation EthiopicMult + (int)mult: (int)plier by: (int)plicand {
int r = 0; while(plier >= 1) { if ( !iseven(plier) ) r += plicand; plier = [EthiopicMult halve: plier]; plicand = [EthiopicMult double: plicand]; } return r;
}
+ (int)halve: (int)a {
return (a>>1);
}
+ (int)double: (int)a {
return (a<<1);
} @end
int main() {
printf("%d\n", [EthiopicMult mult: 17 by: 34]); return 0;
}</lang>
OCaml
<lang ocaml>let ethiopicmult x y =
let rec aux plier pliand acc = if plier = 0 then acc else if plier mod 2 = 0 then aux (plier / 2) (pliand * 2) acc else aux (plier / 2) (pliand * 2) (acc + pliand) in aux x y 0</lang>
Usage example from the interpreter
# ethiopicmult 17 34;; - : int = 578
Octave
<lang octave>function r = halve(a)
r = floor(a/2);
endfunction
function r = doublit(a)
r = a*2;
endfunction
function r = iseven(a)
r = mod(a,2) == 0;
endfunction
function r = ethiopicmult(plier, plicand, tutor=false)
r = 0; if (tutor) printf("ethiopic multiplication of %d and %d\n", plier, plicand); endif while(plier >= 1) if ( iseven(plier) ) if (tutor)
printf("%4d %6d struck\n", plier, plicand);
endif else r = r + plicand; if (tutor)
printf("%4d %6d kept\n", plier, plicand);
endif endif plier = halve(plier); plicand = doublit(plicand); endwhile
endfunction
disp(ethiopicmult(17, 34, true))</lang>
Perl
<lang perl>use strict;
sub halve { return int((shift) / 2); } sub double { return (shift) * 2; } sub iseven { return ((shift) & 1) == 0; }
sub ethiopicmult {
my ($plier, $plicand, $tutor) = @_; print "ethiopic multiplication of $plier and $plicand\n" if $tutor; my $r = 0; while ($plier >= 1) {
$r += $plicand unless iseven($plier); if ($tutor) { print "$plier, $plicand ", (iseven($plier) ? " struck" : " kept"), "\n"; } $plier = halve($plier); $plicand = double($plicand);
} return $r;
}
print ethiopicmult(17,34, 1), "\n";</lang>
Perl 6
<lang perl6>sub halve (Int $n is rw) { $n div= 2 } sub double (Int $n is rw) { $n *= 2 } sub even (Int $n --> Bool) { $n % 2 == 0 }
sub ethiopicmult (Int $a is copy, Int $b is copy --> Int) {
my Int $r = 0; while $a {
even $a or $r += $b; halve $a; double $b;
} return $r;
}</lang>
PHP
<lang php><?php function halve($x) {
return floor($x/2);
}
function double($x) {
return $x*2;
}
function iseven($x) {
return ($x % 2) == 0;
}
function ethiopicmult($plier, $plicand, $tutor) {
if ($tutor) echo "ethiopic multiplication of $plier and $plicand\n"; $r = 0; while($plier >= 1) { if ( !iseven($plier) ) $r += $plicand; if ($tutor) echo "$plier, $plicand ", (iseven($plier) ? "struck" : "kept"), "\n"; $plier = halve($plier); $plicand = double($plicand); } return $r;
}
echo ethiopicmult(17, 34, true), "\n";
?></lang>
PL/SQL
This code was taken from the ADA example above - very minor differences. <lang plsql> create or replace package ethiopian is
function multiply ( left in integer, right in integer) return integer;
end ethiopian; /
create or replace package body ethiopian is
function is_even(item in integer) return boolean is begin return item mod 2 = 0; end is_even;
function double(item in integer) return integer is begin return item * 2; end double;
function half(item in integer) return integer is begin return trunc(item / 2); end half;
function multiply ( left in integer, right in integer) return Integer is temp integer := 0; plier integer := left; plicand integer := right; begin
loop if not is_even(plier) then temp := temp + plicand; end if; plier := half(plier); plicand := double(plicand); exit when plier <= 1; end loop;
temp := temp + plicand;
return temp;
end multiply;
end ethiopian; /
/* example call */ begin
dbms_output.put_line(ethiopian.multiply(17, 34));
end; / </lang>
PL/pgSQL
Everything encapsulated in one function.
<lang plpgsql> CREATE OR REPLACE FUNCTION ethiopian_multiplication(multiplier int, multiplicant int) RETURNS int AS $BODY$ -- works at least on PostgreSQL 8.3, should work in older versions as well DECLARE sum integer := 0; plier integer := abs(multiplier); plicant integer := abs(multiplicant); BEGIN -- handling 0 values IF (multiplier = 0 OR multiplicant = 0) THEN RAISE NOTICE 'One operand is 0. Result 0.'; RETURN 0; END IF; -- running until left operand equals 1 WHILE plier >= 1 LOOP -- is left operand even? IF plier % 2 = 0 THEN -- yes, strike this row RAISE NOTICE '%, % STRIKE', plier, plicant; ELSE -- no, add this row to sum RAISE NOTICE '%, % KEEP', plier, plicant; sum = sum + plicant; END IF; -- halve left argument plier = floor(plier/2); -- double left argument plicant = plicant*2; END LOOP; -- handling negative arguments IF (multiplier < 0 AND multiplicant > 0) OR (multiplier > 0 AND multiplicant < 0) THEN RAISE NOTICE 'Handling negative operands. Invert result.'; sum = 0 - sum; END IF; RETURN sum; END; $BODY$ LANGUAGE 'plpgsql'; </lang>
<lang sql> SELECT ethiopian_multiplication(17, 34); </lang>
<lang text> NOTICE: 17, 34 KEEP NOTICE: 8, 68 STRIKE NOTICE: 4, 136 STRIKE NOTICE: 2, 272 STRIKE NOTICE: 1, 544 KEEP
ethiopian_multiplication
578
(1 row) </lang>
PowerShell
<lang PowerShell> function isEven { param ([int]$value) return [bool]($value % 2 -eq 0) }
function doubleValue { param ([int]$value) return [int]($value * 2) }
function halveValue { param ([int]$value) return [int]($value / 2) }
function multiplyValues { param ( [int]$plier, [int]$plicand, [int]$temp = 0 )
while ($plier -ge 1) { if (!(isEven $plier)) { $temp += $plicand } $plier = halveValue $plier $plicand = doubleValue $plicand }
return $temp }
multiplyValues 17 34 </lang>
Python
<lang python> tutor = True
def halve(x):
return x//2
def double(x):
return x*2
def even(x):
return not x % 2
def ethiopian(multiplier, multiplicand):
if tutor: print( "Ethiopian multiplication of %i and %i" % (multiplier, multiplicand) ) result = 0 while multiplier >= 1: if even(multiplier): if tutor: print( "%4i %6i STRUCK" % (multiplier, multiplicand) ) else: if tutor: print( "%4i %6i KEPT" % (multiplier, multiplicand) ) result += multiplicand multiplier = halve(multiplier) multiplicand = double(multiplicand) if tutor: print() return result
</lang>
Sample output
Python 3.1 (r31:73574, Jun 26 2009, 20:21:35) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ethiopian(17, 34) Ethiopian multiplication of 17 and 34 17 34 KEPT 8 68 STRUCK 4 136 STRUCK 2 272 STRUCK 1 544 KEPT 578 >>>
Without the tutorial code, and taking advantage of Python's lambda:
<lang python> halve = lambda x: x // 2 double = lambda x: x*2 even = lambda x : not x % 2
def ethiopian(multiplier, multiplicand):
result = 0
while multiplier >= 1: if not even(multiplier): result += multiplicand multiplier = halve(multiplier) multiplicand = double(multiplicand)
return result
</lang>
R
<lang R>halve <- function(a) floor(a/2) double <- function(a) a*2 iseven <- function(a) (a%%2)==0
ethiopicmult <- function(plier, plicand, tutor=FALSE) {
if (tutor) { cat("ethiopic multiplication of", plier, "and", plicand, "\n") } result <- 0 while(plier >= 1) { if (!iseven(plier)) { result <- result + plicand } if (tutor) { cat(plier, ", ", plicand, " ", ifelse(iseven(plier), "struck", "kept"), "\n", sep="") } plier <- halve(plier) plicand <- double(plicand) } result
}
print(ethiopicmult(17, 34, TRUE))</lang>
Another interesting implementation could be
<lang R>ethiopicmult <- function(a, b) {
plier <- c(a) plicand <- c(b) while( plier[ length(plier) ] > 1 ) { plier <- c(plier, floor(plier[length(plier)]/2)) plicand <- c(plicand, plicand[length(plicand)]*2) } return( sum(plicand[ plier %% 2 != 0]) )
}</lang>
Ruby
Iterative and recursive implementations here. I've chosen to highlight the example 20*5 which I think is more illustrative. <lang ruby>def even(x); x.even?; end def halve(x); x/2; end def double(x); x*2; end
- iterative
def ethopian_multiply(a, b)
product = 0 while a >= 1 p [a, b, even(a) ? "STRIKE" : "KEEP"] if $DEBUG product += b if not even(a) a = halve(a) b = double(b) end product
end
- recursive
def rec_ethopian_multiply(a, b)
return 0 if a < 1 p [a, b, even(a) ? "STRIKE" : "KEEP"] if $DEBUG (even(a) ? 0 : b) + rec_ethopian_multiply(halve(a), double(b))
end
$DEBUG = true # $DEBUG also set to true if "-d" option given a, b = 20, 5 puts "#{a} * #{b} = #{ethopian_multiply(a,b)}"; puts
$DEBUG = false require 'test/unit' class EthiopianTests < Test::Unit::TestCase
def test_iter1; assert_equal(578, ethopian_multiply(17,34)); end def test_iter2; assert_equal(100, ethopian_multiply(20,5)); end def test_iter3; assert_equal(5, ethopian_multiply(5,1)); end def test_iter4; assert_equal(5, ethopian_multiply(1,5)); end def test_iter5; assert_equal(0, ethopian_multiply(5,0)); end def test_iter6; assert_equal(0, ethopian_multiply(0,5)); end def test_rec1; assert_equal(578, rec_ethopian_multiply(17,34)); end def test_rec2; assert_equal(100, rec_ethopian_multiply(20,5)); end def test_rec3; assert_equal(5, rec_ethopian_multiply(5,1)); end def test_rec4; assert_equal(5, rec_ethopian_multiply(1,5)); end def test_rec5; assert_equal(0, rec_ethopian_multiply(5,0)); end def test_rec6; assert_equal(0, rec_ethopian_multiply(0,5)); end
end</lang> Output:
[20, 5, "STRIKE"] [10, 10, "STRIKE"] [5, 20, "KEEP"] [2, 40, "STRIKE"] [1, 80, "KEEP"] 20 * 5 = 100 Loaded suite ethopian Started ............ Finished in 0.001 seconds. 12 tests, 12 assertions, 0 failures, 0 errors
Seed7
Ethiopian Multiplication is another name for the peasant multiplication:
<lang seed7>const func integer: peasantMult (in var integer: a, in var integer: b) is func
result var integer: result is 0; begin while a <> 0 do if odd(a) then result +:= b; end if; a := a div 2; b *:= 2; end while; end func;</lang>
Original source: [1]
Smalltalk
<lang smalltalk>Number extend [
double [ ^ self * 2 ] halve [ ^ self // 2 ] ethiopianMultiplyBy: aNumber withTutor: tutor [ |result multiplier multiplicand| multiplier := self. multiplicand := aNumber. tutor ifTrue: [ ('ethiopian multiplication of %1 and %2' % { multiplier. multiplicand }) displayNl ]. result := 0. [ multiplier >= 1 ] whileTrue: [ multiplier even ifFalse: [ result := result + multiplicand. tutor ifTrue: [ ('%1, %2 kept' % { multiplier. multiplicand }) displayNl ] ] ifTrue: [ tutor ifTrue: [ ('%1, %2 struck' % { multiplier. multiplicand })
displayNl
] ]. multiplier := multiplier halve. multiplicand := multiplicand double. ]. ^result ] ethiopianMultiplyBy: aNumber [ ^ self ethiopianMultiplyBy: aNumber withTutor: false ]
].</lang>
<lang smalltalk>(17 ethiopianMultiplyBy: 34 withTutor: true) displayNl.</lang>
Tcl
<lang tcl>proc tcl::mathfunc::double n {expr {$n * 2}} proc tcl::mathfunc::halve n {expr {$n / 2}} proc tcl::mathfunc::even n {expr {($n & 1) == 0}} proc tcl::mathfunc::mult {a b} {expr {
$a < 1 ? 0 : even($a) ? [logmult STRUCK] + mult(halve($a), double($b))
: [logmult KEPT] + mult(halve($a), double($b)) + $b }}
- Wrapper to set up the logging
proc ethiopianMultiply {a b {tutor false}} {
if {$tutor} {
set wa [expr {[string length $a]+1}] set wb [expr {$wa+[string length $b]-1}] puts stderr "Ethiopian multiplication of $a and $b" interp alias {} logmult {} apply {{wa wb msg} { upvar 1 a a b b puts stderr [format "%*d %*d %s" $wa $a $wb $b $msg] return 0 }} $wa $wb
} else {
proc logmult args {return 0}
} return [expr {mult($a,$b)}]
}</lang> Demo code: <lang tcl>puts "17 * 34 = [ethiopianMultiply 17 34 true]"</lang> Output:
Ethiopian multiplication of 17 and 34 17 34 KEPT 8 68 STRUCK 4 136 STRUCK 2 272 STRUCK 1 544 KEPT 17 * 34 = 578
UNIX Shell
(Tried with bash --posix, so it should run in sh too) <lang bash>halve() {
echo $(( $1 / 2 ))
}
double() {
echo $(( $1 * 2 ))
}
iseven() {
echo $(( $1 % 2 == 0 ))
}
ethiopicmult() {
plier=$1 plicand=$2 r=0 while [ $plier -ge 1 ]; do
if [ $(iseven $plier) -eq 0 ]; then r=$(( r + plicand)) fi plier=$(halve $plier) plicand=$(double $plicand)
done echo $r
}
echo $(ethiopicmult 17 34)</lang>
Ursala
The first implementation below relies on the representation of natural numbers as lists of bits, lsb first, so that halving is the same as taking the tail, doubling is inserting a zero, and filtering for oddness is filtering by the head, all of which are expressible as primitives. <lang Ursala>
- import nat
emul = @lrtK33PDNlCrXK9rhPFlS sum:-0 </lang> Here is a more verbose version (in keeping with the spirit of the task) treating natural numbers as abstract types, and explicitly using the operators for distribution (*-), triangular iteration (|\), and filtering (*~) among others. <lang Ursala>
- import nat
emul = sum:-0@rS+ odd@l*~+ ^|(~&,double)|\+ *-^|\~& @iNC ~&h~=0->tx :^/half@h ~& </lang>
test program: <lang Ursala>
- cast %n
test = emul(34,17) </lang> output:
578
x86 assembly
, linking with the C standard library and start code.
<lang asm> extern printf global main
section .text
halve shr ebx, 1 ret
double shl ebx, 1 ret
iseven and ebx, 1 cmp ebx, 0 ret ; ret preserves flags
main push 1 ; tutor = true push 34 ; 2nd operand push 17 ; 1st operand call ethiopicmult add esp, 12
push eax ; result of 17*34 push fmt call printf add esp, 8
ret
%define plier 8
%define plicand 12
%define tutor 16
ethiopicmult enter 0, 0 cmp dword [ebp + tutor], 0 je .notut0 push dword [ebp + plicand] push dword [ebp + plier] push preamblefmt call printf add esp, 12 .notut0
xor eax, eax ; eax -> result mov ecx, [ebp + plier] ; ecx -> plier mov edx, [ebp + plicand] ; edx -> plicand
.whileloop cmp ecx, 1 jl .multend cmp dword [ebp + tutor], 0 je .notut1 call tutorme .notut1 mov ebx, ecx call iseven je .iseven add eax, edx ; result += plicand .iseven mov ebx, ecx ; plier >>= 1 call halve mov ecx, ebx
mov ebx, edx ; plicand <<= 1 call double mov edx, ebx
jmp .whileloop .multend leave ret
tutorme
push eax
push strucktxt
mov ebx, ecx
call iseven
je .nostruck
mov dword [esp], kepttxt
.nostruck
push edx
push ecx
push tutorfmt
call printf
add esp, 4
pop ecx
pop edx
add esp, 4
pop eax
ret
section .data
fmt db "%d", 10, 0 preamblefmt db "ethiopic multiplication of %d and %d", 10, 0 tutorfmt db "%4d %6d %s", 10, 0 strucktxt db "struck", 0 kepttxt db "kept", 0</lang>
Smaller version
Using old style 16 bit registers created in debug
The functions to halve double and even are coded inline. To half a value
shr,1
to double a value
shl,1
to test if the value is even
<lang asm>test,01 jz Even Odd: Even:</lang>
<lang asm>;calling program
1BDC:0100 6A11 PUSH 11 ;17 Put operands on the stack 1BDC:0102 6A22 PUSH 22 ;34 1BDC:0104 E80900 CALL 0110 ; call the mulitplcation routine
- putting some space in, (not needed)
1BDC:0107 90 NOP 1BDC:0108 90 NOP 1BDC:0109 90 NOP 1BDC:010A 90 NOP 1BDC:010B 90 NOP 1BDC:010C 90 NOP 1BDC:010D 90 NOP 1BDC:010E 90 NOP 1BDC:010F 90 NOP
- mulitplication routine
1BDC:0110 89E5 MOV BP,SP ; prepare to get operands off stack 1BDC:0112 8B4E02 MOV CX,[BP+02] ; Get the first operand 1BDC:0115 8B5E04 MOV BX,[BP+04] ; get the second oerand 1BDC:0118 31C0 XOR AX,AX ; zero out the result 1BDC:011A F7C10100 TEST CX,0001 ; are we odd 1BDC:011E 7402 JZ 0122 ; no skip the next instruction 1BDC:0120 01D8 ADD AX,BX ; we are odd so add to the result 1BDC:0122 D1E9 SHR CX,1 ; divide by 2 1BDC:0124 D1E3 SHL BX,1 ; multiply by 2 1BDC:0126 83F901 CMP CX,+01 ; are we done (==1) 1BDC:0129 75EF JNZ 011A ; no, go back and do it again 1BDC:012B 01D8 ADD AX,BX ; final add 1BDC:012D C3 RET ; return with the result in AX
- pretty small
</lang>
- Programming Tasks
- Arithmetic operations
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- C
- C++
- ColdFusion
- Common Lisp
- D
- E
- Forth
- Fortran
- Haskell
- J
- Java
- JavaScript
- Logo
- Metafont
- Modula-3
- Objective-C
- OCaml
- Octave
- Perl
- Perl 6
- PHP
- PL/SQL
- PL/pgSQL
- PL/pgSQL examples needing attention
- Examples needing attention
- PowerShell
- Python
- R
- R examples needing attention
- Ruby
- Seed7
- Seed7 examples needing attention
- Smalltalk
- Tcl
- UNIX Shell
- Ursala
- Ursala examples needing attention
- X86 assembly