Ethiopian multiplication is 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

So 17 multiplied by 34, by the Ethiopian method is 578.



Task

The task is to define three named functions/methods/procedures/subroutines:

 one to halve an integer,
 one to double an integer, and
 one to state if an integer is even.


Use these functions to create a function that does Ethiopian multiplication.



References

Ethiopian multiplication explained (BBC Video clip)
A Night Of Numbers - Go Forth And Multiply (Video)
Russian Peasant Multiplication
Programming Praxis: Russian Peasant Multiplication


on run
    {ethMult(17, 34), ethMult("Rhind", 9)}
 
    --> {578, "RhindRhindRhindRhindRhindRhindRhindRhind"}
end run
 
 
-- Int -> Int -> Int
-- or
-- Int -> String -> String
on ethMult(m, n)
    script fns
        property identity : missing value
        property plus : missing value
 
        on half(n) -- 1. half an integer (div 2)
            n div 2
        end half
 
        on double(n) -- 2. double (add to self)
            plus(n, n)
        end double
 
        on isEven(n) -- 3. is n even ? (mod 2 > 0)
            (n mod 2) > 0
        end isEven
 
        on chooseFns(c)
            if c is string then
                set identity of fns to ""
                set plus of fns to plusString of fns
            else
                set identity of fns to 0
                set plus of fns to plusInteger of fns
            end if
        end chooseFns
 
        on plusInteger(a, b)
            a + b
        end plusInteger
 
        on plusString(a, b)
            a & b
        end plusString
    end script
 
    chooseFns(class of m) of fns
 
 
    -- MAIN PROCESS OF CALCULATION
 
    set o to identity of fns
    if n < 1 then return o
 
    repeat while (n > 1)
        if isEven(n) of fns then -- 3. is n even ? (mod 2 > 0)
            set o to plus(o, m) of fns
        end if
        set n to half(n) of fns -- 1. half an integer (div 2)
        set m to double(m) of fns -- 2. double  (add to self)
    end repeat
    return plus(o, m) of fns
end ethMult