English Français Deutsch

Ethiopian multiplication

' Ethiopian multiplication is a method of multiplying integers using only addition, doubling, and halving.

function half(x)
set result = floor(x/2)
end function

function double(x)
set result = 2*x
end function

function even(x)
set result = (x/2 > floor(x/2))
end function

program ethiopian_mul(a,b)
relation first, second
while a >= 1
insert a, b
set a = half(a)
set b = double(b)
end while
extend third = even(first) * second
print
project third sum
end program

run ethiopian_mul(17,34)
print

Ethiopian multiplication is a method of multiplying integers using only addition, doubling, and halving.
first second third
17 34 34
8 68 0
4 136 0
2 272 0
1 544 544
third_sum
578