/* 

  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)
    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.