only one line and no modification of a variable :p

2009-07-22 Reply Admin

After my earlier attempt with bc, I decided to try something more difficult: dc. Seems to work with negative numbers nicely too.

Using dc (GNU bc 1.06.95) 1.3.95:

Code (peasant.dc):
sbsa0[la2~rsalbd2*sb*+0la!=r]dsrxp

Examples:

$ dc -e  39 -e 83 peasant.dc
3237
$ dc -e _45 -e 76 peasant.dc
-3420

jonnyq · 2009-07-22 Reply Admin

Ok here's mine... in javascript, which has its limits

function multiply(x,y) {
 var z = 0;
 if(x < 0) y = 0-y;
 do {
  if(x&1 != 0) z += y; // add to z if x is odd
  x = (x>0?Math.floor:Math.ceil)(x/2); // halve x, drop remainder
  y += y; // double y
 } while(x != 0);
 return z;
}

Works for signed integers.

Haven't read the comments, so someone may have already done the same thing.

Ronuk Raval · 2009-07-22 Reply Admin

Don't know if this has been done yet (probably has).

Naive recursive Python implementation:

def mult(n1, n2):
        if n1 == 1:
                return n2
        if n1 % 2 == 1:
                return n2 + mult(n1 // 2, 2 * n2)
        else:
                return mult(n1 // 2, 2 * n2)

Faster, bit-oriented C89 version (handles negatives):

long mult(int n1, int n2)
{                        
        int sign = 1, place = 1;
        long result = 0;        

        if(n1 < 0) {
                sign *= -1;
                n1 = -n1;  
        }                  
        if(n2 < 0) {       
                sign *= -1;
                n2 = -n2;
        }

        while(n1 > 0) {
                if(n1 & 1) {
                        result += place * n2;
                }
                n1 >>= 1;
                place <<= 1;
        }

        return sign * result;
}

2009-07-22 Reply Admin

wombat:
Recursive Common Table Expression in MS SQL Server:

ya beat me to it, but here's my similar effort anyway :

;with russia(x, y) as ( select 18, 23 union all select x / 2, y * 2 from russia where x > 1 ) select sum(y) from russia where x % 2 <> 0

2009-07-22 Reply Admin

MUMPS:

P(I,S)
  S Q=I I I I S#2 S Q=0
  Q Q+P(I\2,S*2)

Features: Shortened keywords! Keywords reused for variable names! Recursion! Untested!

2009-07-22 Reply Admin

Recursive Java, taking advantage of its Unicode support.

public static int умножить(int Значение1, int Значение2) {
    if(Значение1 == 1)
        return Значение2;

    int крестьянин  = умножить(Значение1 / 2, Значение2 * 2);
    if(Значение1 % 2 == 1)
        крестьянин += Значение2;

    return крестьянин;
}

2009-07-22 Reply Admin

I cleaned-up the PHP function I posted earler. As before, it

handles non-integers,
handles negative numbers,

doesn't choke on zero.

function potemkin_multiply($two_numbers)
{
$power = 0;
$sign  = 1;
foreach ($two_numbers as $num) {
if ($num == 0) {
return 0;
} elseif ($num < 0) {
$sign *= -1;
}
if (($len = strlen(strrchr($num, '.'))) > $power) {
$power = $len - 1;
}
}
foreach ($two_numbers as & $num) {
$num = abs($num * pow(10, $power));
}
$total = 0;
while ($two_numbers[0] > 1) {
if ($two_numbers[0] % 2) {
$total += $two_numbers[1];
}
$two_numbers[0] = floor($two_numbers[0] / 2);
$two_numbers[1] *= 2;
}
return (($total + $two_numbers[1]) / pow(10, $power * 2)) * $sign;
}

Test code:

$nums = array(0, -1, 1, 18, -23, 154., -229.5, 49.0, 389.99,
67.99999, -592.8729, .678, 0.00678);
for ($i = 0; $i < 50; $i++) {
$pair = array($nums[array_rand($nums)], $nums[array_rand($nums)]);
$russian = potemkin_multiply($pair);
$orthodox = $pair[0] * $pair[1];
echo $pair[0] . ' * ' . $pair[1] . ' = ' . $russian . '';
if ((string) $russian != (string) $orthodox) {
echo ' (' . $orthodox . ')';
}
echo '
';
}

2009-07-22 Reply Admin

Ruby solution:

def rpm (first, second) # russian peasant multiplication
  total = 0
  while first > 0
    total += second if 0 != first % 2
    first = first / 2
    second = second * 2
  end
  total
end

xtremezone · 2009-07-22 Reply Admin

jonnyq:
y = 0-y;

There's the solution I was looking for. :P

2009-07-22 Reply Admin

Haskell:

multiply = ((sum . map snd . filter (odd . fst)) .) . tuples                                                                                                   
    where                                                                                                                                                      
        tuples 1 y = [(1, y)]                                                                                                                                  
        tuples x y = (x, y) : tuples (x `div` 2) (y * 2)

2009-07-22 Reply Admin

Here's mine, in HTML5, JavaScript and CSS!

lostlogic · 2009-07-22 Reply Admin

Pythonic solution:

def mult(a,b):
    def g(a,b):
        while a > 0:
            yield a,b
            a /= 2
            b *= 2
    return reduce(lambda x,y: x+y, [b for a,b in g(a,b) if a % 2 == 1])

Addendum (2009-07-22 14:02): Fixed for negatives and zeros.

def mult(a,b):
    a,b = (-a,-b) if a < 0 else (a,b)
    def g(a,b):
        while a > 0:
            yield a,b
            a /= 2
            b *= 2
    return sum([b for a,b in g(a,b) if a % 2 == 1])

Addendum (2009-07-22 14:10): Reduce memory usage at the cost of one line:

def mult(a,b):
    a,b = (-a,-b) if a < 0 else (a,b)
    def g(a,b):
        while a > 0:
            if a % 2 == 1:
                yield b
            a /= 2
            b *= 2
    return sum(g(a,b))

2009-07-22 Reply Admin

#!/usr/bin/perl
package russianPeasantMultiplier;
use strict; use warnings;

if (@ARGV < 2) { die "I take a list of numbers to multiply together - I need at least 2" }

my $register = shift @ARGV;
while (@ARGV) {
	$register = multiply( $register, shift @ARGV );
	printf "Result: %6d\n", $register;
}

sub multiply {
	die "multiply() takes two integers" unless (
		@_ == 2
		&& $_[0] == int($_[0])
		&& $_[1] == int($_[1])
	);
	
	my ($left, $right) = @_;
	my %set;
	
	my $expected_result = $left * $right;
	
	do {
		$set{$left} = $right;
		$left = int( $left / 2 ); #deliberately throw away remainder
		$right = $right * 2;
	} until $left == 1;
	$set{$left} = $right; # make sure the 1=>x pair is recorded
	
	my $result = 0;
	foreach (keys %set) {
		next if $_ % 2 == 0;  # skip any set with an even number on the "left"
		$result += $set{$_};
	}
	
	warn "Result mismatch: expected $expected_result, got $result.\n" unless $result == $expected_result;
	return $result;
}

2009-07-22 Reply Admin

In ruby :

def russian_peasant(x, y) return y if x/2 == 0 (x % 2 == 0) ? russian_peasant(x/2, y2) : y + russian_peasant(x/2, y2) end

Not properly tested, but I think it should work.

2009-07-22 Reply Admin

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.

2009-07-22 Reply Admin

Rather than settle with one 33-character entry, I decided to add a more robust solution. This does 2 things my previous solution doesn't: it handles negatives. And it doesn't use b*2 for doubling. Or a/2 for halving. I figured, since I'm writing a multiplication function anyway, why not use that instead?

    static int RecursiveMultiply(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == 1)
            return b;

        if (b == 1)
            return a;

        if (a == -1)
            return -b;

        if (b == -1)
            return -a;

        if (a == 2)
            return b + b;

        if (b == 2)
            return a + a;

        bool negA = a < 0;
        bool negB = b < 0;

        a = Math.Abs(a);
        b = Math.Abs(b);

        int halfA = 0;

        for (int x = 0; x < a; x++)
            if (RecursiveMultiply(x, 2) == a || RecursiveMultiply(x, 2) + 1 == a)
            {
                halfA = x;
                break;
            }

        int retVal = RecursiveMultiply(halfA, RecursiveMultiply(b, 2)) + RecursiveMultiply(a & 1, b);

        if (negA ^ negB)
            return RecursiveMultiply(retVal, -1);

        return retVal;
    }

2009-07-22 Reply Admin

public static int multiplicate(int num1, int num2) {
	System.out.print("call: " + num1 + " * " + num2);
	int result = num2;
	int oddLineValuesSum = 0;
	while (num1 > 1) {
		if (num1%2 == 1) {
			oddLineValuesSum += result;
		}
		num1 /= 2;
		result *= 2;
	}
	result += oddLineValuesSum;

	// In case the left number was negative
	if (num1 == -1) {
		result = -result;
	}

	System.out.println(" = " + result);
	return result;
}

2009-07-22 Reply Admin

Pascal, though specifically written in Delphi 7

Function rpm (num1, num2 : integer; var accumulator : integer) :integer; { Russion Peasant Multiplication implementation} begin // If the first number is not even add the second number // to the total if (num1 mod 2 <> 0) then accumulator := accumulator + num2;

// If the first number is not 1 recursively call self if num1 > 1 then rpm (num1 div 2, num2 * 2, accumulator);

//return result result := accumulator; end;

DeepThought · 2009-07-22 Reply Admin

Here is my submission. I've not looked at any of the other comments yet, so I apologize if this is similar to any earlier posts.

The realize that submitting an entire class is probably overkill, but I thought it would be helpful to see the recursive method (_multiply(int,int,int)) in context.

/**
 * Simple utility class containing the static
 * {@link #multiply(int,int) multiply} method used to determine the product
 * of the two integer operands, but it does this by using the
 * 
 * Russian Peasant algorithm. 

 * This code is a response to a "Programming Praxis" challenge put
 * forth by the thedailywtf.com website.
 * 
While not a specific requirement of the challenge, this class was
 * specifically coded to avoid directly making use of the language's
 * multiplication (*) or division (/) operators.
 * @author DeepThought (2009-07-22)
 */
public class RussianPeasantMultiply2
{
	/**
	 * Recursive method used to determine which of the second operands is to
	 * be summed into the final result. It returns the results of that
	 * summation when the first operand has been reduced to 1. 

	 * Each successive call to this method will result in the first operator
	 * being reduced by half while the second operator is doubled.
	 * The value of second operator will be added to the final results
	 * whenever the first operator is found to be an odd number.
	 * @param operand1 int - first operand
	 * @param operand2 int - second operand
	 * @param intermediateSum int - current result of summing up the second
	 * operators when the first operator is odd
	 */
	protected static int _multiply(int operand1, int operand2, int intermediateSum)
	{
		int results = 0;
		if ((operand1 & 1) == 1)
		{
			intermediateSum += operand2;
		}
		results = (operand1 == 1) ?
			intermediateSum :
			_multiply(operand1 >> 1, operand2 + operand2, intermediateSum);
		return(results);
	}
	/**
	 * This method is what is to be called to evaluate the product of the two operands.
	 * It will short-circuit the logic when either operand is 0 or 1 and will also negate
	 * the results of the recursive
	 * {@link #_multiply(int,int,int) _multiply(int,int,int)} method when the first
	 * operator is a negative number.
	 */
	public static int multiply(int operand1, int operand2)
	{
		int results;
		int absOp1 = Math.abs(operand1);
		int absOp2 = Math.abs(operand2);
		if (absOp1 == 0 || absOp2 == 0)
		{
			results = 0;
		}
		else if (absOp1 == 1)
		{
			results = absOp2;
		}
		else if (absOp2 == 1)
		{
			results = absOp1;
		}
		else
		{
			results = _multiply(absOp1, operand2, 0);
			if (operand1 < 0) results = (results ^ -1) + 1;
		}
		return(results);
	}
	/**
	 * Parsed a string argument supplied by the command-line and returns
	 * the integer equivalent.
It will display an error message and
	 * exit processing if a java.lang.NumberFormatException
	 * is thrown.
	 */
	public static int parseIntArguement(String strValue)
	{
		int intValue = 0;
		try
		{
			intValue = Integer.parseInt(strValue);
		}
		catch (NumberFormatException nfe)
		{
			System.err.println("Invalid number for operand \"" + strValue + "\"!");
			System.exit(1);
		}
		return(intValue);
	}
	/**
	 * Main application entry point
	 */
	public static void main(String args[])
	{
		try
		{
			if (args.length < 2)
			{
				System.err.println("Please supply two operands!");
				System.exit(1);
			}
			int operand1 = parseIntArguement(args[0]);
			int operand2 = parseIntArguement(args[1]);
			System.out.println("results = " + multiply(operand1,operand2));
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}
}

P.S. While previewing the comment I can see that the site appears to be inserting
tags and the beginning of each line of my code block even though it is embedding the code within a

tag. If that is also the case for the final post then not a result of me intentionally adding extra carriage returns or line-feeds in the original source. Sorry, but there doesn't appear to be anything I can do about it.

Greg R · 2009-07-22 Reply Admin

Fine, I've rewritten mine to handle negative numbers (even if they are restricted to the party elite who will simply subtract the peasants from the population until they have the proper answer) and to avoid explicitly using multiplication anywhere.

public static int умножить(int Значение1, int Значение2) {
    if(Значение1 == 1)
        return Значение2;

    if (Значение1 < 0) {
        Значение2 = 0 - Значение2;
        Значение1 = 0 - Значение1;
    }

    int крестьянин  = умножить(Значение1 / 2, Значение2 + Значение2);
    if(Значение1 % 2 == 1)
        крестьянин += Значение2;

    return крестьянин;
}

2009-07-22 Reply Admin

I think I've implemented a quantum physics one, but can't tell unless I open the box, and then it might kill the cat. Damn Schrödinger.

2009-07-22 Reply Admin

Here is the wtf of java program you would likely find when looking at others code :

int multiply(int a, int b){ int stuff = 0, z = -1; while ( a >> ++z > 0) stuff += (((a >> z) & 0x1) == 1 ? b * Math.pow(2, z) : 0 );

return stuff; }

2009-07-22 Reply Admin

C# int RussianMult(int a, int b) { int c = 0; if (a == 0 || b == 0) return c; else { int d = 0; while (a != 0) { if ((a % 2) != 0) d += (b * 2); a = a / 2; b = b * 2; } c = d/2; return c; }

}

cincinnatvs · 2009-07-22 Reply Admin

public int multiply (int operand1, int operand2) throws Exception {
	int product = 0;

	// While the first operand is still at least one, continue to execute the loop...
	while (operand1 >= 1) {
		// Show the current values...
		System.out.println ("" + operand1 + "\t" + operand2);

		// If the first operand is odd, add the value of the second operand to the total (our product).
		if (operand1 % 2 > 0) product += operand2;

		// In accordance with the "Russian Peasant Multiplication" method, divide the first operand by 2
		// and multiply the second operand by two.
		operand1 /= 2;
		operand2 *= 2;
	}

	// Return the product of this process.
	return product;
}

2009-07-22 Reply Admin

int russianMultiply(int a, int b) {
	// Create vars
	int left=a;
	int right=b;
	int rightSum=0;
	int errorOffset=0;
	
	if(left % 2 != 0 && right % 2 == 0) { // Prevent incorrect results
		int t = left;
		left = right;
		right = t;
	} else if(left % 2 != 0 && right % 2 != 0) {
		errorOffset = right;
		left++;
	}
	
	// Multiply
	for(;left > 1;) {
		left /= 2;
		right *= 2;
		if((left % 2) != 0) rightSum += right;
	}
	
	return rightSum - errorOffset;
}

I had to compensate for the algorithm's failure when a is odd.

2009-07-22 Reply Admin

My attempt at a compile time C++ version - outputs the answer in the form of an error message. Actually builds the whole table like the pen and paper working in the example animation too.

template <int N, int M, typename NEXT=void>
struct mult_list {
  enum {n=N};
  enum {m=M};
  typedef NEXT tail;
};

template <int N, int M>
struct mult_list<N,M,void> {
  enum {n=N};
  enum {m=M};
  typedef void tail;
};

template <int N, int M> 
struct russian {
  typedef mult_list<N,M, typename russian<N/2,M*2>::result> result;
};

template <int M> 
struct russian<1,M> {
  typedef mult_list<1,M> result;
};

template <typename LIST>
struct add_odd {
  enum {total=add_odd<typename LIST::tail>::total + (LIST::n % 2 ? LIST::m : 0) };
};

template <>
struct add_odd<void> {
  enum {total=0};
};

template <int N> 
struct output;

namespace {
  output<add_odd<russian<18,23>::result>::total> result;
}

2009-07-22 Reply Admin

brainfuck...not sure if this is going to show up properly with all the angle braces, but let's give it a try....

>+<+[>[>[-]+<-]>[<+>>>>>>>>>>>>>>[-]<<<<<<<<<<<<+[->,.----------[<+>>++++++[<------>-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<<<<<<<<<<[>>>>
>>>>>>++++++++++<<<<<<<<<<-]<[>>>>>>>>>>>+<<<<<<<<<<<-]]<]>>>>>>>>>>>>>[-]<<<<<<<<<<<<<+[->,.----------[<+>>++++++[<------>-]>>>>>>>>>>
>[<<<<<<<<<<<+>>>>>>>>>>>-]<<<<<<<<<<<[>>>>>>>>>>>++++++++++<<<<<<<<<<<-]<[>>>>>>>>>>>>+<<<<<<<<<<<<-]]<]>>>>>>>>[-]>>[-]<<[>>+<<-][-]>
>>>>[<<<<<+<<<<<<<<+>>>>>>>>>>>>>-]<<<<<<<<<<<<<[>>>>>>>>>>>>>+<<<<<<<<<<<<<-]>>>>>>>>>>>[-]<<<[>>>+<<<-][-]>>>>[<<<<+<<<<<<<<+>>>>>>>>
>>>>-]<<<<<<<<<<<<[>>>>>>>>>>>>+<<<<<<<<<<<<-]>>>>>>>>>[-]<[>+<-]<<<<<<<<<-]>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>-]<<
<<<<<<<<<<<<<<<<[>[-]+<-]>[<+>>>>>>>>>>[-]>[<+<<<<<<<<+>>>>>>>>>-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>[-]>>>>>>>>>>[<<<<<<<<<<+<<<<<<
<+>>>>>>>>>>>>>>>>>-]<<<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>[-]++>[-]+<[<<<<<<<<<<<<<+>>>>>>>>>>>>>-]->[<
<<<<<<<<<<<<<-<+>>>>>>>>>>>>>>>-]<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<-]>[>>>>>>>>>>>>>+<<<<<<<<<<<<<[-]]<->>>>>>>>>>>>>>[<<<
<<<<<<<<<<<->>>>>>>>>>>>>>-]<<<<<<<<<<<<<<[>>>>>>>>>>>>>>+<<<<<<<<<<<<<<-]>>>>>>>>[>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<->>>>>>>>>>[-]]<<<<<<
<<<-]<[>[-]+<-]>[<+>>>>>>>>>>[-]>>[<<+<<<<<<<<+>>>>>>>>>>-]<<<<<<<<<<[>>>>>>>>>>+<<<<<<<<<<-]>>>>>>>[-]>>>>[<<<<+<<<<<<<+>>>>>>>>>>>-]<
<<<<<<<<<<[>>>>>>>>>>>+<<<<<<<<<<<-]>>>>>>>[>+<<<<<<<<+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>>>>[-]<<[>>+<<-][-]>[<+<<<<<<<<+>>>>>>>
>>-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>[-]+>[<<<<<<<+>>>>>>>-]-<[<<<<<<-<+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>[>>>>>>>+<<<<<<<[-]]>>>
>>>>[>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<->>>>>>>>>>[-]]<<<<<<<<<-]<[>[-]+<-]>[<+>>>>>>>>>>[-]>[<+<<<<<<<<+>>>>>>>>>-]<<<<<<<<<[>>>>>>>>>+
<<<<<<<<<-]>>>>>>>[-]++>[<<<<<+>>>>>-]<<<<<[>>>>[<<<<<+<<+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>>[>-[<<+<+>>>-]<<<[>>>+<<<-]+>[<->[-]]<[>>
-[>>>>>>-<<<<<<[-]]+<<[-]]>>-]>>>>>>+<<<<<]>>>>>>[-]<[>+<-][-]>>>[<<<+<<<<<<<<+>>>>>>>>>>>-]<<<<<<<<<<<[>>>>>>>>>>>+<<<<<<<<<<<-]>>>>>>
>[-]++>[<<<<<<<+>>>>>>>-]<<<<<<<[>>>>>>[>+<<<<<<<<+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>-]>>>>>>>>>>[-]<<<[>>>+<<<-]>>>>>>>>+<<<<<<<<<<<<
<<<<<<->-]>>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>-]<<<<<<<<<<<<<<<<<<<<<[>[-]+<-]>[<+>>++++++++++++++[>++++++>
+++++++>++++++++>++++>++<<<<<-]>--.>+++.>+++.++.<+++++++.>-.>++.>++++.[-]<[-]<[-]<[-]<[-]<>>>>>>>>[-]>>[<<+<<<<<<<<+>>>>>>>>>>-]<<<<<<<
<<<[>>>>>>>>>>+<<<<<<<<<<-]>[-]>[-]>[-]>[-]>>>>[<<<<<+[>+<<<<+>>>-]<<<[>>>+<<<-]+>>>>----------[<<<<->>>>[-]]<<<<[>>+>[-]<<<-]>>[>>+<<<
<+>>-]<<[>>+<<-]+>>>>----------[<<<<->>>>[-]]<<<<[>+>[-]<<-]>>>>>>>>-]<<<<<<<[<++++++++[>++++++>++++++<<-]>.>.[-]<[-]]>[<<++++++++[>>++
++++<<-]>>.[-]]<<++++++++[>>>++++++<<<-]>>>.[-]<<<++++++++++.[-]<<<->>-]<<]@

2009-07-22 Reply Admin

Ok, once more with bit shifting and accounting for negative numbers.

    public static long multiply(long first, long second) {
        if(first < 0 && second < 0) {
            return multiply(Math.abs(first), Math.abs(second));
        } else if(first < 0 || second < 0) {
            return -multiply(Math.abs(first), Math.abs(second));
        } else if(first == 0 || second == 0) {
            return 0;
        } else if(first == 1) {
            return second;
        } else if(first % 2 == 1) {
            return second + multiply(first >> 1, second << 1);
        } else {
            return multiply(first >> 1, second << 1);
        }
    }
    
    public static void main(String[] args) {
        Random r = new Random();
        for(int i = 0 ; i < 1000000 ; i++) {
            long first = (long)r.nextInt();
            long second = (long)r.nextInt();
            long result = multiply(first,second);
            if((first * second) != result) {
                System.out.println("Failed for " + first + " * " + second + " = " + (first * second) + "\t" + result);
            }
        }
    }

2009-07-22 Reply Admin

Fine, since everyone seems soooo concerned that peasants be able to properly multiply negative numbers, I revised my Windows XP batch file answer. I also removed the multiplication assignment step, since I guess it is cheating.

Check out the _sign variable! Don't you wish your language could do that sort of nonsense?

@echo off
set _a=18
set _b=23
call :mult %_a% %_b% _result
echo %_a% x %_b% = %_result%
goto :EOF


:mult
::   Multiply two numbers
::   Parameters:
::    %1 - first number
::    %2 - second number
::    %3 - variable to return result in
  setlocal
  set _a=%1
  set _b=%2
  set _res=0
  set _sign=LEQ 1
  if "%_a:~0,1%"=="-" set _sign=GEQ -1
  :calc
    set _eventest=0
    for /L %%i in (0,2,8) do if %_a:~-1%==%%i set _eventest=1
    if %_eventest%==0 set /a _res+=_b
    if %_a% %_sign% goto endcalc
    set /a _a/=2
    set /a _b=_b+_b
    goto calc
  :endcalc
  if "%_a:~0,1%"=="-" (
    if "%_res:~0,1%"=="-" set _res=%_res:~1%
    if Not "%_res:~0,1%"=="-" set _res=-%_res%
  )
  endlocal & set %3=%_res%
goto :EOF

2009-07-22 Reply Admin

ath:

Same thing in python:

def is_odd(n):
    return (n % 2) != 0
def rmul(x, y):
s = 0
while(x != 1):
if is_odd(x):
s += y
x /= 2
y *= 2
return y + s

Any of these solutions checking for != 1 need to double check when the argument is 0.

This (and floating point numbers) are why it is always safer to use > or >= versus trying to "hit" an exact match.

As far as I can tell rmul(0,y) == infinite loop.

aef123 · 2009-07-22 Reply Admin

public static long PeasantMult(long operand1, long operand2) { long product = 0; while (operand1 != 1) { if (operand1 % 2 != 0) { product += operand2; } operand1 /= 2; operand2 *= 2; }
return (product + operand2); }

2009-07-22 Reply Admin

MUMPS:
P(I,S)

S Q=I I I I S#2 S Q=0

Q Q+P(I\2,S*2)

Features: Shortened keywords! Keywords reused for variable names! Recursion! Untested!

That doesn't work:

$ZE:<UNDEFINED>P+2^cTRAL1

This is tested and i added some extra MUMPS-flavour:

M(S,Q) N N,FN,F Q:$G(S)=""!($G(Q)="") "0" ; wtf?!
 S N=$S('(+S<0=(+Q<0)):"-",1:""),S=$FN(+S,"-",0),Q=$FN(+Q,"-",0)
 S F=$S(S#2:Q,1:"") Q:S=0!(Q=0) "0"
 S FN="" F  S S=S\2,Q=Q*2 S:S#2 FN=FN+Q Q:S=1
 Q N_(FN+F)

->

:W $$M^cTRAL1(18,23)
414
:W $$M^cTRAL1(19,23)
437
:W $$M^cTRAL1(-23,42)
-966
:W $$M^cTRAL1(-23,-12.5)
299

:

aef123 · 2009-07-22 Reply Admin

public static long PeasantMult(long operand1, long operand2) { long product = 0; while (operand1 > 1) { if (operand1 % 2 != 0) { product += operand2; } operand1 /= 2; operand2 *= 2; }
return operand1 * (product + operand2); }

astonerbum · 2009-07-22 Reply Admin

JavaScript. No Bitwise operations, but no use of multiplication either... Thats v2 :) Though still uses division so its still a problem, bitwise operations eliminate the need.

Handles positive and negative numbers.

function rpmult(x, y){
  var flip = false;
  if ( x === 0 || y === 0 ) {
    return 0;
  }
  if ( x === 1 ) {
    return y;
  }
  if ( x < 0 ) { 
    x = -x;
    flip = true;
  }
  if ( x % 2 === 0) {
    added = 0;
  }
  var added = ( x % 2 === 0 ? 0 : y );
  var recurse = rpmult(Math.floor(x / 2), y + y);
  return flip ? - (added + recurse) : added + recurse;
}

2009-07-22 Reply Admin

Here's another scala solution. It's not as neat as the recursive solution but it's based on lists, so more like the pen-and-paper version.

def mult(a: Int, b: Int) = { def m(a: Int, b: Int): List[(Int,Int)] = if (a==1) List((a,b)) else (a,b) :: m(a/2,b*2) m(a,b).filter(_.1%2 == 1).foldLeft(0)( + _._2) }

2009-07-22 Reply Admin

Osno:
All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail.

Granted, the goal was to define the multiply operator so it shouldn't be in the code.

HOWEVER, it is almost always a really bad idea to bitshift instead of using multiply/divide:

<< may lead to silent overflows instead of throwing an exception.

  int z1 = int.MaxValue * 2;   // Compile-time exception
  int z2 = int.MaxValue << 1;  // Silent overflow, return -2

For negative values, >> and / are NOT equivalent ((-1 >> 1) != (-1 / 2)).

  int y1 = -1 >> 1;   // -1
  int y2 = -1 / 2;    // 0

Numerical multiply/divide are hardly the bottleneck of any modern application. Let's keep the bitshift operators for what it was intended: shift bits. It was probably a smart optimization 30 years ago, but in 2009 it is a bad and pointless practice.

2009-07-22 Reply Admin

Eyrieowl:
brainfuck...

Nice, but two questions: - How am I supposed to format the input? I wasn't able to get anything sensible out of it. - Was this hand-written? (I always think generated Brainfuck code is lame.)

Trurl · 2009-07-22 Reply Admin

Granted, the goal was to define the multiply operator so it shouldn't be in the code.

I see...

Here's my altered submission:

MUMPS:

 ;-
M(S,Q) N N,FN,F Q:$G(S)=""!($G(Q)="") "0" ; wtf?!
 S N=$S('(+S<0=(+Q<0)):"-",1:""),S=$FN(+S,"-",0),Q=$FN(+Q,"-",0)
 S F=$S(S#2:Q,1:"") Q:S=0!(Q=0) "0"
 S FN="" F  S S=S\2,Q=Q+Q S:S#2 FN=FN+Q Q:S=1
 Q N_(FN+F)
 ;-

Trurl

2009-07-22 Reply Admin

method1:
Paula:
public class Paula extends WTF { public static string Paulabean = "brillant!"; }

Best solution by far

especially since she misspelled 'brilliant' ;)

tirerim · 2009-07-22 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.

Nonsense. In Perl, $n*=2 has fewer characters than $n+=$n. :-P

2009-07-22 Reply Admin

I figured that, to keep things interesting, I'd try to implement this using only regular expressions, instead of any real "math." I didn't quite accomplish it, since writing regular expressions to perform addition seemed too tedious, so I threw in a lookup table to assist with the additon step (only accounting for 2 addition operators in code, and a fixed 200 of them at run-time).

Interestingly enough, the thing actually works pretty well, has no theoretical limits on integer size, and never has to do decimal/binary translation at any point (though, technically, operations are carried out internally in a sort of base-30 system). Works with positive and negative integers of arbitrary size. Faster run-time if the smaller operand is on the left. :-)

#!/usr/bin/perl -w $_ = join(' ', @ARGV); m#^\s*-?\d+\sx\s-?\d+\s*# or die('Input should be in "#### x ####" format.'); $sign = '+'; while(s#-##) { $sign =~ tr#+-#-+#; } s#\s##g; s#$#=0\n#; %sums = (); %out = (); %carry = (); for($a = 0; $a < 10; $a++) { $i = $a; $i =~ tr#0-9#a-j#; $k = $a; $k =~ tr#0-9#A-J#; for($b = 0; $b < 10; $b++) { $c = $a + $b; # FIXME: Math on processor! $d = $c + 1; # FIXME: Math on processor! $j = $b; $j =~ tr#0-9#a-j#; length($c) > 1 and $c =~ tr#0-9#A-J# or $c =~ tr#0-9#a-j#; $c =~ s#.(?=.)##; length($d) > 1 and $d =~ tr#0-9#A-J# or $d =~ tr#0-9#a-j#; $d =~ s#.(?=.)##; for($e = 0; $e < 10; $e++) { $f = $e; $f =~ tr#0-9#a-j#; $g = $e; $g =~ tr#0-9#A-J#; $sums{$a . $b . $e} = $c; $sums{$i . $b . $e} = $c; $sums{$a . $j . $e} = $c; $sums{$i . $j . $e} = $c; $sums{$a . $b . $f} = $c; $sums{$i . $b . $f} = $c; $sums{$a . $j . $f} = $c; $sums{$i . $j . $f} = $c; $sums{$a . $b . $g} = $d; $sums{$i . $b . $g} = $d; $sums{$a . $j . $g} = $d; $sums{$i . $j . $g} = $d; } } $out{$a} = $i; $carry{$a} = $k; } while(!m#^0+x#) { s#(?<!\d)(\d)#0$1#g; if(m#\d+[13579]x#) { s#(\d)(=\d*)(\d)#$out{$1}$2$sums{$1.$3.0}#; while(m#\d[a-j]=#) { s#=([^0])#=0$1#; s#(\d)([a-j]=\d*)(\d)(.)#$out{$1}$2$sums{$1.$3.$4}$4#; } while(m#=0*[0-9A-J]#) { s#=([A-J])#=0$1#; s#0(?=[a-j]$)#a#; s#1(?=[a-j]$)#b#; s#2(?=[a-j]$)#c#; s#3(?=[a-j]$)#d#; s#4(?=[a-j]$)#e#; s#5(?=[a-j]$)#f#; s#6(?=[a-j]$)#g#; s#7(?=[a-j]$)#h#; s#8(?=[a-j]$)#i#; s#9(?=[a-j]$)#j#; s#0(?=[A-J]$)#b#; s#1(?=[A-J]$)#c#; s#2(?=[A-J]$)#d#; s#3(?=[A-J]$)#e#; s#4(?=[A-J]$)#f#; s#5(?=[A-J]$)#g#; s#6(?=[A-J]$)#h#; s#7(?=[A-J]$)#i#; s#8(?=[A-J]$)#j#; s#9(?=[A-J]$)#A#; } tr#A-Ja-j#0-90-9#; } s#^0#a#; s#^1#A#; s#^2#b#; s#^3#B#; s#^4#c#; s#^5#C#; s#^6#d#; s#^7#h#; s#^8#i#; s#^9#j#; while(m#^[A-Ja-j]\d#) { s#(?<=[a-j])0#a#; s#(?<=[a-j])1#A#; s#(?<=[a-j])2#b#; s#(?<=[a-j])3#B#; s#(?<=[a-j])4#c#; s#(?<=[a-j])5#C#; s#(?<=[a-j])6#d#; s#(?<=[a-j])7#D#; s#(?<=[a-j])8#e#; s#(?<=[a-j])9#E#; s#(?<=[A-J])0#f#; s#(?<=[A-J])1#F#; s#(?<=[A-J])2#g#; s#(?<=[A-J])3#G#; s#(?<=[A-J])4#h#; s#(?<=[A-J])5#H#; s#(?<=[A-J])6#i#; s#(?<=[A-J])7#I#; s#(?<=[A-J])8#j#; s#(?<=[A-J])9#J#; } tr#A-Ja-j#0-90-9#; s#0=#a=#; s#1=#c=#; s#2=#e=#; s#3=#g=#; s#4=#i=#; s#5=#A=#; s#6=#C=#; s#7=#E=#; s#8=#G=#; s#9=#I=#; while(m#\d[A-Ja-j]=#) { s#0(?=[a-j])#a#; s#1(?=[a-j])#c#; s#2(?=[a-j])#e#; s#3(?=[a-j])#g#; s#4(?=[a-j])#i#; s#5(?=[a-j])#A#; s#6(?=[a-j])#C#; s#7(?=[a-j])#E#; s#8(?=[a-j])#G#; s#9(?=[a-j])#I#; s#0(?=[A-J])#b#; s#1(?=[A-J])#d#; s#2(?=[A-J])#f#; s#3(?=[A-J])#h#; s#4(?=[A-J])#j#; s#5(?=[A-J])#B#; s#6(?=[A-J])#D#; s#7(?=[A-J])#F#; s#8(?=[A-J])#H#; s#9(?=[A-J])#J#; } tr#A-Ja-j#0-90-9#; s#(?<!\d)0+(?=\d|0(?!\d))##g; } s#.*=##; s#^#$sign#; s#^+##; print;

2009-07-22 Reply Admin

Mine is similar. Too bad we were prevented from making one-liners by "The yield statement cannot be used inside an anonymous method or lambda expression!"

private int PeasantMultiply(int first, int second)
{
    return GetColumns(first, second).Where(foo => foo.First % 2 == 1).Sum(bar => bar.Second);
}

private IEnumerable<Pair<int>> GetColumns(int a, int b)
{
    while (a >= 1)
    {
        yield return new Pair<int>(a, b);
        a = a / 2;
        b = b * 2;
    }
}

moltonel · 2009-07-22 Reply Admin

#!/bin/sh

grep -q '^1*' <<< $1 && echo $(( $1 )) || $0 "$(( $(sed 's/*.//' <<< $1)/2 ))$(( $(sed 's/.*//;s/+.//' <<< $1)2 ))$(grep -oE '[13579]*[0-9]+' <<< $1| sed 's/.*/+/')$(grep -o '+.*' <<< $1)"

only one line and no modification of a variable :p

Addendum (2009-07-22 14:42): That's bash of course, not sh.

2009-07-22 Reply Admin

Nobody has submitted ARM code yet that I have seen. Does this win for smallest number of instructions?

 ; multiplicands in r0 and r1

  mov r2,#0
loop
  movs r0,r0,lsr #1
  addcs r2,r1
  mov r1,r1,asl #1
  bne loop

astonerbum · 2009-07-22 Reply Admin

finally its time i learned how to do bitwise operations in javascript :P

This time there is absolutely no division or multiplication used in the algorithm, or Math.floor :P

function rpmult(x, y){
  var flip = false;
  if (x === 0 || y === 0) {
    return 0;
  }
  if (x === 1) {
    return y;
  }
  if (x < 0) { 
    x = -x;
    flip = true;
  }
  var added = (((x & 0x1) === 0x1) ? 0 : y);
  var recurse = rpmult(x >>> 1, y + y);
  return flip ? - added + recurse : added + recurse;
}

2009-07-22 Reply Admin

Sorry, in advance.

interface IMultiplierStrategy {
	public function mul( $a, $b );
}
abstract class Arithmetic  {
	protected
		$a, $b;
	public function __construct( $a, $b ) 	{
		$this->a = $a;
		$this->b = $b;
	}
}
class Multiply extends Arithmetic {
	public function mul( IMultiplierStrategy $strategy ) 	{
		return $strategy->mul( $this->a, $this->b );
	}
}
class RussianMultiplierStrategy implements IMultiplierStrategy {
	protected
		$tally = 0;
	public function mul( $a, $b ) {
		if( $a > 1 && $a %2 != 0 ) {
			$this->tally += $b;
		}
		if( $a == 1 ) {
			return $this->tally + $b;
		}
		return $this->mul( intval( $a /2 ), $b *2 );
	}
}
$mul = new Multiply( 18, 23 );
echo $mul->mul( new RussianMultiplierStrategy );

To the PHB: it's extensible multiplication architecture.

java.lang.Chris; · 2009-07-22 Reply Admin

FORTRAN 77

       PROGRAM RUSSIAN_MULTIPLY
       IMPLICIT NONE

       INTEGER RM
       INTEGER N

       N = RM(34, 4)

       PRINT *, '34 * 4 = ', N

       STOP
       END

       INTEGER FUNCTION RM(X, Y)
       INTEGER X
       INTEGER Y

       INTEGER Z

       Z = 0

       DO WHILE (X .GT. 0)
           Z = Z + MOD(X, 2) * Y
           X = X / 2
           Y = Y * 2
       ENDDO

       RM = Z

       RETURN
       END

2009-07-22 Reply Admin

#define int инт #define return разврат #define if еслибы #define while покашто #define else иначе #define printf напечатать //к черту всех floats инт множение(инт пиво,инт квас) { инт чердылка=0; еслибы(пиво > квас ) //чтобы быстрее работала, пацаны {чердылка=квас;квас=пиво;пиво=чердылка;чердылка=0;}

покашто(пиво!=1) { еслибы((пиво & 0x1)==1) //ne делитса на два чердылка+= квас; пиво>>=1; еслибы(квас < 0) напечатать("Ну твою мать!"); }

разврат чердылка; }

инт негативноеMноение(инт пиво,инт квас) {разврат -1*множение(инт пиво,инт квас);}

2009-07-22 Reply Admin

http://thedailywtf.com/Comments/Programming-Praxis-Russian-Peasant-Multiplication.aspx?pg=5#278037

OmnipotentEntity · 2009-07-22 Reply Admin

My solution.

#include <stdio.h>

int main (int argc, char* argv[]) {
  if (argc == 3) {
    long a = atoi(argv[1]);
    long b = atoi(argv[2]);
    long sum = 0;
    if (b&1) {
      sum += a;
    }
    while (b > 1) {
      b = b >> 1;
      a = a << 1;
      if (b&1) {
        sum += a;
      }
    }
    printf("%ld\n", sum);
    return 0;
  } else {
    return 1;
  }
}

Russian Peasant Multiplication

only one line and no modification of a variable :p

Leave a comment on “Russian Peasant Multiplication”