/*
Etiopian multiplication (Rosetta code) in Picat.
http://rosettacode.org/wiki/Ethiopian_multiplication
"""
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
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% import util.
% import cp.
main => go.
go =>
println(ethiopian(17,34)),
ethiopian2(17,34,Z2),
println(Z2),
println(ethiopian(17,34,true)),
_ = random2(),
_ = ethiopian(random() mod 10000,random() mod 10000,true),
nl.
ethiopian(Multiplier, Multiplicand) = ethiopian(Multiplier, Multiplicand,false).
ethiopian(Multiplier, Multiplicand,Tutor) = Result =>
if Tutor then
printf("\n%d * %d:\n",Multiplier, Multiplicand)
end,
Result1 = 0,
while (Multiplier >= 1)
% println([Multiplier,Multiplicand,Result1]),
OldResult = Result1,
if not even(Multiplier) then
Result1 := Result1 + Multiplicand
end,
if Tutor then
printf("%6d % 8s\n",Multiplier,cond(OldResult=Result1,"--",Multiplicand.to_string()))
end,
Multiplier := halve(Multiplier),
Multiplicand := double(Multiplicand)
end,
if Tutor then
println(" ======="),
printf(" %8s\n",Result1.to_string()),
nl
end,
Result = Result1.
% Inspired by the Prolog solution
ethiopian2(First,Second,Product) =>
ethiopian2(First,Second,0,Product).
ethiopian2(1,Second,Sum0,Sum) =>
Sum = Sum0 + Second.
ethiopian2(First,Second,Sum0,Sum) =>
Sum1 = Sum0 + Second*(First mod 2),
ethiopian2(halve(First), double(Second), Sum1, Sum).
halve(X) = X div 2.
double(X) = 2*X.
is_even(X) => X mod 2 = 0.