# Ethiopian multiplication

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

- A Night Of Numbers - Go Forth And Multiply (Video)
- Ethiopian multiplication
- Russian Peasant Multiplication

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