Ethiopian multiplication

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

       17    34

Halving the first column:

Doubling the second column:

Strike-out rows whose first cell is even:

Sum the remaining numbers in the right-hand column:

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

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>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' (plier `div` 2) (pliand * 2) acc
       | otherwise  = ethiopicmult' (plier `div` 2) (pliand * 2) (acc + pliand)</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

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

 public static int halveInt(int halveMe){
   return halveMe << 1; //shift left
 }

 public static boolean isEven(int num){
   return num % 2 == 0;
 }

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

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 if (!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>

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>

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

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

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>

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>

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>