# 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