begin script

2009-07-23 Reply Admin

My solution in haskell:

rpm :: Int -> Int -> Int
rpm a b = sum $ aux a b [] where         
  aux 1 b xs = b:xs
  aux a b xs | odd a     = aux (a`div`2) (b*2) (b:xs)
             | otherwise = aux (a`div`2) (b*2) xs

P.S. Does not terminate for a<=0

2009-07-23 Reply Admin

Simple PHP version. No array lists.

function rpm($val1,$val2){ echo $val1.' x '.$val2.' = ';

while($val1 >= 1){
	if($val1%2 != 0)
		$done += $val2;
	$val1 = floor($val1/2);
	$val2 *= 2;
}
echo $done;

}

juancn · 2009-07-23 Reply Admin

Simple recursive implementation in scala (first version):

def peasant(a : Int, b : Int) : Int = 
	if (a < 0 && b > 0) -peasant(-a, b)
	else if (a < 0 && b < 0) peasant(-a, -b)
	else if (a > 0 && b < 0) -peasant(a, -b)
	else if (a > b) peasant(b, a)
	else if (a == 0) 0
	else if (a == 1) b
	else if (a % 2 != 0) a+b+peasant(a/2, b*2)
	else peasant(a/2, b*2)

It's not too pretty, but supports all edge cases (since the naive algorithm only works for positive integers).

This one, is a bit denser (but more obscure):

def peasant(a : Int, b : Int) : Int = 
	if (a.abs > b.abs) peasant(b, a)
	else if (a.abs < 2) a*b
	else if (a % 2 != 0) a+b+peasant(a/2, b*2)
	else peasant(a/2, b*2)

Also note that the multiplications can be removed (either changed by shifts or by an additional if clause).

It can probably be simplified. I don't like the first if very much, and my gut tells me that it's probably a more elegant way to solve this.

I haven't read other solutions yet and I'm eagerly waiting for the winning entries :D

Addendum (2009-07-23 14:51): OoopS! That's what happens when you post without properly testing:

def peasant1(a : Int, b : Int) : Int = 
	if (a < 0 && b > 0) -peasant1(-a, b)
	else if (a < 0 && b < 0) peasant1(-a, -b)
	else if (a > 0 && b < 0) -peasant1(a, -b)
	else if (a > b) peasant1(b, a)
	else if (a == 0) 0
	else if (a == 1) b
	else if (a % 2 != 0) b+peasant1(a/2, b*2)
	else peasant1(a/2, b*2)

for{ a <- -100 to 100
	 b <- -100 to 100 } 
	assert (a*b == peasant1(a,b), "peasant1 a: " + a + ", b: " + b + " => " + peasant1(a,b) )

And the (not much) denser version:

def peasant(a : Int, b : Int) : Int = 
	if (a < 0) -peasant(-a,b)
	else if(b < 0) -peasant(a,-b)
	else if(a < 2) a*b
	else if (a % 2 != 0) b+peasant(a/2, b*2)
	else peasant(a/2, b*2)

for{ a <- -100 to 100
	 b <- -100 to 100 } 
	assert (a*b == peasant(a,b), "peasant a: " + a + ", b: " + b + " => " + peasant(a,b) )

(I might still have one or two WTFs in this code, but that's life ;) )

2009-07-23 Reply Admin

In Ruby:

def mul(a,b) (1..a).to_a.reverse.inject(0){|res,i| (i == a) ? ( [res + ((a % 2 == 1) ? b : 0) , ( a >>= 1; b <<= 1 )][0]) : res } end

PatrickBeebe · 2009-07-23 Reply Admin

C# Recursion:

    public static int RussianMultiplication(int x, int y)
    {
        if (x == 0 || y == 0) return 0;
        int sign = (x >> 31 | 1) * (y >> 31 | 1); 
        x *= (x >> 31 | 1);
        y *= (y >> 31 | 1);
        if (y <  x)
            return sign*RecursiveRussianMultiplication(y, x);
        else
            return sign*RecursiveRussianMultiplication(x, y);
    }

    public static int RecursiveRussianMultiplication(int x, int y)
    {
        if (x ==-1 || x == 1) return y;
        return (x % 2 == 0 ? 0 : y) + RecursiveRussianMultiplication(x /= 2, y += y);
    }

2009-07-23 Reply Admin

Here's mine, in python, with doctests, in 4 variations... it was a slow day at work :P

"""
Russian peasant multiplication functions. 

>>> russian_mult(18, 23)
414
>>> russian_mult(2, 4)
8
>>> russian_mult(-2, 4)
-8
>>> russian_mult(-2, -4)
8
>>> russian_mult_gen(18, 23)
414
>>> russian_mult_gen(2, 4)
8
>>> russian_mult_gen(-2, 4)
-8
>>> russian_mult_gen(-2, -4)
8
>>> russian_mult_opt(18, 23)
414
>>> russian_mult_opt(2, 4)
8
>>> russian_mult_opt(-2, 4)
-8
>>> russian_mult_opt(-2, -4)
8
>>> russian_mult_rec(18, 23)
414
>>> russian_mult_rec(2, 4)
8
>>> russian_mult_rec(-2, 4)
-8
>>> russian_mult_rec(-2, -4)
8
"""

def correct_values(func):
        """
        This decorator function 'corrects' the inputs of the
        other functions. It does this in two ways:
          1) It ensures that the numerically lowest absolute value is the lhs. This is to minimise the looping as this is the loop control
          2) It ensures negative multiplication can take place. It does this by multiplying both sides by -1 if the lhs is less than -1.
        This can be removed by taking away the '@correct_values' line before a function to return to a 'pure' russian peasant multiplication algorithm
        >>> def echo(lhs, rhs):
        ...     print lhs, rhs
        >>> correct_values(echo)(-23, -18)
        18 23
        >>> correct_values(echo)(-43245, 2)
        2 -43245
        """
        def corrector(lhs, rhs):
                lhs, rhs = (rhs, lhs) if abs(rhs) < abs(lhs) else (lhs, rhs)
                lhs, rhs = (lhs * -1, rhs * -1) if lhs < 0 else (lhs, rhs)
                return func(lhs, rhs)
        corrector.__doc__ = func.__doc__
        return corrector

@correct_values
def russian_mult(lhs, rhs):
        """
        Simplest, most exact conversion of 'russian peasant multiplication'. 
        Builds a list of pairs and then iterates over them to find the result
        
        >>> russian_mult(18, 23)
        414
        """
        mult_list = [(lhs, rhs)]
        while mult_list[-1][0]:
                mult_list.append( (mult_list[-1][0] / 2, 
                                                   mult_list[-1][1] * 2) )
        result = 0
        for line in mult_list:
                result += line[1] if line[0] % 2 else 0
        return result
        
@correct_values
def russian_mult_opt(lhs, rhs):
        """
        'Optimised' version of the first algorithm. It removes the
        need to store the results by calculating the result in a 
        single pass.
        
        >>> russian_mult_opt(18, 23)
        414
        """
        result = 0
        while lhs:
                result += rhs if lhs % 2 else 0
                lhs /= 2
                rhs *= 2
        return result

@correct_values
def russian_mult_gen(lhs, rhs):
        """ 
        Generator version of the russian_mult_opt function.
        Uses a python generator to get values. This is then
        given to a reduce which iterates over the generator
        and produces the result.
        
        >>> russian_mult_gen(18, 23)
        414
        """
        def build_list(lhs, rhs):
                while lhs:
                        yield rhs if lhs % 2 else 0
                        lhs /= 2
                        rhs *= 2
        return reduce(lambda x, y: x + y, build_list(lhs, rhs))
@correct_values
def russian_mult_rec(lhs, rhs):
        """
        'Russian peasant multiplication' reduced to a recursive one-liner.
        Returns 0 when lhs is 0, otherwise recursion, adding the rhs to the resu
lt
        when called with an odd lhs value.
        The recursion is done within the inline _russian_mult_rec function so as
 to
        avoid issues with the @correct_values decorator. If this isn't done then
 infinite
        recursion can occur and correct values aren't obtained.
        
        >>> russian_mult_rec(18, 23)
        414
        """
        def _russian_mult_rec(lhs, rhs):
                return 0 if not lhs else (rhs if lhs % 2 else 0) + _russian_mult
_rec(lhs / 2, rhs * 2)
        return _russian_mult_rec(lhs, rhs)

if __name__ == '__main__':
    import doctest
    doctest.testmod()

I also added a 'correction' decorator to allow multiplication with negatives and to switch the inputs if the larger one is first (minor optimisation)

2009-07-23 Reply Admin

Here is a C# version that multiplies two text numbers

private static string Multiply(string number1, string number2)
        {
            string[,] multiplicationSteps = {{ number1, number2 }};
            while (CanAddStep(multiplicationSteps))
            {
                multiplicationSteps = AddStep(multiplicationSteps);
            }
            multiplicationSteps = RemoveEvenFactor1Steps(multiplicationSteps);
            string result = AddAllFactor2Steps(multiplicationSteps);
            return result;
        }

        private static string AddAllFactor2Steps(string[,] multiplicationSteps)
        {
            string lastStep = string.Empty;
            string result = string.Empty;
            for (int index = 0; index < multiplicationSteps.GetLength(0); index++)
            {
                lastStep = result;
                result = AddNumbers(lastStep, multiplicationSteps.GetValue(index, 1).ToString());
            }
            return result;
        }

        private static string AddNumbers(string number1, string number2)
        {
            string addendum1 = number1.PadLeft(number2.Length, '0');
            string addendum2 = number2.PadLeft(number1.Length, '0');
            StringBuilder result = new StringBuilder();
            string lastStep = string.Empty;
            string currentStep = string.Empty;
            for (int index = addendum1.Length - 1; index >= 0; index--)
            {
                lastStep = currentStep;
                currentStep = AddDigits(addendum1[index], addendum2[index]);
                if (string.IsNullOrEmpty(currentStep))
                {
                    currentStep = "0";
                }
                if (lastStep.Length > 1)
                {
                    currentStep = AddNumbers(lastStep[0].ToString(), currentStep);
                }
                int lastDigitOfCurrentStep = currentStep.Length - 1;
                result.Insert(0, currentStep[lastDigitOfCurrentStep]);
            }
            if (currentStep.Length > 1)
            {
                result.Insert(0, currentStep[0]);
            }
            return result.ToString();
        }

        private static string[,] RemoveEvenFactor1Steps(string[,] multiplicationSteps)
        {
            int newArraySize = multiplicationSteps.GetLength(0);
            string[,] result = new string[newArraySize, 2];
            Array.Copy(multiplicationSteps, result, multiplicationSteps.Length);
            int indexStop = result.GetLength(0) - 1;
            for (int index = 0; index < indexStop; index++)
            {
                string lastValue = result.GetValue(index, 0).ToString();
                int lastDigitOfLastValue = lastValue.Length - 1;
                string halfLastDigit = GetHalfOfDigit(lastValue[lastDigitOfLastValue]);
                if (halfLastDigit.Length == 1)
                {
                    result.SetValue(string.Empty, index, 0);
                    result.SetValue(string.Empty, index, 1);            
                }
            }
            return result;
        }

        private static string[,] AddStep(string[,] multiplicationSteps)
        {
            int newArraySize = multiplicationSteps.GetLength(0) + 1;
            string[,] result = new string[newArraySize, 2];
            Array.Copy(multiplicationSteps, result, multiplicationSteps.Length);
            int index = multiplicationSteps.GetLength(0) - 1;
            string nextNumber1 = GetHalfOfNumber(multiplicationSteps.GetValue(index, 0).ToString());
            string nextNumber2 = DoubleNumber(multiplicationSteps.GetValue(index, 1).ToString());
            int nextArrayLocation = multiplicationSteps.GetLength(0);
            result.SetValue(nextNumber1, nextArrayLocation, 0);
            result.SetValue(nextNumber2, nextArrayLocation, 1);
            return result;
        }

        private static string DoubleNumber(string number)
        {
            StringBuilder result = new StringBuilder();
            string lastStep = string.Empty;
            string currentStep = string.Empty;
            for (int index = number.Length - 1; index >= 0 ; index--)
            {
                lastStep = currentStep;
                currentStep = DoubleDigit(number[index]);
                if (string.IsNullOrEmpty(currentStep))
                {
                    currentStep = "0";
                }
                if (lastStep.Length > 1)
                {                    
                    currentStep = AddNumbers(lastStep[0].ToString(), currentStep);
                }
                int lastDigitOfCurrentStep = currentStep.Length - 1;
                result.Insert(0, currentStep[lastDigitOfCurrentStep]);
            }
            if (currentStep.Length > 1)
            {
                result.Insert(0, currentStep[0]);
            }
            return result.ToString();
        }

        private static string DoubleDigit(char digit)
        {
            switch (digit)
            {
                case '0':
                    return "0";
                case '1':
                    return "2";
                case '2':
                    return "4";
                case '3':
                    return "6";
                case '4':
                    return "8";
                case '5':
                    return "10";
                case '6':
                    return "12";
                case '7':
                    return "14";
                case '8':
                    return "16";
                case '9':
                    return "18";
            }
            return string.Empty;
        }

        private static bool CanAddStep(string[,] multiplicationSteps)
        {
            int index = multiplicationSteps.GetLength(0) - 1;
            string halfValue = GetHalfOfNumber(multiplicationSteps.GetValue(index, 0).ToString());
            if (string.IsNullOrEmpty(halfValue))
            { return false; }
            else
            { return true; }
        }

        private static string GetHalfOfNumber(string number)
        {
            StringBuilder result = new StringBuilder();
            string lastStep = string.Empty;
            string currentStep = string.Empty;
            for (int index = 0; index < number.Length; index++)
            {
                lastStep = currentStep;
                currentStep = GetHalfOfDigit(number[index]);
                if (string.IsNullOrEmpty(currentStep))
                {
                    currentStep = "0";
                }
                if (lastStep.Length > 1)
                {
                    int lastDigitOfLastStep = lastStep.Length - 1;
                    currentStep = AddNumbers(lastStep[lastDigitOfLastStep].ToString(), currentStep);
                }
                if (currentStep[0] != '0')
                {
                    result.Insert(0, currentStep[0]);
                }
            }
            return result.ToString();
        }

        private static string GetHalfOfDigit(char digit)
        {
            switch (digit)
            {
                case '0':
                    return "0";
                case '1':
                    return "05";
                case '2':
                    return "1";
                case '3':
                    return "15";
                case '4':
                    return "2";
                case '5':
                    return "25";
                case '6':
                    return "3";
                case '7':
                    return "35";
                case '8':
                    return "4";
                case '9':
                    return "45";
            }
            return string.Empty;
        }

        private static string AddDigits(char digit1, char digit2)
        {
            switch (digit1)
            {
                case '0':
                    switch (digit2)
                    {
                        case '0':
                            return "0";
                        case '1':
                            return "1";
                        case '2':
                            return "2";
                        case '3':
                            return "3";
                        case '4':
                            return "4";
                        case '5':
                            return "5";
                        case '6':
                            return "6";
                        case '7':
                            return "7";
                        case '8':
                            return "8";
                        case '9':
                            return "9";
                    }
                    break;
                case '1':
                    switch (digit2)
                    {
                        case '0':
                            return "1";
                        case '1':
                            return "2";
                        case '2':
                            return "3";
                        case '3':
                            return "4";
                        case '4':
                            return "5";
                        case '5':
                            return "6";
                        case '6':
                            return "7";
                        case '7':
                            return "8";
                        case '8':
                            return "9";
                        case '9':
                            return "10";
                    }
                    break;
                case '2':
                    switch (digit2)
                    {
                        case '0':
                            return "2";
                        case '1':
                            return "3";
                        case '2':
                            return "4";
                        case '3':
                            return "5";
                        case '4':
                            return "6";
                        case '5':
                            return "7";
                        case '6':
                            return "8";
                        case '7':
                            return "9";
                        case '8':
                            return "10";
                        case '9':
                            return "11";
                    }
                    break;
                case '3':
                    switch (digit2)
                    {
                        case '0':
                            return "3";
                        case '1':
                            return "4";
                        case '2':
                            return "5";
                        case '3':
                            return "6";
                        case '4':
                            return "7";
                        case '5':
                            return "8";
                        case '6':
                            return "9";
                        case '7':
                            return "10";
                        case '8':
                            return "11";
                        case '9':
                            return "12";
                    }
                    break;
                case '4':
                    switch (digit2)
                    {
                        case '0':
                            return "4";
                        case '1':
                            return "5";
                        case '2':
                            return "6";
                        case '3':
                            return "7";
                        case '4':
                            return "8";
                        case '5':
                            return "9";
                        case '6':
                            return "10";
                        case '7':
                            return "11";
                        case '8':
                            return "12";
                        case '9':
                            return "13";
                    }
                    break;
                case '5':
                    switch (digit2)
                    {
                        case '0':
                            return "5";
                        case '1':
                            return "6";
                        case '2':
                            return "7";
                        case '3':
                            return "8";
                        case '4':
                            return "9";
                        case '5':
                            return "10";
                        case '6':
                            return "11";
                        case '7':
                            return "12";
                        case '8':
                            return "13";
                        case '9':
                            return "14";
                    }
                    break;
                case '6':
                    switch (digit2)
                    {
                        case '0':
                            return "6";
                        case '1':
                            return "7";
                        case '2':
                            return "8";
                        case '3':
                            return "9";
                        case '4':
                            return "10";
                        case '5':
                            return "11";
                        case '6':
                            return "12";
                        case '7':
                            return "13";
                        case '8':
                            return "14";
                        case '9':
                            return "15";
                    }
                    break;
                case '7':
                    switch (digit2)
                    {
                        case '0':
                            return "7";
                        case '1':
                            return "8";
                        case '2':
                            return "9";
                        case '3':
                            return "10";
                        case '4':
                            return "11";
                        case '5':
                            return "12";
                        case '6':
                            return "13";
                        case '7':
                            return "14";
                        case '8':
                            return "15";
                        case '9':
                            return "16";
                    }
                    break;
                case '8':
                    switch (digit2)
                    {
                        case '0':
                            return "8";
                        case '1':
                            return "9";
                        case '2':
                            return "10";
                        case '3':
                            return "11";
                        case '4':
                            return "12";
                        case '5':
                            return "13";
                        case '6':
                            return "14";
                        case '7':
                            return "15";
                        case '8':
                            return "16";
                        case '9':
                            return "17";
                    }
                    break;
                case '9':
                    switch (digit2)
                    {
                        case '0':
                            return "9";
                        case '1':
                            return "10";
                        case '2':
                            return "11";
                        case '3':
                            return "12";
                        case '4':
                            return "13";
                        case '5':
                            return "14";
                        case '6':
                            return "15";
                        case '7':
                            return "16";
                        case '8':
                            return "17";
                        case '9':
                            return "18";
                    }
                    break;
            }
            return string.Empty;
        }

2009-07-23 Reply Admin

An even better newlisp oneliner:

(define (rmul x y) (if (= x 1) y (+ (* (& x 1) y) (rmul (>> x) (<< y)))))

Thanks to the poster who noticed that the and operator is of use here, it saved a comparison operation.

2009-07-23 Reply Admin

C++ :)

#include <iostream>
template <typename T>
class RussianNumerable
{
protected:
T value;
public:
bool printoutput;
RussianNumerable(T val)
{
	value = (T)val;
	printoutput = false;
}

//must maintain compatibility with regular numbers!
RussianNumerable & operator = (const T &in)
{
	value = in;
	return *this;
}

 operator T() 
{
	return value;
}

//correct way of multiplying!!!
T & operator * (const T &in)
{
	T n1 = value;
	T n2 = in; 
	T answer = 0;
	T first = 0;
	T second = 0;
	if(printoutput)
	{
		std::cout<<n1<<" x "<<n2<<"\n";
	}
	for(int i = n2; i != 1;)
	{
		if(i == n2)
		{
			first = n2*2;
		}
		n1/=2;
		n2*=2;
		if(printoutput)
		{
			std::cout<<n1<<"    "<<n2<<"\n";
		}
		for(int a=0;a<2000000;a+=3){a-=2;} //executes too fast?
		if((int)n1 == 1 || (int)n1 == -1)
		{
			second = n2;
			break;
		}
	}
	if(printoutput)
	{
		std::cout<<"========\n";
	}
	answer = first+second;
	
	return answer;
}

};
int main()
{
RussianNumerable<float> a = 18;
RussianNumerable<float> b = 23;
a.printoutput = true;
std::cout<<a*b<<"\n";
std::cin.get();
return 0;

}

2009-07-23 Reply Admin

First attempt, in Python.

def multiply(x, y):
    answer = 0
    while x:
        x, odd = divmod(x, 2)
        if odd:
            answer += y
        y += y
    return answer

samanddeanus · 2009-07-23 Reply Admin

Scheme with objects represented as higher order functions using message passing and GOTO done with call-with-current-continuation:

(define (adder x)
  (let ((total x))
    (lambda (op)
      (cond ((eq? op 'total) total)
	    ((eq? op 'add) (lambda (x) (set! total (+ total x)) total))
	    (else (error "Invalid operation -- ADDER" op))))))

(define (halver x)
  (let ((value x))
    (lambda (op)
      (cond ((eq? op 'value) value)
	    ((eq? op 'halve) (set! value (quotient value 2)) value)
	    (else (error "Invalid operation -- HALVER" op))))))

(define (doubler x)
  (let ((value x))
    (lambda (op)
      (cond ((eq? op 'value) value)
	    ((eq? op 'double) (set! value (+ value value)))
	    (else (error "Invalid operation -- DOUBLER" op))))))

(define (mul x y)
  (let ((left (halver (abs x)))
	(right (doubler (if (negative? x)
			   (- y)
			   y)))
	(result (adder 0)))
    ((call-with-current-continuation
      (lambda (goto)
	(letrec ((ten (lambda ()
			(if (zero? (left 'value))
			    (result 'total)
			    (goto twenty))))
		 (twenty (lambda ()
			   (if (odd? (left 'value))
			       ((result 'add) (right 'value)))
			   (left 'halve)
			   (right 'double)
			   (goto ten))))
	  ten))))))

dee · 2009-07-23 Reply Admin

One more; MySQL stored function:

DELIMITER WTF

CREATE FUNCTION peasant (argLeft BIGINT, argRight BIGINT)
  RETURNS BIGINT
  DETERMINISTIC
BEGIN
  DECLARE result BIGINT DEFAULT 0;
  IF argLeft = 0 THEN
    RETURN 0;
  END IF;

  -- negative numbers
  IF argLeft < 0 THEN
    SET argLeft = -argLeft;
    SET argRight = -argRight;
  END IF;
  
  -- helper table for multiplication rows
  CREATE TEMPORARY TABLE peasant_helper (
    itemLeft BIGINT NOT NULL,
    itemRight BIGINT NOT NULL
  );
  
  -- insert the multiplication rows
  WHILE argLeft > 0 DO
    INSERT INTO peasant_helper VALUES (argLeft, argRight);
    SET argLeft = argLeft >> 1;
    SET argRight = argRight + argRight;
  END WHILE;

  -- calculate the sum of the right side 
  -- of the rows with an odd left side
  SET result = (
    SELECT
      SUM(itemRight)
    FROM
      peasant_helper
    WHERE
      itemLeft & 1
  );

  DROP TEMPORARY TABLE peasant_helper;
  RETURN result;
END
WTF

DELIMITER ;

mysql> SELECT peasant(18,23);
+----------------+
| peasant(18,23) |
+----------------+
|            414 |
+----------------+
1 row in set (0.00 sec)

Addendum (2009-07-23 16:04): Accumulators are so non-inventive. Try harder, people!

2009-07-23 Reply Admin

I've seen a couple of Erlang solutions, but neither of them did concurrency, so here:

-module(peasant).
-export([mul/2,pairs/3,filter/1,flatten/1,add/1]).

pairs(0,_,FilterPid) ->
    FilterPid ! over;
pairs(X,Y,FilterPid) ->
    FilterPid ! [X,Y],
    pairs(X div 2, Y*2, FilterPid).

filter(FlattenPid) ->
    receive
        over ->
            FlattenPid ! over;
        [X,Y] ->
            if
                (X rem 2)==1 ->
                    FlattenPid ! [X,Y]
            end,
            filter(FlattenPid)
    end.

flatten(AddPid) ->
    receive
        over ->
            AddPid ! over;
        [_,Y] ->
            AddPid ! Y,
            flatten(AddPid)
    end.

add(MulPid,Total) ->
    receive
        over ->
            MulPid ! Total;
        X ->
            add(MulPid,Total+X)
    end.

add(MulPid) ->
    add(MulPid,0).

mul(X, Y) ->
    spawn(peasant,pairs,
          [X,Y,
           spawn(peasant,filter,
                 [spawn(peasant,flatten,
                        [spawn(peasant,add,[self()])])])]),
    receive
        Res ->
            Res
    end.

2009-07-23 Reply Admin

Here's a simple recursive algorithm, written in python (I'm a Plone/Zope developer, so it's what I use regularly... plus, it's awesomest). A little colour for that cozy vi feeling ;)

I thought about handling the negative numbers in the recursive part, which is much more satisfying, algorithmically, but that would mean calculating the sign of left for every recursion, rather than just once. In my solution, calculating the sign takes work on the order of O(1); the alternate would be on the order of O(log(left)). It makes more sense to just pass the magnitudes in for recursion, and slap the sign back on afterwards. I'm sure that's how the Russians are tought to do it, anyway.

def _russian (left, right):
  result = {}
  if left:
    result[left] = right
    result.update(_russian(left // 2, right * 2))
  return result

def russian (left, right):
  sign = left * right / abs(left * right)
  return sign * sum([
    r for l, r in _russian(abs(left), abs(right)).items()
    if l % 2
  ])

2009-07-23 Reply Admin

I think I am ahead on longest version. ;)

In the interest of being true to the problem, I used no built in math functions on the numbers passed in (which is why it is all string manipulation). I did use built in math functions with the integers used for indexing, but only addition and subtraction.

The Multiplication function works just fine with non-negative integers passed in as strings, but will give unpredictable results if anything else is passed in, which is a big WTF.

I tried to use as many WTFs in the function as possible, but don't know how to count them.

It is very easy to read, so maybe I should have obfuscated it to make it unmainable.

I think I have come up with the most WTF version so far (in a commonly used language), and would really like that sticker. ;)

The real WTF is the amount of time taken to write a simple multiplication function.

2009-07-23 Reply Admin

I, too, tried to pack mine with any many WTFs as possible, but no-one even seems to have noticed. Hell, mine crashes and burns as written.

Way to code review, everyone...

2009-07-23 Reply Admin

Qwertyuiopas:
Any time you use n = n * 2 or n *=2, n += n would work. Any time you use n = n * -1 or n *= -1, n = -n would work.
Anyone using * for 2 or -1 has NO EXCUSE.

The excuse is called compilers. Code what you mean and not what you want the compiler to do. The compiler knows what is fast better then you do more often then not. If you want a double, double it. 'n*=2' will take an identical number of cycles as 'n+=n' on modern CPUs. All you've done is obfuscate that you wanted to double something to increment something by something else, that happens to be itself, so that it is double what you wanted it to be.

Same with the left shift and right shift by 1. Do you mean multiply by two or do you actually want to use it as a bit mask? The compiler will probably change it to a bit-wise operator if it is faster anyways. Or as it more likely the case, the arithmetic operator is just as fast as the bit-wise operator. All you've accomplished is made it harder on humans and taken options away from the compiler.

2009-07-23 Reply Admin

My C++ version is here:

int multiply(int a, int b) { int aa[32]; int bb[32]; int i = 0; aa[i] = a; bb[i] = b; while(a!=1) { a/=2; b*=2; i++; aa[i]=a; bb[i]=b; } int result = 0; for(int ii=0;ii<=i;ii++) { if ((aa[ii]&1) == 1) { result += bb[ii]; } } return result; }

2009-07-23 Reply Admin

WTF, no PowerShell yet?

begin script

clear-host

$left = 18 $right = 23 $sum = 0

if ($left -lt 0) { $left *= -1 $right *= -1 }

while ($left -gt 0) { if (($left % 2) -eq 1) { $sum += $right }

$left = [Math]::Floor($left / 2) $right = $right * 2 }

write-host $sum

end script

Should handle negative numbers and 0 but haven't tested it too much because I couldn't be arsed. For the same reason, no bitwise operators or recursion.

ajp · 2009-07-23 Reply Admin

did this one that handles 0 and negative numbers.

//F# Version 1.9.6.16
#light
let isOdd x = 
  (x%2) = 1

let abs x =
  if x < 0 then -x else x

let rec mult x y = 
  match x with
  | 0 -> 0
  | 1 -> y
  | _ when isOdd x -> y + mult (x/2) (y*2)
  | _ -> mult (x/2) (y*2)
  
let Multiply a b =
  match a with
  | _ when ((a < 0) && (b > 0)) or ((a>0) && (b<0)) -> -mult (abs a) (abs b)
  | _ -> mult (abs a) (abs b)

2009-07-23 Reply Admin

Larry H.:

unsigned russian(unsigned a, unsigned b) 
{ 
   return ((a & 1) ? b : 0) + ((a & ~1) ? russian(a>>1, b<<1) : 0);
}

Not tested.

Now that's what I was looking for. No fair using standard multiplication, division or mod operators. This code gets the job done using only shifts. Bravo!

2009-07-23 Reply Admin

operations are done in wrong order
not doing correct operations (a & 1 is and-operation, not testing whether it's odd or even -- proper solution tests for decimal number last digit equals 1,3,5,7 or 9 to test if it's odd - otherwise it's different from how you do it by hand)
not following the rules (it said just ONE FUNCTION is allowed)

2009-07-23 Reply Admin

The assembly language submissions seemed a little too high level, so I went for Verilog. It compiles, probably synthesizes, but I didn't simulate it...

Implement it in a CPLD, no processor required :)

Just saw Ikegami's discrete logic solution for 4-bit numbers. Cool! Mine does 32-bit numbers though :P

module multiply (
    input               clock,
    input               reset,
    
    input               start,
    input       [31:0]  a,
    input       [31:0]  b,
    
    output reg          finished,
    output reg  [63:0]  c
);

    reg     [4:0]   count;

    reg     [31:0]  a_latched;
    reg     [63:0]  b_latched;
    
    always @(posedge clock or posedge reset)
    begin
        if (reset == 1'b1) begin
            finished    <= 1'b0;
            a_latched   <= 32'b0;
            b_latched   <= 64'b0;
            c           <= 64'b0;
            count       <= 5'd0;
        end else begin
            
            finished    <= 1'b0;
            
            if (start == 1'b1) begin
                count[4:0] <= 5'd31;
                
                a_latched[31:0] <= a[31:0];
                b_latched[63:0] <= { 32'b0, b[31:0] };
                c               <= 64'b0;
                
            end else if (|count) begin
                if ( a_latched[0] == 1'b1 ) begin
                    c[63:0] <= c[63:0] + b_latched[63:0];
                end
                    
                a_latched[31:0] <= { 1'b0, a_latched[31:1] };
                b_latched[63:0] <= { b_latched[62:0], 1'b0 };
                    
                count[4:0] <= count[4:0] - 5'd1;
                    
                if (count[4:0] == 5'd1) begin
                    finished    <= 1'b1;
                end
            end
        end
    end

endmodule

2009-07-23 Reply Admin

Scala:

def russianMultiply(a:Int, b:Int) = {
  def loop(x:Int, y:Int, list:List[(Int,Int)]):List[(Int,Int)] =
      if(x == 0) list else loop(x >> 1, y << 1, (x, y) :: list)
  loop(a, b, Nil).filter(_._1 % 2 == 1).foldLeft(0)(_+_._2)
}

2009-07-23 Reply Admin

In addition to Python3, there is also a non-recursive, one-line, one-statement solution in Haskell:

mul a b =
    let (_,_,p) = foldl (\(a,b,p) _ -> (div a 2,b*2,p+b*mod a 2)) (a,b,0) [1..a] in p

Or, more efficiently:

mul a b =
    let (_,_,p) = foldl (\(a,b,p) _ -> (div a 2,b*2,p+b*mod a 2)) (a,b,0) [1..ceiling$logBase 2$fromIntegral a+1] in p

However, recursion (over "interm") makes it more clear:

mul a b =
    let interm = (a,b) : [ (div a 2,b*2) | (a,b) <- interm ]
        cut_interm = takeWhile ((0<).fst) interm
    in
    sum [ b | (a,b) <- cut_interm, odd a ]

Maurits · 2009-07-23 Reply Admin

80 characters, Perl, requires positive whole multiplicands:

perl -e "($a,$b)=@ARGV;map{$c+=$b<<$_ if$a>>$_&1}(0..log($a)/log 2);print$c" 8 7

http://blogs.msdn.com/matthew_van_eerde/archive/2009/07/23/bad-perl-russian-peasant-multiplication-algorithm.aspx

MichaelWH · 2009-07-23 Reply Admin

In Haskell, dealing with negatives.

peasant :: Int -> Int -> Int
peasant 1 y = y
peasant x y
    | x < 0     = -(peasant (-x) y)
    | odd x     = y + p
    | otherwise = p
  where
    p = peasant (x `div` 2) (y * 2)

andyesslinger · 2009-07-23 Reply Admin

Hopefully this is original enough... Batch file...

@echo ON REM Russian Peasant Multiplication via Batch file

@echo OFF set /A m1 = %1 set /A m2 = %2 set /A EvenOdd=0 set /A EvenOddRet=0 set /A Calc=0

REM Cheat so we know if the output is correct. set /A mval = %1 * %2

REM Decide if we're going to use the given numbers... Set /A EvenOdd = %m1% goto FindEvenOdd

REM Begin the loop :Start

REM Odd Numbers are added to the accumulator REM Even numbers are displayed but not used if %EvenOddRet% equ 0 echo '--- %m1% x %m2%' if %EvenOddRet% equ 1 echo ' %m1% x %m2%' if %EvenOddRet% equ 1 set /A Calc = calc + %m2%

REM Divide m1; multiply m2 set /A m1 = (%m1% / 2) set /A m2 = %m2% * 2

REM Reset the storage to the current number Set /A EvenOdd = %m1%

goto FindEvenOdd

REM Jump back after determining Even/Odd :Back

REM if m1 is zero or less we're done; print the totals... if %m1% GTR 0 goto Start

echo 'Answer: %mval%' echo 'Calc : %Calc%' pause

REM Subtract 10 from the current number until we have a single digit REM then hit the brute force code to see if it's even/odd :FindEvenOdd if %EvenOdd% GTR 9 set /A EvenOdd = %EvenOdd% - 10

if %EvenOdd% GTR 9 goto FindEvenOdd

if %EvenOdd% EQU 0 Set /A EvenOddRet = 0
if %EvenOdd% EQU 1 Set /A EvenOddRet = 1
if %EvenOdd% EQU 2 Set /A EvenOddRet = 0
if %EvenOdd% EQU 3 Set /A EvenOddRet = 1
if %EvenOdd% EQU 4 Set /A EvenOddRet = 0
if %EvenOdd% EQU 5 Set /A EvenOddRet = 1
if %EvenOdd% EQU 6 Set /A EvenOddRet = 0
if %EvenOdd% EQU 7 Set /A EvenOddRet = 1
if %EvenOdd% EQU 8 Set /A EvenOddRet = 0
if %EvenOdd% EQU 9 Set /A EvenOddRet = 1

GOTO Back

2009-07-23 Reply Admin

Here´s my solution in PROLOG:

russian_mul(X,1,Erg):-
  !, Erg = X.

russian_mul(X,Y,Erg):-
  1 is Y mod 2,
  YHalf is Y // 2,
  XDouble is X * 2,
  russian_mul(XDouble, YHalf, RekErg),
  Erg is X + RekErg.

russian_mul(X,Y,Erg):-
  0 is Y mod 2,
  YHalf is Y // 2,
  XDouble is X * 2,
  russian_mul(XDouble, YHalf, RekErg),
  Erg = RekErg.

2009-07-23 Reply Admin

A proper 6502 assembler solution.

Features:

multiplies two 8-bit numbers with 16 bit result
inner loop of only 17 clock cycles per iteration
worst case behaviour of 40 clock cycles per iteration
minimizes number of iterations
total execution time: 25 - 320 cycles (i.e. only 3x slower (worst case) than MUL on Intel 8088)
43 bytes size
relocatable to about anywhere in address space
uses C64-friendly memory locations

; INPUT  = op1 in A, op2 in X
; OUTPUT = low byte in X, high byte in Y
; memory locations used as temp space = $fb, $fc, $fd
	stx $fc    ; save op2
	cmp $fc    ; compare both operands
	bcc noswap ; swap them unless op1 < op2
	sta $fc    ; save op1 instead of op2
	txa        ; swap op2 for op1
noswap:
	ldx #$00   ; prepare result low byte
	stx $fd    ; clear high byte of op2
	ldy #$00   ; prepare result high byte
	beq begin  ; skip shift of op2 for first iteration

loop:
	asl $fc    ; multiply op2 by 2, low byte
	rol $fd    ; multiply op2 by 2, high byte
begin:
	lsr        ; divide op1 by 2
	bcs add    ; if op1 was odd before division, add op2
	bne loop   ; if op1 is not zero repeat loop
	rts        ; otherwise return result

add:
	sta $fb    ; save current value of op1
	clc        ; prepare addition
	txa        ; fetch low byte
	adc $fc    ; add op2, low byte
	tax        ; store low byte
	tya        ; fetch high byte
	adc $fd    ; add op2, high byte
	tay        ; store high byte
	lda $fb    ; restore op1
	bne loop   ; if op1 is not zero repeat loop
	rts        ; otherwise return result

mol1111 · 2009-07-23 Reply Admin

I created index of all entries. Languages sorted by their name, entries sorted by order in which they appear. If you cannot find your entry, look in the "Other" (for languages with only one entry) or "Unspecified" (if you have not specified language and it was not easily deductable).

ABAP dv 277800 Someone 277998 278677

APL Captain Obvious 277817 Steve the Cynic 278029 278054

Assembler Dascandy x86, ARM 277793 Bosshog 6502 277804 278103 Stalker x64 277911 kastein IA64 277930 Bob Montgomery 6502 278147 Lunkwill m68k 278154 flax ARM 278263 Kevin Kofler m68k 278381 Gumpy Guss PDP-8 278418 bd_ Rabbit 2000 278438 Chris Walton x86 278499 C x86 278562 Anonymous ARM 278710 Moe 6502 279053

BASIC Alex Papadimoulis VBScript 277748 Kees QB/VB ? 277803 Takis VB.Net 277814 RayS VBA 277842 278407 djjeavons VB.Net 277887 Slinky VB? 278001 antelopelovefan VBA 278068 JoLoCo Sinclair 278126 Yorick Sinclair 278372 bluebearr AutoIt 278460 James VBA 278489 Don Knisley VBA 278534 k1 278548 278550 Takis VB.Net 278799 some VBA coder VBA 278862

bc/dc Nick Pope 277951 278207

brainfuck Qwertyuiopas 278037 Eyrieowl 278241 Philipp 278837

Brilliant Paula 277801

C/C++ Tim 277783 277784 Larry H. 277798 Stefan 277813 Zombywuf templates 277815 darkwraith 277832 KimmoS 277850 KnoNoth 277851 whileloopsareugly 277873 TerraNova 277876 YES WE CAN! 277912 little3lue templates 277914 GWO 277924 277962 277964 277965 ponky 277952 278066 hh10k 277969 shub 277985 278055 _flt 278003 Harleqin 278009 Zor 278046 278053 278059 Kman templates 278062 278880 Fooba 278100 serg 278113 hornet 278173 278191 Bored 278175 xtremezone 278176 278190 278205 Haggis 278189 Ronuk Raval 278209 Alan Woodland templates 278240 Михаил 278267 OmnipotentEntity 278270 MG 278284 Resistance Assembler 278321 Rob Hulswit templates 278329 278331 mxsscott 278342 Rob H 278352 J.I. 278356 Sam 278391 spiderlama 278416 0ffh 278451 Chris Walton 278499 demo templates 278528 khahem 278731 Mr. Black 278769 n1L templates 278844 markwhi 278906 278908 Lightnix 278994 TP 279023

C# Jay 277786 Dopefish 277788 Brettm 277812 Dan 277834 277856 Damien 277843 Felix Ungman 277867 GM 277894 Fabio Lima 277922 277957 Osno 277972 277997 278021 groknroll 277980 campkev 277991 277994 278078 278081 Sean Handley 277995 Oliver Klozoff 278000 WraithShade 278057 Floyd LINQ 278082 chriswatson LINQ 278106 Codism LINQ 278139 Jared Youtsey 278149 David C. 278161 278226 jeff.woodhull LINQ 278201 It'sMe 278203 Shiftyness 278236 stannius LINQ 278261 blueberry 278286 VirtualBlackFox LINQ 278292 nine 278293 TNProgrammer 278302 dontera 278324 The Answer + 2 278328 hornet threads 278340 Rob H 278352 Lernin ur codez 278376 PatrickBeebe 278393 Veryth LINQ 278433 brian 278450 Thomas Eyde 278456 Joel 278461 joeyadams 278471 jnz 278473 JXO 278474 czetts 278846 HCGL 278911 Jeremy Burns 278922 PatrickBeebe 278974 Paul N 278983

D Rief 278006 Quxxy 278069

Erlang Mike McNally 278434 278440 MichaelWH 278877 John Stracke 279008

F# darklajid 277890 277941 278137 Patrick Simpson 278127 ajp 278357 279029 cmugford 278486

FORTRAN rst 277978 java.lang.Chris; 278266

Groovy Matt 277949

Haskell freako 277838 Dave Ingram 277839 Sebastian Paaske Tørholm 277870 HypocriteWorld 277878 Maxim 277889 Noah Easterly 278130 semanticprecision 278170 Andrew Nurse 278198 Jonas Kramer 278220 ikorb 278299 valderman 278405 278406 Twey 278439 Joost 278567 jefu 278838 dub 278874 iggy 278935 vog 279045 MichaelWH 279047

Java Cookie 277785 Jay 277786 Mat Rantell 277802 Will 277831 Drew 277844 Arjan 277879 Philipp 277903 277919 Kook 277963 277968 imhe 278105 278138 Jannik Jochem 278115 Thuktun 278124 idle 278128 klagdon 278131 278242 amischiefr 278152 Greg R 278212 278231 Davi Cavalcanti 278228 DeepThought 278230 bb 278235 cincinnatvs 278237 Fred Dagg 278408 subanark 278537 Rorick 278749 Queex 278761 Coyne 278892

Javascript Zishan 277882 Jason Knight 277898 Mestafais 278005 Markus Persson 278039 jjs105 278136 jonnyq 278208 Phroggy 278221 astonerbum 278248 278264 278343 Scott 278294 Beat by the system 278319 Rob Hulswit 278329 Jeb Walter Strate 278345 Crindigo 278419 Chris 278484

LISP newlisp.org newLISP 277861 278283 MP 2778711 leppie Scheme 277881 dee Scheme 277900 Éibhear Emacs 277910 Dmitri Savichev Scheme 277992 277999 lyml Scheme 277996 Harleqin Common Lisp 278009 Alex Muscar Common Lisp 278090 278096 278160 278514 278516 Trey Jackson Emacs 278194 Bob Scheme 278206 samanddeanus Scheme 278271 asdfghj Scheme 278311 guille_ 278317 Ted Walther, newLISP fan newLISP 278344 278986 unit3 Common Lisp 278417 noSignal Scheme 278469 iamtim2 newLISP 278491 jvmbsd7 Scheme 278493 Chris Judge 278868 samanddeanus Scheme 278998

LOLCODE JaguarOne 277920 PopeHappyCat 278099

Lua Stefan 277854 Will 278010 Tiogshi 278368 Methuselah 278675

MSIL Osno 278153 278197 278729 278786 278801

Other hydrus Clojure 277792 db2 HP 48 277857 Dave Ingram vimscript 277862 pjt33 SML 277864 SR ColdFusion 277896 Will MUSH 277942 Samuel A. Falvo II Forth 277976 Sal Postscript 278093 acsi Spreadsheet 278150 Cindi Knox mIRC 278174 MUMPS MUMPS 278211 Trurl MUMPS 278246 278255 darkscout Matlab 278298 treyb Excel 278300 Roger RPGLE 278337 Tom Medley - www.tommedley.com ML 278350 ikegami circuit diagram 278370 dee COBOL 278403 yowzer ocaml 278428 J Mathematica 278467 StarLite Progress V9 278583 Ralf Smalltalk 278794 Rorick Rebol 278810 278873 Whatever Befunge-93 278988 Rusty Nail Verilog 279040

Pascal Azeroth 277837 malach Delphi 277860 baka0815 277868 277877 278020 278028 278065 DougB Delphi 278179 Trevor Dubinsky Delphi 278229 mol1111 Turbo Vision 278374

Perl Me 277807 277845 epv 277849 Steven de B 277884 WarheadsSE 277944 278061 Anonymous 277977 tirerim 278119 John Evans 278141 Jim Halfpenny 278143 Igor V. 278199 Darren 278223 Warr regex 278260 278420 qoo3h 278353 Andrew Rodland 278358 H2 278388 Florent 278401 278404 Toby Gray 278538 278540 bugmonkey 278658 rjp 278714 Maurits 279046

PHP The Wolf 277787 277799 Erin 277797 Clark S 277858 277872 Ryan 277863 Daniel 277904 277909 FatherStorm 277932 aBase 278036 278214 John Evans 278141 HonoredMule 278158 278168 278184 IcePanther 278195 Tim 278196 Paul 278265 LeCoyote 278396 mjomble 278413 mneimeyer 278524 LatecomerX 278617 278673 bugmonkey 278658 Evo 278886 278934 AngeloR. 278960

Prolog Anonymous Coward 277938 Mike5 278204 A.T. 278641 278646 Corpsegrinder 279051

Python ath 277789 277806 278244 phihag 277811 277818 277869 Fenris 277823 Jeff Kemp 277852 277940 Tempura 277875 Stalin 277880 Jim 277901 Eutactic 277915 RECURSIVEMAN 277916 rob tracey 277917 krat 277918 drBeat 277925 ross 277931 halber_mensch 277936 277943 277955 277979 278129 Real russian peasant :) 277974 Remy 278004 Billy 278007 Josh Bohde 278017 278080 278092 278104 278166 278854 Wulf0r 278024 Jürgen 278086 koblas 278101 Rob W. 278111 Chad M 278132 Jörg 278163 martinp 278172 JJM 278193 Ronuk Raval 278209 lostlogic 278222 SoaperGEM 278305 ZzzZZZz 278318 Lee Crabtree 278355 sdeek 278359 opussf 278364 KukkerMan 278366 Edinburgh Mike 278375 mwchase 278395 Adrian 278402 Jukka 278412 tdh 278444 Mr.'; Drop Database -- 278459 agrif 278497 Python 278688 Lom 278732 the real wtf fool 278842 workmad3 278975 inky 278996 Scott 279009

Ruby arnemart 277825 277855 Mike Dotterer 277829 exo 277926 Nicholas Laux 277958 277971 Xthlc 277983 278026 derula 278050 Amadan 278071 Northpole 278072 jweir77 278079 Jürgen 278086 Dave Havlicek 278122 Jeremy Weathers 278216 Chewbie 278224 Jimmy Selgen 278367 Redredredredredred 278380 Pony Princess 278967

Scala Alex Ciarlillo 277937 Ian McLaird 278023 Matt 278249 Unlabeled Meat 278332 juancn 278962 Landei 279042

Shell mat BASH 277791 bluebearr Batch 278012 278243 Ken B Batch 278032 moltonel BASH 278262 278272 278282 Julian Calaby BASH 278485 The_Assimilator PowerShell 279028 andyesslinger Batch 279049

SQL SQLDork 277795 KnowOracle Oracle 277816 277822 277824 Chris Hunt Oracle 277836 csulli13 277888 MeesterTurner T-SQL 277959 wombat T-SQL 278186 shane blake T-SQL 278210 Dave Havlicek PL/pgSQL 278322 Bodestone 278341 DFHawthorne Oracle 278409 Paul N T-SQL 278425 278427 Hidayat Oracle 278526 SlyEcho 278535 Boneist Oracle 278555 EJCorcoran T-SQL 278795 dee MySQL 279007

Tcl/Tk Albrecht from Germany 278142 278145

Unspecified Z 277796 Matthew Verleger 277827 ruckc 277828 cwink 277899 277905 Bob 277907 avl 277929 Jonathan 277967 buzkie 277984 Alex Guzman 278084 SimonY 278120 David Young 278185 Humanoid Life-form 278238 aef123 278245 278247 Josue Chi 278303 Michael Clark (mjac.co.uk) 278360 Eric 278371 Wheaties 278426 astander 278544 col obvious 278598 Alex 278628

XSLT Dave van der Brugge 278133 wombat 278808

Addendum (2009-07-24 02:26): jnz 278473 should be in C/C++ category.

mol1111 · 2009-07-23 Reply Admin

Yorick:

Speccy basic, recursive:

  10 DEF FN m(a,b)=VAL ((("FN m(
"+STR$ a+"*2,INT ("+STR$ b+"/2))
+("+STR$ b+"-2*INT ("+STR$ b+"/2
))*"+STR$ a) AND b<>1)+(STR$ a A
ND b=1))

C Nonsense in BASIC, 20:1

jnz · 2009-07-23 Reply Admin

mol1111:
I created index of all entries.

Wow, that must have taken a lot of work.

mol1111:
C# ... jnz 278473

My entry should be in the C/C++ section.

2009-07-23 Reply Admin

This seems like a good opportunity to show the world why Haskell is interesting. I'll write several implementations.

We'll need some import statements:

import Control.Monad.State
import Test.QuickCheck

Unit tests

Where would we be without unit tests, eh? QuickCheck is a really cool library that automagically generates lots of test-cases for you.

Here's our generic test case. We write it as a function called prop_russian_multiplication with arguments mul, n1 and n2. mul is the multiply function we want to test. We leave it as a parameter because we will want to test several different implementations. When we run QuickCheck it evaluates prop_russian_multiplication with lots of random numbers for n1 and n2, checking that it is always True:

prop_russian_multiplication mul n1 n2 =
  n1 >= 0 ==> -- Only generate test cases with n1 >= 0
    n1 `mul` n2 == n1 * n2 -- The property to test
  -- This line doesn't do anything, but it gives QuickCheck
  -- some hints.
  where types = (n1 :: Integer, n2 :: Integer)

Syntax notes: Whitespace (indents and newlines) is significant. "--" marks comments. Backticks () are syntactic sugar that let us write a prefix function (<i>mul n1 n2</i>) as an infix (<i>n1mul` n2).

Iterative style

Haskell is a pure functional language, so it doesn't let you modify variables. If it did, we could write code like:

russian_multiply n1 n2 =
  total := 0
  while (n1 > 0)
    if (odd n1) total += n2
    n1 := n1 `div` 2
    n2 := n2 * 2
  return total

We can't do that, but we can cheat! We can write an auxiliary function called loop with arguments total, n1 and n2. loop can modify n1, n2 and total by calling itself with modified values, like this:

russian_multiply_iterative n1 n2 = loop n1 n2 0
  where
    -- First the special case where n1 == 0.
    loop 0  n2 total = total -- We're done here.  total is the answer
    -- Now the general case.
    loop n1 n2 total = loop (n1 `div` 2) -- new value for n1
                            (n2 * 2)     -- new value for n2
                            (if (odd n1) then total + n2 else total) 
                                         -- new value for total

Then (here's the cool part) the compiler will notice that this is equivalent to a loop that modifies local variables. After the compiler has worked its magic, we have code exactly the same as the pseudo-code I wrote earlier. loop really is a loop! (This is known as tail-call optimisation, and is a requirement in the Haskell 98 standard.)

List style

This most closely matches the way the Russian peasant would really do it. It is also, perhaps, the most Haskell-ish way.

To solve 18 x 23, we first generate the list [18, 9, 4, 2, 1] (called halves) and the infinite list [23, 46, 92, ...] (called doubles). (Haskell is lazy, so infinite lists are fine. Haskell constructs only as much of the list as is needed.) Haskell's powerful list-processing syntax and libraries can do the rest in a single line:

russian_multiply_lists n1 n2 =
  sum [d | (h, d) <- zip halves doubles, odd h]
    where
      halves = f n1
        where
          f 0 = []
          f n = n : f (n `div` 2)
      doubles = iterate (* 2) n2

Here's another cool thing. As I said earlier, Haskell constructs the lists on demand, but the elements of the list are consumed as soon as they are produced. A smart compiler will notice that the lists are just intermediaries between a producer and consumer, and cut out the middle man. Ultimately, we end up with object code that is exactly the same as for the iterative version!

Why does this matter? Well, the "natural" way to do it is the list way. That's how the Russian peasant does it. But the most efficient way to do it is the iterative way. Of course, any half-decent programmer knows this already, and writes his code the efficient way, but if he is a Haskell programmer, he doesn't need to. The compiler is smart enough to figure it out for him.

This technique for eliminating intermediate data structures is, known as deforestation. It is based on a deep, mathematical relationship between Data Structures (lists, in this case) and Algorithms (iteration) known as a hylomorphism.

Monadic style

I told a small lie earlier. Haskell does let you modify variables, but only in carefully controlled circumstances. You have to wrap it all in a thing called a Monad. There's more deep maths involved, and it's hard to get your head round, but here's a simple example using the State Monad.

This code is similar to the iterative code, except that instead of total we have state. The state only exists within stateful_loop. execState initialises the state of (stateful_loop n1 n2) to 0, runs it, and then returns the final state.

russian_multiply_monadic n1 n2 =
  execState (stateful_loop n1 n2) 0
    where
      stateful_loop n1 n2 =
        -- We're done here.
        --  () is a dummy value; it's the state we want
        if n1 == 0 then return ()
          else do
            -- if n1 is odd modify the state
            when (odd n1) $ modify (n2 +)
            -- repeat the loop with new n1 and n2
            -- but keeping the same state
            stateful_loop (n1 `div` 2)
                          (n2 * 2)

This code might be equivalent to the iterative code ... but I'm not sure. Monads can be tricky. But very powerful. Monads are a principled way to implement things like: non-determinism, really smart parsing libraries, I/O, and much more besides.

Running it

main = do
  quickCheck $ prop_russian_multiplication russian_multiply_iterative
  quickCheck $ prop_russian_multiplication russian_multiply_lists
  quickCheck $ prop_russian_multiplication russian_multiply_monadic
  putStrLn $ "18 x 23 = " ++ show (18 `russian_multiply_lists` 23)

Which should give the output:

OK, passed 100 tests.
OK, passed 100 tests.
OK, passed 100 tests.
18 x 23 = 414

2009-07-23 Reply Admin

import scala.annotation.tailrec
def rpmul(a : Int, b : Int) : Int = {
    if (a < 0) {
        if (b < 0) rpmul(-a,-b) else -rpmul(-a,b)
    }
    else if (b < 0) -rpmul(a,-b)
    else {
        val (x,y) = if (a > b) (b,a) else (a,b)
        @tailrec def f(a : Int, b : Int, result : Int) : Int =
            if (a == 0) result
            else f(a>>1, b<<1, result + (a & 1) * b)
        f(x, y, 0)
    }
}

Scala 2.8 trunk - remove @tailrec and import for 2.7.

2009-07-23 Reply Admin

didn't look too hard, but didn't see any awk solutions. how about:

awk 'NF==2{t=0;x=$1;y=$2;while(x>=1){if(x%2==1){t+=y}x=int(x/2);y=y*2}print t}'

just feed in 2 numbers per input line

2009-07-24 Reply Admin

It's not much, but here was my solution. Copy this into a .lua and watch the magic!

-- rpc.lua
-- the russian peasant calculator
-- http://thedailywtf.com/Articles/Programming-Praxis-Russian-Peasant-Multiplication.aspx

function iterate_calculation(num1, num2, racetrack)
	accumulator = 0
	racetrack = racetrack or {}
	table.insert(racetrack, {num1 = num1, num2 = num2})
	
	num1 = math.floor(num1 / 2)
	num2 = math.floor(num2 * 2)
	
	if num1 >= 1 then
		iterate_calculation(num1, num2, racetrack)
	else
		for key, value in ipairs(racetrack) do
			if (value.num1 % 2) == 0 then
				value.num2 = 0
			end
		end
		for key, value in ipairs(racetrack) do
			accumulator = accumulator + value.num2
		end
	end
	return accumulator
end

if not arg[1] then
	print("Usage: " .. arg[-1] .. " " .. arg[0] .. " num1 num2")
	os.exit()
end

print(arg[1] .. " x " .. arg[2] .. " = " .. iterate_calculation(arg[1], arg[2]))

DBA_In_OKC · 2009-07-24 Reply Admin

MSSQL 2005/2008. No loops, only CTE recursion.

CREATE TABLE #operands (leftval int, rightval int); INSERT #operands SELECT 18, 23;

WITH russians (leftval, rightval) AS ( SELECT leftval / 2, rightval * 2 FROM #operands UNION ALL SELECT leftval / 2, rightval * 2 FROM russians WHERE leftval > 0 )

SELECT SUM(rightval) FROM russians WHERE leftval % 2 = 1;

DROP TABLE #operands;

Addendum (2009-07-24 00:59): Sorry, should be ... WITH russians (leftval, rightval) AS ( SELECT leftval, rightval FROM #operands ...

in case the first value is odd...

2009-07-24 Reply Admin

As there were complaints about the maintainability of the solutions, I added some comments.

%% russian(?A,?B,?P)
%% Multiplies A and B the russian style and unifies the result with P.
%% All parameters may be variables.
russian(A,B,P) :-
    % validate that all args are variables or positive integers
    (var(A);integer(A),A>=0),
    (var(B);integer(B),B>=0),
    (var(P);integer(P),P>=0), !,
    do_crazy_table_stuff(A,B,P).

%% do_crazy_table_stuff(?A,?B,?P)
%% does the crazy table stuff
do_crazy_table_stuff(A,B,P) :-
    % If one of the factors is a variable, I prefer if it's the first one.
    nonvar(A), var(B), !, do_crazy_table_stuff(B,A,P).
do_crazy_table_stuff(A,B,P) :-
    % A is a value, B as well. Thus, there is exactly one result P.
    nonvar(A), !, row(A,B,P,0,P), !. % <-- Therefore, here is a cut.
do_crazy_table_stuff(A,B,P) :-
    % A is a variable, B is not -> many results
    nonvar(B), !, row(A,B,P,0,P).
do_crazy_table_stuff(A,B,P) :-
    % A is a variable, B as well -> even more results
    % make sure P is initialized somehow
    length(_,P), between(0,P,B), row(A,B,P,0,P).

%% row(?A,+B,?P,+N,?R).
%% A single row of the multiplication table
%% A: factor 1 in this row; B: factor 2 in this row
%% P: Result of the multiplication (only set if provided externally)
%% N: Number of current row, starting at 0
%% R: Result so far (sum of rows >= N where A is odd)
row(_,_,P,N,_) :-
    % if P is provided, end recursion if N is just too big
    nonvar(P), P < 1<<(N-1), !, fail.
row(0,_,_,_,0). % if A is 0, the result should be 0 as well
row(A,B,P,N,R) :-
    % before caring about this row, solve the next
    row(Ax,B<<1,P,N+1,Rx),
    % of course, this A should be twice as big
    halve(A,Ax,Rem),
    % add B to result if A is odd
    R is Rx+B*Rem.

%% halve(-X2,+X,-Rem)
%% Ensures that X is halve the size of X2,
%% the remainder is stored in Rem (1 if X2 is odd, 0 else)
halve(1,0,1) :- !. % X and X2 being zero is not allowed
halve(X2,X,Rem) :- (Rem=0;Rem=1), X2 is X*2+Rem.

Examples:

?- russian(18,23,Z).  % Z = 414;
?- russian(18,Y,414). % Y = 23;
?- russian(X,23,Z).   % X = 1, Z = 23; X = 2, Z = 46; ...
?- russian(X,Y,414).  % X = 1, Y = 414; X = 2, Y = 207; ...
?- russian(X,Y,Z).    % X = 0, Y = 0, Z = 0; X = 1, Y = 1, ...

mol1111 · 2009-07-24 Reply Admin

jnz:

mol1111:
C# ... jnz 278473
My entry should be in the C/C++ section.

Sorry for the mistake. I guess it isn't the last one but I had no energy to check the results :-)

2009-07-24 Reply Admin

45 X 76 is uneven, so you add 76 to start with

2009-07-24 Reply Admin

Ok here is one more Brainfuck version. This one has comments ;)

++++++>	                                            # A=6 (Input 1)
++++++++++++<                                       # B=12 (Input 2)
[                                                   # While (A <> 0) {
  >>>[-]>[-]>[-]>[-]<<<<<<                          #   D = 0; E = 0; F = 0; G = 0;| P = A
  [>>>+>+>+<<<<<-]                                  #   D = A; E = A; F = A; A = 0;
  >>>>>[-<<<<<+>>>>>]<                              #   A = F; F = 0;    
  [-[->+<[>>+<<-]]>>[<<+>>-]<<]                     #   F = E / 2; E = 0; G = 0;
  >[-<+>]<                                          #   E = F; F = 0;  
  [>++<-]>[<+>-]<                                   #   E = E * 2; F = 0;
  >>[-]<<<                                          #   G = 0;
  >[-<->]<                                          #   if (D != E)	  
  [                                                 #   {
    [-]<<                                           #     D = 0
    [>+>+<<-]                                       #     C = C (plus) B; D = B; B = 0;
    >>[-<<+>>]                                      #     B = D; D = 0;
  ]                                                 #   }
  <<[>>++<<-]>>[-<<+>>]>[-]                         #   B = B * 2; D = 0;
  <<<<[-[->>>+<<<[->>>>+<<<<]]>>>>[-<<<<+>>>>]<<<<] #   D = A / 2; A = 0; E = 0; 
  >>>[-<<<+>>>]<<<                                  #   A = D; D = 0;  
]                                                   # }
>>.                                                 # Output as Ascii (H = 66)

2009-07-24 Reply Admin

A major shortcoming of all the examples I've looked as the insistence on using base 10 operations - this smacks of a distinct lack of under-engineering and foresight on the part of the developers. My code can use any radix which can be represented by a single character per digit:

<?php // $digits=array('0','1','2','3','4','5','6','7','8','9'); // decimal $digits=array('0','1'); // binary // $digits=array('0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'); // hexadecimal // $digits=array('.','!','$','%','^','*','{','>'); // wtfimal $a=$argv[1]; $b=$argv[2]; $reverse_digits=array_flip($digits); $base=count($digits); $pairs=array(); $even=array(); for ($offset=0; $offset<count($digits); $offset++) { $even[]=$digits[$offset++]; } praxis_gen_pairs($a, $b); $out=praxis_reduce_pairs(); print "$a x $b = $out\n"; exit; function praxis_gen_pairs($a, $b) { global $pairs, $digits; $pairs[]=array($a, $b); $a=praxis_half($a); $b=praxis_double($b); if ($a!=$digits[0]) { praxis_gen_pairs($a, $b); } } function praxis_double($x) { global $digits, $reverse_digits, $base; $out=''; $carry=0; for ($i=strlen($x)-1; $i>=0; $i--) { $new_offset=$reverse_digits[$x[$i]]+$reverse_digits[$x[$i]]+$carry; $carry=0; if ($new_offset>=$base) { $carry=1; $new_offset=$new_offset % $base; } $out=$digits[$new_offset] . $out; } if ($carry) $out=$digits[$carry] . $out; return praxis_tidy($out); } function praxis_half($x) { global $digits, $reverse_digits, $base, $even; $out=''; $carry=0; for ($i=0; $i<strlen($x); $i++) { $offset=(integer)(($reverse_digits[$x[$i]] + $carry)/2); $carry=0; if (!in_array($reverse_digits[$x[$i]], $even)) { $carry=$base; } $out.=$digits[$offset]; } return praxis_tidy($out); } function praxis_reduce_pairs() { global $pairs, $even, $digits; $out=$digits[0]; foreach($pairs as $offset=>$val) { // is it even? $digit=substr($val[0],-1); if (in_array($digit, $even)) { unset($pairs[$offset]); } else { $out=praxis_add($pairs[$offset][1], $out); } } return $out; } function praxis_add($a, $b) { global $digits, $reverse_digits, $base; if (strlen($a)<strlen($b)) { $x=$a; $a=$b; $b=$x; } while (strlen($b)<strlen($a)) { $b=$digits[0] . $b; } $carry=0; $out=''; for ($x=strlen($a); $x>0; $x--) { $offset=$reverse_digits[$a[$x-1]] + $reverse_digits[$b[$x-1]] + $carry; if ($offset>=$base) { $carry=1; $offset-=$base; } else { $carry=0; } $out=$digits[$offset] . $out; } if ($carry) $out=$digits[$carry].$out; return praxis_tidy($out); } function praxis_tidy($a) { global $digits; while ((substr($a,0,1)==$digits[0]) && (strlen($a)>1)) { $a=substr($a,1); } return($a); } ?>

2009-07-24 Reply Admin

mol1111:
C Nonsense in BASIC, 20:1

Do you mean it didn't work when you tried it? I may have made a mistake when transcribing it from the emulator window, but I think I checked it thoroughly. If you type it in, please take care to use tokens for DEF FN, VAL, FN, STR$, INT, AND and <> instead of spelling them out.

2009-07-24 Reply Admin

A False implementation!

0 23 18 [$0>][$[$1>][2-]#1=[@@$@+@@\]?2/\2*\]#%%.

2009-07-24 Reply Admin

And the ugly simple False implementation...

18a:23b:0[a;$2/2*=~[b;+]?a;1>][a;2/a:b;2*b:]#.

2009-07-24 Reply Admin

Perl, entirely without arithmetic.

($_,$b)=map{'.'x$_}@ARGV;
/^(.+)\1(.?)$/,($_,$b,$c)=($1,$b.$b,$c.($2&&$b))while/../;
print length$b.$c;

2009-07-24 Reply Admin

Matthew Verleger:
int RussianSum( int A, int B ){ return A ? RussianSum(A>>2,B<<2) + (!!(A&1))*(B): 0; }

"RussianSum(A>>2,B<<2) + (!!(A&1))*(B): 0;" looks more like a swearing Russian @!#&^$

2009-07-24 Reply Admin

Finally the most aesthetic esoteric False version:

0 23 18 [$$2/2*\-[@@$@+\@]?$1>][2/\2*\]#%%.

mol1111 · 2009-07-24 Reply Admin

Yorick:
mol1111:
C Nonsense in BASIC, 20:1
Do you mean it didn't work when you tried it? I may have made a mistake when transcribing it from the emulator window, but I think I checked it thoroughly. If you type it in, please take care to use tokens for DEF FN, VAL, FN, STR$, INT, AND and <> instead of spelling them out.

Sorry, it was my mistake, I had not used tokens for keywords inside strings. Now it works perfectly! Great job! And I thought that deffn is useless...

Russian Peasant Multiplication

begin script

end script

Leave a comment on “Russian Peasant Multiplication”