Ethiopian multiplication: Difference between revisions

From Rosetta Code
Content added Content deleted
(Correct parameter type)
(added factor implemenation)
Line 536: Line 536:
return ab
return ab
}</lang>
}</lang>

=={{header|Factor}}==
<lang factor>USING: arrays kernel math multiline sequences ;
IN: ethiopian-multiplication

/*
This function is built-in
: odd? ( n -- ? ) 1 bitand 1 number= ;
*/

: double ( n -- 2*n ) 2 * ;
: halve ( n -- n/2 ) 2 /i ;

: ethiopian-mult ( a b -- a*b )
[ 0 ] 2dip
[ dup 0 > ] [
[ odd? [ + ] [ drop ] if ] 2keep
[ double ] [ halve ] bi*
] while 2drop ;</lang>


=={{header|FALSE}}==
=={{header|FALSE}}==

Revision as of 19:38, 25 December 2009

Task
Ethiopian multiplication
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:

  1. Take two numbers to be multiplied and write them down at the top of two columns.
  2. 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.
  3. 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.
  4. Examine the table produced and discard any row where the value in the left column is even.
  5. 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 named functions/methods/procedures/subroutines:

  1. one to halve an integer,
  2. one to double an integer, and
  3. one to state if an integer is even.

Use these functions to create a function that does Ethiopian multiplication.

References

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

Translation of: C
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

<lang algol68>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>

  1. 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 };

};

  1. include <iostream>

int main(int, char **) { 

       std::cout << EthiopianMultiplication<17, 54>::Result << std::endl;
       return 0;

}</lang>

C#

<lang csharp>static void Main(string[] args) { 

   EthopianMultiplication(17, 34);
   Console.ReadKey();

}

static int Half(int value) { 

   return value >> 1;

}

static int Double(int value) { 

   return value << 1;

}

static bool Even(int value) { 

   return (value % 2) == 0;

}

static void EthopianMultiplication(int lhs, int rhs) { 

   int total = 0;
   int col1 = lhs;
   int col2 = rhs;

   while (col1 > 0)
   {
       Console.WriteLine("{0,4} | {1,4}", col1, col2);
       if (!Even(col1))
       {
           total = total + col2;
       }
       col1 = Half(col1);
       col2 = Double(col2);
   }

   Console.WriteLine("Total = {0}", total);

}</lang>

ColdFusion

Version with as a function of functions:

<lang cfm><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 cfm><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#...


<cfloop condition = "Number_A GTE 1"> <cfif even(Number_A) EQ 1> <cfset Result = Result + Number_B> <cfset Action = "Keep"> <cfelse> <cfset Action = "Strike"> </cfif> <cfset Number_A = halve(Number_A)> <cfset Number_B = double(Number_B)> </cfloop>
#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

Clojure

<lang lisp>(defn halve [n] 

 (bit-shift-right n 1))

(defn twice [n]  ; 'double' is taken 

 (bit-shift-left n 1))

(defn even [n]  ; 'even?' is the standard fn 

 (zero? (bit-and n 1)))

(defn emult [x y] 

 (reduce + 
   (map second 
     (filter #(not (even (first %))) ; a.k.a. 'odd?'
       (take-while #(pos? (first %)) 
         (map vector 
           (iterate halve x) 
           (iterate twice y)))))))

(defn emult2 [x y] 

 (loop [a x, b y, r 0]
   (if (= a 1)
     (+ r b)
     (if (even a)
       (recur (halve a) (twice b) r)
       (recur (halve a) (twice b) (+ r b))))))</lang>

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>int ethiopian(int n1, int n2) { 

   static int doubleNum(int n) { return n * 2; }
   static int halveNum(int n) { return n / 2; }
   static bool isEven(int n) { return !(n % 2); }

   int result;

   while (n1 >= 1) {
       if (!isEven(n1))
           result += n2;
       n1 = halveNum(n1);
       n2 = doubleNum(n2);
    }

    return result;

}

void main() { 

   printf("17 ethiopian 34 is %d\n", ethiopian(17, 34));

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

Factor

<lang factor>USING: arrays kernel math multiline sequences ; IN: ethiopian-multiplication

/* This function is built-in

odd? ( n -- ? ) 1 bitand 1 number= ;
  • /
double ( n -- 2*n ) 2 * ;
halve ( n -- n/2 ) 2 /i ;
ethiopian-mult ( a b -- a*b )
   [ 0 ] 2dip
   [ dup 0 > ] [
       [ odd? [ + ] [ drop ] if ] 2keep
       [ double ] [ halve ] bi*
   ] while 2drop ;</lang>

FALSE

<lang false>[2/]h: [2*]d: [1&]o: [0[@$][$o;![@@\$@+@]?h;!@d;!@]#%\%]m: 17 34m;!. {578}</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

Works with: Fortran version 90 and later

<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: <lang j>double =: 2&* NB. or the primitive +: halve =:  %&2 NB. or the primitive -: even =: 2&|

ethiop =: +/@(even@] # (double~ <@#)) (1>.<.@halve)^:a:</lang>

Example: <lang j> 17 ethiop 34 578</lang>

Note: this could be implemented more concisely as #.@(*#:), which abides by the letter of the task, but evades its spirit.

Java

Works with: Java version 1.5+

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

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

Lua

<lang lua>function halve(a) 

   return a/2

end

function double(a) 

   return a*2

end

function isEven(a) 

   return a%2 == 0

end

function ethiopian(x, y) 

   local result = 0

   while (x >= 1) do
       if not isEven(x) then
           result = result + y
       end

       x = math.floor(halve(x))
       y = double(y)
   end

   return result;

end

print(ethiopian(17, 34))</lang>

MMIX

In order to assemble and run this program you'll have to install MMIXware from [1]. This provides you with a simple assembler, a simulator, example programs and full documentation.

<lang mmix>A IS 17 B IS 34

pliar IS $255 % designating main registers pliand GREG acc GREG str IS pliar % reuse reg $255 for printing

LOC Data_Segment GREG @ BUF OCTA #3030303030303030 % reserve a buffer that's big enough to hold OCTA #3030303030303030 % a max (signed) 64 bit integer: OCTA #3030300a00000000 % 2^63 - 1 = 9223372036854775807  % string is terminated with NL, 0

LOC #1000 % locate program at address GREG @ halve SR pliar,pliar,1 GO $127,$127,0

double SL pliand,pliand,1 GO $127,$127,0

odd DIV $77,pliar,2 GET $78,rR GO $127,$127,0

% Main is the entry point of the program Main SET pliar,A % initialize registers for calculation SET pliand,B SET acc,0 1H GO $127,odd BZ $78,2F % if pliar is even skip incr. acc with pliand ADD acc,acc,pliand % 2H GO $127,halve % halve pliar GO $127,double % and double pliand PBNZ pliar,1B % repeat from 1H while pliar > 0 // result: acc = 17 x 34 // next: print result --> stdout // $0 is a temp register LDA str,BUF+19 % points after the end of the string 2H SUB str,str,1 % update buffer pointer DIV acc,acc,10 % do a divide and mod GET $0,rR % get digit from special purpose reg. rR % containing the remainder of the division INCL $0,'0' % convert to ascii STBU $0,str % place digit in buffer PBNZ acc,2B % next % 'str' points to the start of the result TRAP 0,Fputs,StdOut % output answer to stdout TRAP 0,Halt,0 % exit</lang> Assembling: 

~/MIX/MMIX/Progs> mmixal ethiopianmult.mms

Running: 

~/MIX/MMIX/Progs> mmix ethiopianmult
578

Modula-3

Translation of: Ada

<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("17 times 34 = " & Fmt.Int(Multiply(17, 34)) & "\n");

END Ethiopian.</lang>

Objective-C

Using class methods except for the generic useful function iseven. <lang objc>#import <stdio.h>

  1. 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 { int((shift) / 2); } sub double { (shift) * 2; } sub iseven { ((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

Works with: Rakudo version #21 "Seattle"

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

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

This example is incorrect. Please fix the code and remove this message.

Details: The example is to have separate functions for doubling, halving, and checking if a number is even.

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 plpgsql>SELECT ethiopian_multiplication(17, 34);</lang>

<lang plpgsql>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

This example is incorrect. Please fix the code and remove this message.

Details: The task specifies that examples should have separate functions for doubling, halving, and checking if a number is even.

<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

  1. 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

  1. 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</lang>

Output: 

[20, 5, "STRIKE"]
[10, 10, "STRIKE"]
[5, 20, "KEEP"]
[2, 40, "STRIKE"]
[1, 80, "KEEP"]
20 * 5 = 100

A test suite: <lang ruby>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> 

Loaded suite ethopian
Started
............
Finished in 0.001 seconds.

12 tests, 12 assertions, 0 failures, 0 errors

Scheme

In Scheme, even? is a standard procedure. <lang scheme>(define (halve num) 

 (quotient num 2))

(define (double num) 

 (* num 2))

(define (*mul-eth plier plicand acc) 

 (cond ((zero? plier) acc)
       ((even? plier) (*mul-eth (halve plier) (double plicand) acc))
       (else (*mul-eth (halve plier) (double plicand) (+ acc plicand)))))

(define (mul-eth plier plicand) 

 (*mul-eth plier plicand 0))

(display (mul-eth 17 34)) (newline)</lang> Output: 

578

Seed7

Ethiopian Multiplication is another name for the peasant multiplication:

<lang seed7>const proc: double (inout integer: a) is func 

 begin
   a *:= 2;
 end func;

const proc: halve (inout integer: a) is func 

 begin
   a := a div 2;
 end func;

const func boolean: even (in integer: a) is 

 return not odd(a);

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 not even(a) then
       result +:= b;
     end if;
     halve(a);
     double(b);
   end while;
 end func;</lang>

Original source (without separate functions for doubling, halving, and checking if a number is even): [2]

Smalltalk

Works with: GNU 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>

SNUSP

<lang snusp> /==!/==atoi==@@@-@-----# 

   |   |          /-\          /recurse\    #/?\ zero

$>,@/>,@/?\<=zero=!\?/<=print==!\@\>?!\@/<@\.!\-/ 

       < @     #                 |   \=/  \=itoa=@@@+@+++++#
    /==\ \===?!/===-?\>>+# halve !     /+ !/+ !/+ !/+   \    mod10
  1. ! @ | #>>\?-<+>/ /<+> -\!?-\!?-\!?-\!?-\!

/-<+>\ > ? />+<<++>-\ \?!\-?!\-?!\-?!\-?!\-?/\ div10 ?down? | \-<<<!\=======?/\ add & # +/! +/! +/! +/! +/ \>+<-/ | \=<<<!/====?\=\ | double ! # | \<++>-/ | | \=======\!@>============/!/</lang>

This is possibly the smallest multiply routine so far discovered for SNUSP.

Tcl

<lang tcl># This is how to declare functions - the mathematical entities - as opposed to procedures proc function {name arguments body} { 

   uplevel 1 [list proc tcl::mathfunc::$name $arguments [list expr $body]]

}

function double n {$n * 2} function halve n {$n / 2} function even n {($n & 1) == 0} function mult {a b} { 

   $a < 1 ? 0 :
   even($a) ? [logmult STRUCK] + mult(halve($a), double($b))

 : [logmult KEPT] + mult(halve($a), double($b)) + $b }

  1. 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

This solution makes use of the functions odd, double, and half, which respectively check the parity, double a given natural number, or perform truncating division by two. These functions are normally imported from the nat library but defined here explicitly for the sake of completeness. <lang Ursala>odd = ~&ihB double = ~&iNiCB half = ~&itB</lang> The functions above are defined in terms of bit manipulations exploiting the concrete representations of natural numbers. The remaining code treats natural numbers instead as abstract types by way of the library API, and uses 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

Works with: nasm

, 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>
Retrieved from "https://rosettacode.org/wiki/Ethiopian_multiplication?oldid=121564"