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 × 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 68 4 136 2 272 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 named 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**.

Using C++ templates, these kind of tasks can be implemented as meta-programs. The program runs at compile time, and the result is statically saved into regularly compiled code. Here is such an implementation without tutor, since there is no mechanism in C++ to output messages during program compilation.

template<int N> struct Half { enum { Result = N >> 1 }; }; template<int N> struct Double { enum { Result = N << 1 }; }; template<int N> struct IsEven { static const bool Result = (N & 1) == 0; }; template<int Multiplier, int Multiplicand> struct EthiopianMultiplication { template<bool Cond, int Plier, int RunningTotal> struct AddIfNot { enum { Result = Plier + RunningTotal }; }; template<int Plier, int RunningTotal> struct AddIfNot <true, Plier, RunningTotal> { enum { Result = RunningTotal }; }; template<int Plier, int Plicand, int RunningTotal> struct Loop { enum { Result = Loop<Half<Plier>::Result, Double<Plicand>::Result, AddIfNot<IsEven<Plier>::Result, Plicand, RunningTotal >::Result >::Result }; }; template<int Plicand, int RunningTotal> struct Loop <0, Plicand, RunningTotal> { enum { Result = RunningTotal }; }; enum { Result = Loop<Multiplier, Multiplicand, 0>::Result }; }; #include <iostream> int main(int, char **) { std::cout << EthiopianMultiplication<17, 54>::Result << std::endl; return 0; }

Content is available under GNU Free Documentation License 1.2.