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.