program EthiopianMultiplication;
{
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
}
function EthiopianMultiply(a, b: Integer): Integer;
var
sum: Integer;
begin
sum := 0;
while a > 0 do
begin
if (a mod 2 = 1) then { keep only odd rows }
begin
sum := sum + b;
writeln('sum = ', sum);
end;
a := a div 2; { halve left side }
b := b * 2; { double right side }
writeln('a = ', a, ' b = ', b);
end;
EthiopianMultiply := sum;
end;
var
a, b: Integer;
begin
a := 57;
b := 18;
writeln(EthiopianMultiply(a, b));
end.
{
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
}
