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:
- 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:
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
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%2) == 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>
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>ethiopicmult 1 pliand acc = acc + pliand ethiopicmult plier pliand acc =
if (plier `mod` 2) == 0 then ethiopicmult (plier `div` 2) (pliand * 2) acc else ethiopicmult (plier `div` 2) (pliand * 2) (acc + pliand)</lang>
Usage example from the interpreter
*Main> ethiopicmult 17 34 0 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
<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>
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
<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
, 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>