• Romeo (unregistered) in reply to Bob

You've just forget to sum the first line...

Bob:
Someone straighten me out here but I think the peasant don't know math for crap.

May be I'm doing it wrong but when I Multiply 45 x 76, I get 3420

# Peasants get:```45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432```

``````	3344
``````

# Flip the numbers and you get the right answer 76 45 38 90 0 19 180 180 9 360 360 4 720 0 2 1440 0 1 2880 2880

``````	3420
``````

Peasant math apparently only works if one of the number is even and in the first column.

This must be why they remain peasants.

• Bob (unregistered) in reply to Jeff Kemp
Jeff Kemp:
Bob:
Peasants get:[code] 45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432 ====================== 3344

You forgot to add the initial 76: 45 is odd.

I will blame this on poor specifications.

• djjeavons (unregistered)
```    Private Function Multiply(ByVal number As Integer, ByVal multiplyBy As Integer)

Dim lastNumber As Integer = number
Dim remainder As Integer = 0
Dim additionNumbers As Integer = 0
Dim lastMultiplyByValue As Integer = multiplyBy

System.Math.DivRem(System.Math.DivRem(lastNumber, 2, remainder), 2, remainder)
If remainder = 0 Then additionNumbers += lastMultiplyByValue

Do Until lastNumber = 1

lastMultiplyByValue *= 2
System.Math.DivRem(System.Math.DivRem(lastNumber, 2, remainder), 2, remainder)
lastNumber = System.Math.Floor(lastNumber / 2)

If Not remainder = 0 Then
End If

Loop

End Function
```
• csulli13 (unregistered)

SQL function using columns

CREATE FUNCTION RussianMultiply (@Num1 int, @Num2 int) RETURNS int AS BEGIN

CREATE TABLE #Columns(C1 int, C2 int)

WHILE @Num1 >= 1 BEGIN

``````INSERT INTO #Columns VALUES(@Num1, @Num2)

SET @Num1 = @Num1/2
SET @Num2 = @Num2 * 2
``````

END

DELETE FROM #Columns WHERE C1 % 2 = 0

RETURN SUM(C2) FROM #Columns

END

• Maxim (unregistered)

russian = curry \$ sum . map snd . filter (odd.fst) . takeWhile ((>0).fst) . iterate ((`div`2) *** (*2))

• (cs)

Nice idea. F# solution, without much thoughts put into it (in other words: Nicer solutions probably exist) and assuming #light:

```let russianMultiplication (x:int) (y:int) =
let rec russianMultiplicationRec x y l =
match x with
| 0 -> [(1, 0)]
| 1 -> ((1, y) :: l)
| _ -> russianMultiplicationRec (x/2) (y*2) ((x, y) :: l)

russianMultiplicationRec x y []
|> List.fold (fun acc (x, y) ->
if x % 2 = 1 then acc + y
else acc
) 0
```
• (cs) in reply to SR

I think we did one worse.

Database error A database query syntax error has occurred. This may indicate a bug in the software. The last attempted database query was:
``````(SQL query hidden)
``````

from within function "MediaWikiBagOStuff::_doquery". MySQL returned error "1194: Table 'mw_objectcache' is marked as crashed and should be repaired (localhost)".

• Osno (unregistered)

All the people looping on 1 instead of 0 fail. All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail.

• SR (unregistered)

ColdFusion:

<cffunction name="multiply" returntype="numeric"> <cfargument name="x" required="Yes" type="numeric"> <cfargument name="y" required="Yes" type="numeric"> <cfargument name="total" required="no" type="numeric">

``````&lt;cfif NOT IsDefined("arguments.total")&gt;
&lt;cfif arguments.x MOD 2 NEQ 0&gt;
&lt;cfset arguments.total = arguments.y&gt;
&lt;cfelse&gt;
&lt;cfset arguments.total = 0&gt;
&lt;/cfif&gt;
&lt;/cfif&gt;

&lt;cfset newX = Int(arguments.x / 2)&gt;
&lt;cfset newY = arguments.y * 2&gt;

&lt;cfif newX MOD 2 NEQ 0&gt;
&lt;cfset arguments.total = arguments.total + newY&gt;
&lt;/cfif&gt;
&lt;cfif arguments.x GT 1&gt;
&lt;cfset arguments.total = multiply(newX, newY, arguments.total)&gt;
&lt;/cfif&gt;
&lt;cfreturn arguments.total&gt;
``````

</cffunction>

Glad I use Java these days.

• GM (unregistered)

Another C# one: private int Multiply(int a, int b) { int result = 0, aBy2, bBy2;

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

aBy2 = a ;
bBy2 = b ;
do
{
aBy2 = aBy2 / 2;
bBy2 = bBy2 * 2;
if (aBy2 % 2 == 1)
{
result += bBy2;
}
} while (aBy2 != 1);

return result;
}
``````
• Damien (unregistered)

For those "handling negatives and zero" - the correct behaviour for these, given the literal description of the algorithm, is to loop forever, because the left hand column will never equal 1. (Not that my previous solution gets this right either)

• SR (unregistered)

2nd attempt:

<cffunction name="multiply" returntype="numeric"> <cfargument name="x" required="Yes" type="numeric"> <cfargument name="y" required="Yes" type="numeric"> <cfargument name="total" required="no" type="numeric">
``````<cfif NOT IsDefined("arguments.total")>
<cfif arguments.x MOD 2 NEQ 0>
<cfset arguments.total = arguments.y>
<cfelse>
<cfset arguments.total = 0>
</cfif>
</cfif>

<cfset newX = Int(arguments.x / 2)>
<cfset newY = arguments.y * 2>

<cfif newX MOD 2 NEQ 0>
<cfset arguments.total = arguments.total + newY>
</cfif>
<cfif arguments.x GT 1>
<cfset arguments.total = multiply(newX, newY, arguments.total)>
</cfif>
<cfreturn arguments.total>
``````
</cffunction>
• Soops (unregistered) in reply to Bob

Clue:

3420 - 3344 = 76

• Jason Knight (unregistered)

Javascript version:

``````function calculate() {
var num1 = 28;
var num2 = 13;
var tot = 0;
if ((num1 % 2) != 0) { tot = num2 }
while (num1 > 1) {
num1 = Math.floor(num1 / 2);
num2 *= 2;
if ((num1 % 2) != 0) { tot += num2 }
}
}
``````
• cwink (unregistered)

public static int Multiply( int op1, int op2 ) { return Mult( Math.Abs(op1), op2*op1/Math.Abs(op1) ); }

private static int Mult( int op1, int op2 ) { if( op1 == 1 ) return op2; else return (op1 & 1)*op2 + Mult( op1 >> 1, op2 << 1 ); }

• dee (unregistered)

Iterative Scheme:

```(define (peasant left right)
(define (peasant-i left right sum)
(if (= left 0)
(apply + sum)
(peasant-i (floor (/ left 2))
(+ right right)
(if (= (modulo left 2) 1)
(append sum (list right))
sum))))
(if (< left 0)
(peasant-i (- left) (- right) '())
(peasant-i left right '())))
```

Works with negative numbers and zeroes. I tried to follow the manual process as closely as possible :)

• Jim (unregistered) in reply to phihag
phihag:
code golf: Python 3, 1 statement, 1 line, 70 characters:
`m=lambda a,b:sum(b<`

Python 3, 64 characters

```m=lambda a,b:sum(b<
```
• Bob (unregistered) in reply to Bob
Bob:
Jeff Kemp:
Bob:
Peasants get:[code] 45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432 ====================== 3344

You forgot to add the initial 76: 45 is odd.

I will blame this on poor specifications.

I will add that many solutions here are making the same error.

• Philipp (unregistered)

public class SmallTest { public static void main(String [] args) { try { int m1 = Math.abs(Integer.parseInt(args[0])); int m2 = Math.abs(Integer.parseInt(args[1])); if (m1 > m2) {int temp = m1; m1 = m2; m2 = temp;} int result = 0; while (m1 >= 1) { if ((m1 & 1) > 0) result += m2; m1 >>= 1; m2 <<= 1; } System.err.println(args[0] + " * " + args[1] + " == " + result); } catch (Exception e) { System.err.println("Whoops: " + e.getMessage()); } } }

There you go. Even works for negative numbers ;) -- and it heavily optimizes... :)

• Daniel (unregistered)

Recursion is always the right answer!!

function peasantMath(\$a,\$b) { return ((\$a>>1)%2 == 0 ? 0 : \$b<<1) + (\$a>>1 == 1 ? 0 : peasantMath(\$a>>1, \$b<<1)); }

Also, TRWTF is that the link to esoteric languages is throwing database errors.

• cwink (unregistered)
``````  public static int Multiply( int op1, int op2 )
{
if( op1 == 0 || op2 == 0 )
return 0;
else
return Mult( Math.Abs(op1), op2*op1/Math.Abs(op1) );
}

private static int Mult( int op1, int op2 )
{
if( op1 == 1 )
return op2;
else
return (op1 & 1)*op2 + Mult( op1 >> 1, op2 << 1 );
``````

}

• Anonymous (unregistered)

Oh wow, this is unbelievable. No trolls, no grammar nazis, no flame-bait, no spammers - just everyone chipping in on an interesting coding challenge. I think this is probably the most civilised comments page I've ever seen on TDWTF. Well done everyone, you've all earnt a cookie.

• Bob (unregistered)
```(define (halve x) (quotient x 2))
(define (double x) (+ x x))
(define (mul x y)
(let iter ((x (abs x))
(y (if (negative? x)
(- y)
y))
(acc 0))
(cond
((zero? x) acc)
((even? x) (iter (halve x) (double y) acc))
(else (iter (- x 1) y (+ acc y))))))
```
• Jeff Kemp (unregistered) in reply to Bob
Bob:
Bob:
Jeff Kemp:
...

You forgot to add the initial 76: 45 is odd.

I will blame this on poor specifications.

I will add that many solutions here are making the same error.

and only those who said their solution is "untested" have half an excuse... :)

• Daniel (unregistered)

Adjusted to handle negatives, and to handle an initial odd left operand, as pointed out above. This is PHP by the way, though it's not doing anything special.

```function peasantMath(\$a,\$b) {
if ( \$a < 0 ) {
\$a *= -1;
\$b *= -1;
}
return ((\$a)%2 == 0 ? 0 : \$b) + (\$a == 1 ? 0 : peasantMath(\$a>>1, \$b<<1));
}```

• Éibhear (unregistered) in reply to newlisp.org

Using emacs lisp (and the dreaded recursion):

(defun russian-peasant-multiply (factor1 factor2) (cond ((eq factor1 1) factor2 ) ((eq (mod factor1 2) 0) (russian-peasant-multiply (/ factor1 2) (* factor2 2)) ) (t (+ factor2 (russian-peasant-multiply (/ factor1 2) (* factor2 2)))) ) )

• Stalker (unregistered)

Another assembly version, this time x64 using nasm

```SECTION	.text
GLOBAL	RussianMul
RussianMul:

[BITS 64]
xor	rax, rax
.start:
bt	rcx, 0
jnc	.even
.even:
shr	rcx, 1
shl	rdx, 1
test	rcx, rcx
jnz	.start

ret
```
• YES WE CAN! (unregistered)

doesn't use any * or /, supports negative numbers:

#define NEGATE(x) (~(x) + 1)

int russian_multiplication(int a, int b) { short think_positive = 1; int result=0;

``````if (a < 0) {
a=NEGATE(a);
think_positive=NEGATE(think_positive);
}

if (b < 0) {
b=NEGATE(b);
think_positive=NEGATE(think_positive);
}

// do it the russian way:
while (a > 0) {
if (a & 1) {
result+=b;
}
a >>= 1;
b <<= 1;
}

// think positive!
if (think_positive == -1)
result = NEGATE(result);
return result;
``````

}

• Stefan (unregistered) in reply to Osno
Osno:
All the people looping on 1 instead of 0 fail. All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail.

java.math.abs(int x)

public static int abs(int a)
``````Returns the absolute value of an int value. If the argument is not negative, the argument is returned. If the argument is negative, the negation of the argument is returned.

<b>Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative.</b>

Parameters:
a - the argument whose absolute value is to be determined
Returns:
the absolute value of the argument.
Integer.MIN_VALUE
``````

if you use shifting operators, russion(Integer.MIN_VALUE, ...) will always end in an infinity loop if your loop condition depends on a value != 0

• little3lue (unregistered)

Damn: someone beat me to a C++ metaprogramming solution. This is easier to read:

template <long a, long b> struct RusMult { enum { value = ((a&1) ? b : 0 ) + RusMult<(a>>1),(b<<1)>::value }; };

template <long b> struct RusMult<0,b> { enum { value = 0 }; };

// Usage: result = RusMult< a, b >::value;

• Eutactic (unregistered)

Python 3.x Why else would they support unicode? Translation is probably hilariously wrong.

#Русский крестьянин умножения модуль

def Умножение(X,Y): пар = []

``````def Населять(X,Y):
пар = []
while X > 0:
пар.append([X,Y])
X = X//2
Y = Y*2
return Суммавсех(Ликвидировать(пар))

def Ликвидировать(пар):
пар = [Элемент for Элемент in пар if Элемент[0] %2 != 0]
return пар

def Суммавсех(пар):
Сумма = 0
for Элемент in пар:
Сумма += Элемент[1]
return Сумма

пар = Населять(X, Y)
return пар
``````

print(Умножение(18, 23))

414

• RECURSIVEMAN (unregistered)

RECURSIVE MAN SAYS:

def _mult(a,b): if a == 1: return [(a,b)] return [(a,b)]+_mult(a/2,b*2) def mult(a,b): return sum(b for (a,b) in _mult(a,b) if a%2==1)

I was trying to stick exactly to the algorithm. The intermediate list of numbers that you'd write down on paper is first produced by _mult. The list comprehension then crosses out which ones are unnecessary, and adds the rest.

• rob tracey (unregistered)

python:

def rus(a,b): c = 0 while a > 0: a = a/2 b = b*2 if a % 2 != 0: c += b print 'total = ',c

• (cs)
```def russian_peasant(n1, n2):
remainder = 0
if n1 > n2: n1, n2 = n2, n1
while n1 != 1:
if n1 % 2:
remainder += n2
n1 >>= 1
n2 <<= 1

return n2 + remainder
```
• Philipp (unregistered)

Small improvement; now it really works with negative numbers...

public class SmallTest { public static void main(String [] args) { try { boolean n = args[0].trim().startsWith("-") ^ args[1].trim().startsWith("-"); int m1 = Math.abs(Integer.parseInt(args[0])); int m2 = Math.abs(Integer.parseInt(args[1])); if (m1 > m2) {int temp = m1; m1 = m2; m2 = temp;} int result = 0; while (m1 >= 1) { if ((m1 & 1) > 0) result += m2; m1 >>= 1; m2 <<= 1; } System.out.println(args[0] + " * " + args[1] + " == " + ((n && result != 0) ? "-" : "") + result); } catch (Exception e) { System.err.println("Whoops: " + e.getMessage()); } } }

• JaguarOne (unregistered)

Not very esoteric.... LOLCODE

HAI CAN HAS STDIO?

``````HOW DUZ I MULTIPLY_STALIN YR SOVIETA AN YR SOVIETB
I HAS A PROFIT
PROFIT R TROOF
I HAS A THROWFUD
THROWFUD R 0

IM IN YR USSR_LOOP WILE PROFIT AN SOVIETA BIGGR 0
IZ MOD OF SOVIETA AN 2 NOT 0?
YARLY
THROWFUD R SUM THROWFUD N SOVIETB

KTHX

SOVIETA R QUOSHUNT SOVIETA AN 2
SOVIETB R PRODUKT SOCIETB AN 2
IM OUTTA YR USSR_LOOP
IF U SAY SO
``````

KTHXBYE

• Andrew Brehm (unregistered)

"It is said that Russian peasants multiply using a most curious method"

Is that why there are so many of them?

• Fabio Lima (unregistered)

Minimalist C#

static int RussianMultiply(int a, int b) { int r=0; for (int i=a/2;i!=1;i--,a=a/2,b=b*2,r=r+(a%2)*b){} return r; }

• povman (unregistered)

Here's my very realistic solution, in C:

```/* Oh god, who wrote this? - geoff */
int RussianMultiply(int a, int b)
{
return a * b; /* TODO: Implement russian peasant multiplication */
}
```
• GWO (unregistered)

unsigned long long mult(unsigned long a, unsigned b) { unsigned long long acc = 0; while(a != 0) acc += (a%2)b,a/=2,b=2; return acc; }

• drBeat (unregistered) in reply to ath

This never terminates if x == 0.

My try:

```def russian_multiply(a, b):
product = 0
while a:
if a & 1:
product += b
a >>= 1
b <<= 1
return product
```
• exo (unregistered)

a very horribly ruby one-liner:

def mul(a, b) (t=[[a, b]]).inject(0){|acc,(a, b)|a<=0?acc:acc+(t<<[a>>1,b<<1])[-2][1]*(a%2==1?1:0)} end

• (cs) in reply to Paula
Paula:
public class Paula extends WTF { public static string Paulabean = "brillant!"; }

Best solution by far

• Benjamin Bridges (unregistered)

Don't see anyone doing this for the adding portion: sum += b * (a & 1);

Save an if statement.

• avl (unregistered)

uint32 rpMultiply(uint32 a, uint32 b) { uint32 res = 0;

if (b < a) { // change for shorten time a = a ^ b; b = a ^ b; a = a ^ b; }

do { if (a & 1) { res += b; a >>= 1; b <<= 1; } while (a); } return res; }

• (cs) in reply to Dascandy
Dascandy:
X86:
```; assumption: eax contains arg1, ebx contains arg2
mov edx, eax
next:
shr ebx, 1
cmovc ecx, edx
cmovnc ecx, 0
jz end
lea eax, [eax*2 + ecx]
jmp next
end:
ret
```

ARM:

```	mov r2, r0
next    test r1, 1
mov r1, #0, r1 shr 1
movz pc, lr
b next
```

awesome! more assembly required...

In IA64 assembly:

```.text
.align 32
.global russian_multiply
.proc russian_multiply
russian_multiply::
alloc	r14=ar.pfs,2,0,0,0
mov	r2=pr
movl	r8=0;;
startloop:
tbit.nz	p6=r32,1
cmp.e	p7=1,r32;;
(p7)	br.cond	endloop;;
shr	r32=r32, 1
shl	r33=r33, 1;;
br.cond	startloop;;
endloop:
mov	pr=r2
mov	ar.pfs=r14;;
br.ret.sptk	b0;;
.endp russian_multiply
```

Usable in C as: int russian_multiply(int num1, int num2);

Addendum (2009-07-22 10:26): cmp.eq not cmp.e. brainfart...

• ross (unregistered)

Python. Recursive, works with positive integers.

def mul(a,b): if a != 1: if a % 2 == 1: return b + mul(a >> 1, b << 1) else: return mul(a >> 1, b << 1) else: return b

• FatherStorm (unregistered)
```<?php
\$x=rand(1,65535);
\$y=rand(1,65535);
\$ans=\$x*\$y;
while(\$x>=1){
if(\$x % 2==1 ){
\$z+=\$y;
}
\$x=intval(\$x/2);
\$y=\$y*2;
}
echo"\$ans == \$z";;
?>
```
• Phil (unregistered) in reply to Bob
Bob:
Someone straighten me out here but I think the peasant don't know math for crap.

May be I'm doing it wrong but when I Multiply 45 x 76, I get 3420

# Peasants get:```45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432```

``````	3344
``````

# Flip the numbers and you get the right answer 76 45 38 90 0 19 180 180 9 360 360 4 720 0 2 1440 0 1 2880 2880

``````	3420
``````

Peasant math apparently only works if one of the number is even and in the first column.

This must be why they remain peasants.

You're doing it wrong. In the first example you forgot to add the 76 on the first row.

• threecheese (unregistered) in reply to Me
Me:
I was concerned my entry was too long and too legible. So I've shaved 11 bytes off it :)

sub m(){my(\$a,\$b)[email protected];my\$t;while(\$a){\$t+=\$b if\$a&1;\$a>>=1;\$b<<=1;}\$t;}

if you wanted illegible, you should assume no strict (drop the 'my \$t') and use indexes of @ instead of assigning \$a and \$b to it...