// Example: 57 * 18
//
// 57 18
// Halving the first column:
//
// 28 18
// 14
// 7
// 3
// 1
// Doubling the second column:
//
// 28 36
// 14 72
// 7 144
// 3 288
// 1 576
// Remove rows whose first cell is even:
//
// 18
// 28 36 x
// 14 72 x
// 7 144
// 3 288
// 1 576
// Sum the remaining numbers in the right-hand column:
// 18
// 28 -
// 14 -
// 7 162
// 3 288
// 1 576
// ====
// 1026
public class EthiopianMultiplication {
public static int ethiopianMultiply(int a, int b) {
int sum = 0;
while (a > 0) {
if (a % 2 == 1) { // keep only odd rows
sum += b;
System.out.println("sum = " + sum);
}
a /= 2; // halve left side
b *= 2; // double right side
System.out.println("a = " + a + " b = " + b);
}
return sum;
}
public static void main(String[] args) {
int a = 57;
int b = 18;
System.out.println(ethiopianMultiply(a, b));
}
}
/*
run:
sum = 18
a = 28 b = 36
a = 14 b = 72
a = 7 b = 144
sum = 162
a = 3 b = 288
sum = 450
a = 1 b = 576
sum = 1026
a = 0 b = 1152
1026
*/
