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: to half an integer; 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
Python <lang python> tutor = True
def halve(x):
return int(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 >>>