/*
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
*/
object EthiopianMultiplication {
def ethiopianMultiply(a0: Int, b0: Int): Int = {
var a = a0
var b = b0
var sum = 0
while (a > 0) {
if (a % 2 == 1) { // keep only odd rows
sum += b
println(s"sum = $sum")
}
a /= 2 // halve left side
b *= 2 // double right side
println(s"a = $a b = $b")
}
sum
}
def main(args: Array[String]): Unit = {
val a = 57
val b = 18
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
*/
