Nice one for a golf challenge.

• Chris Hunt (unregistered)

Recursive approach using ORACLE PL/SQL:

```CREATE OR REPLACE FUNCTION russian_mult (pleft IN NUMBER,
pright IN NUMBER)
RETURN NUMBER IS
newleft NUMBER;
BEGIN
-- Sanity checking: pleft has to be an integer
IF pleft != TRUNC(pleft) THEN
RAISE VALUE_ERROR;
END IF;

newleft := TRUNC(pleft/2);

-- tests for 0 and negative numbers added for completeness
IF pleft < 0 THEN
RETURN - russian_mult(-pleft,pright);
ELSIF pleft = 0 THEN
RETURN 0;
-- the main bit starts here!
ELSIF pleft = 1 THEN
RETURN pright;
ELSIF pleft/2 = newleft THEN  -- even number
RETURN russian_mult(newleft,pright*2);
ELSE -- odd number
RETURN russian_mult(newleft,pright*2) + pright;
END IF;
END;
/
SQL> SELECT russian_mult(18,23) FROM dual

RUSSIAN_MULT(18,23)
-------------------
414
```
• Azeroth (unregistered)

You and your prmature optimizations! I made my code follow the instructions (in Pascal implementation of SCAR)

```program PhilBewig;

type
TNumberLine = record
LeftColumn: Integer;
RightColumn: Integer;
CrossedOut: Boolean;
end;

TNumberLineSheet = array of TNumberLine;

function MultiplyNumbers(a, b: Integer): Integer;
var
Sheet: TNumberLineSheet;
i: Integer;
begin
//They start by writing the two numbers to be multiplied at the head of two columns
i:= 0;
SetArrayLength(Sheet, i + 1);
Sheet[i].CrossedOut:= False;
Sheet[i].LeftColumn:= a;
Sheet[i].RightColumn:= b;

//Then they repeatedly .. until the number in the left column is one
while(Sheet[i].LeftColumn > 1)do
begin
//writing the two new numbers immediately below their predecessors
i:= i + 1;
SetArrayLength(Sheet, i + 1);
Sheet[i].CrossedOut:= False;
//divide the number in the left column by two (dropping any remainder)
Sheet[i].LeftColumn:= Sheet[i - 1].LeftColumn div 2;
//double the number in the right column
Sheet[i].RightColumn:= Sheet[i - 1].RightColumn * 2;
end;

//Then they cross out all rows where the number in the left column is even
for i:= 0 to GetArrayLength(Sheet) - 1 do
begin
if(Sheet[i].LeftColumn mod 2 = 0)then
Sheet[i].CrossedOut:= True;
end;

//and add the remaining numbers in the right column, which is the desired product
Result:= 0;
for i:= 0 to GetArrayLength(Sheet) - 1 do
begin
if(not Sheet[i].CrossedOut)then
Result:= Result + Sheet[i].RightColumn;
end;
end;

begin
Writeln(IntToStr(MultiplyNumbers(18, 23)));
end.
```
• freako (unregistered)

What, no Haskell? Oh you sorry bunch of infidels...

mlt :: Int -> Int -> Int mlt 1 y = y mlt x y = (if x `mod` 2 == 0 then 0 else y) + mlt (x `div` 2) (y * 2)

• Dave Ingram (unregistered)

```peasant :: Int -> Int -> Int
peasant x y = sum (map (\(_, z) -> z) (filter (\(x, _) -> mod x 2 == 1) (peasantnums x y)))
where peasantnums 1 b = [ (1, b) ]
peasantnums a b = (a, b) : peasantnums (div a 2) (b*2)```
• Bonce (unregistered)

A few people have missed a bug in their code when the first value equals 1.

• Russian Peasant (unregistered)

Bah. Looks like me hearing of this method for the first time. In Soviet Russia we just multiply it by electronic calculators. Or by abacus. Or by slide rule. Whatever appropriate.

• (cs)

Quick and dirty (just how I like it!) and hopefully stays true to the manual working process, not being naughty and skipping a few steps. When run in a suitable VBA host (e.g. Excel) will even show the working table.

```Public Function RussianMultiply(x As Long, y As Long) As Long
Dim vals() As Long
ReDim vals(1 To Round(Sqr(x), 0) + 1, 1 To 2) As Long
Dim i As Long, j As Long, c As Long, Msg As String
i = 1
Do Until x = 0
vals(i, 1) = x
vals(i, 2) = y
i = i + 1
x = x \ 2
y = y * 2
Loop
For j = 1 To i - 1
If vals(j, 1) / 2 = vals(j, 1) \ 2 Then
Msg = " X"
Else
c = c + vals(j, 2)
Msg = vals(j, 2)
End If
Debug.Print vals(j, 1) & vbTab & vals(j, 2) & vbTab & Msg
Next
Debug.Print vbCrLf & "=" & vbTab & c
RussianMultiply = c
End Function```

Sample output:

```>RussianMultiply 18,23
18  23   X
9   46  46
4   92   X
2   184  X
1   368 368

=   414```

Addendum (2009-07-22 09:26): Oops, posted the +ve numbers only version. Replace Sqr(x) with Sqr(Abs(x))), add a new long s, where s = Sgn(x) * Sgn(y), and amend the output as required

• Damien (unregistered)

C# (I normally do VB, but wanted simple iterator support):

``````	static void Main(string[] args)
{
Int32 total = 0;
foreach (NumPair p in GetColumns(Int32.Parse(args), Int32.Parse(args)))
{
if (p.First % 2 == 1)
{
total = total + p.Second;
}
}
Console.WriteLine(total);
}

private struct NumPair
{
public Int32 First;
public Int32 Second;
}

private static IEnumerable<NumPair> GetColumns(Int32 Num1, Int32 Num2)
{
NumPair current = new NumPair();
current.First = Num1;
current.Second = Num2;
while (current.First > 0)
{
yield return current;
current.Second = current.Second * 2;
current.First = Convert.ToInt32(Math.Floor(current.First / 2.0));
}
yield break;
}
``````
• Drew (unregistered)

Java. Untested and recursive.

public void int multiply(int x, int y) { if(x == 1) { return y; } else if(x%2 == 1) {
return y + multiply(x/2, y2); } else { return multiply(x/2, y2); } }

• Me (unregistered)

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;}

• Dave Ingram (unregistered) in reply to freako

You got there a couple of minutes before me... and more concisely. In my defence, it has been about 5 years since I last wrote any Haskell... but I share your sentiment ;)

• Anon (unregistered)

TRWTF is the animated gif

• lemon (unregistered)

int russianPeasantMultiply(int a, int b) { // Russian peasant just optimized his code return a * b; }

• epv (unregistered)

Perl solution. Obeys strict pragma and has error checking.

```use strict;

main:
{
my \$arg1 = shift;
my \$arg2 = shift;

my \$russian = russianMultiply(\$arg1, \$arg2);
my \$real    = \$arg1 * \$arg2;

print "Russian Method: \$russian\nNormal Method: \$real\n";
\$russian==\$real?print "Success, same result\n":print "Failure, different results\n";
}

sub russianMultiply
{
use integer;

my \$leftArg;
my \$rightArg;
my \$product;

(\$leftArg, \$rightArg) = @_;

for(;
\$leftArg >= 1;
\$leftArg /= 2 and \$rightArg *= 2)
{
if(\$leftArg%2)
{
\$product += \$rightArg;
}
}

return \$product;
}
```
• KimmoS (unregistered)

## simple non-WTF C++ template version:

template <typename T> T russian_multiply(T paula, T bean) { T brillant = 0; for(;;) { if( paula & 1 ) brillant += bean; paula /= 2; if( paula == 0 ) return brillant; bean *= 2; } }

#include <iostream>

int main() { long a, b; std::cin >> a >> b; std::cout << a << "*" << b << "=" << russian_multiply(a,b) << std::endl; }

• KnoNoth (unregistered)

//Not really important part :) #define and ,int #define lets int #define be = #define is = #define jack_is_alive (jack>1){ #define jack_is_not_even (jack%2) #define plus + #define divided / #define multiplied * #define begin_action { #define end_action }

//The code itself lets multiple(lets jack and john) begin_action lets bill be 0; while jack_is_alive if jack_is_not_even bill is bill plus john; jack is jack divided 2; john is john multiplied 2; end_action return bill plus john; end_action

//You can call function like that multiple(int num1, int num2). It's written in C of course

• Jeff Kemp (unregistered)

I've just learned Python so I just had to contribute... this version doesn't actually use the * or / operators, which I think defeats the purpose somewhat. Works with all integers, positive or negative.

```def rusky_mult (left, right):
"""multiply
In Russia, peasants multiply You!
"""
if left < 0 and right < 0:
left, right = -left, -right
# left must be positive
elif left < 0:
left, right = right, left
product = 0
while left >= 1:
if left & 1:
product = product + right
left = left >> 1
right = right << 1
return product```
• freako (unregistered) in reply to Dave Ingram
Dave Ingram:
You got there a couple of minutes before me... and more concisely. In my defence, it has been about 5 years since I last wrote any Haskell... but I share your sentiment ;)

Ah, but yours is truer to the spirit of the algorithm provided. Mind, I'm a mere dabbler in the high mysteries of Haskell.

• Stefan (unregistered)

Lua

```function russian(a, b)
local s = 0;
if a < 0 then s = s + 1; end
if b < 0 then s = s + 1; end
a, b = math.abs(a), math.abs(b);
if b > a then a, b = b, a; end
if s == 1 then b = -b; end
local r = 0;
while(a > 0) do
if (a % 2) > 0 then r = r + b; end
a, b = math.floor(a / 2), b * 2;
end
return r;
end
```
• arnemart (unregistered)

New and improved recursive ruby version:

```class Fixnum
def * num
self == 1 ? num : (self/2) * (num+num) + (self%2 == 1 ? num : 0)
end
end

puts 7 * 7
```

• Dan (unregistered) in reply to Dan

C# again, but without that stinky Math.Abs():

public int PeasantMul(int i, int j) { int accum = 0;

while (i != 0) { accum += ((i >> 31) | 1) * ((0 - (i & 1)) & j); i /= 2; j *= 2; }

return accum; }

• (cs)

In UserRPL, as I've got my HP 48 handy, and I'm in the mood for the unconventional approach.

<< 0 3 ROLLD WHILE OVER 0 > REPEAT IF OVER 2 MOD THEN ROT OVER + 3 ROLLD END 2 * SWAP 2 / FLOOR SWAP END DROP2 >>

• Clark S (unregistered) in reply to The Wolf
The Wolf:
And in PHP:
```<?php
<pre>```function russian(\$x, \$y) {
\$left = array();
\$right = array();

while (\$x > 1) {
\$left[] = \$x;
\$right[] = \$y;

\$x = floor(\$x / 2);
\$y *= 2;
}

\$left[] = \$x;
\$right[] = \$y;
\$result = 0;

foreach (\$left as \$index => \$x) if (\$x % 2) {
\$result += \$right[\$index];
}

return \$result;
}

echo russian(41238, 193625);
``````

?>

I'll see that and raise you:
```<?php
function russkiply(\$a, \$b) {
\$product = 0;
while (\$a >= 1) {
if (\$a % 2)
\$product += \$b;
\$a = floor((float)\$a /= 2);
\$b *= 2;
}
return \$product;
}```

• arnemart (unregistered) in reply to KimmoS
KimmoS:
simple non-WTF C++ template version

Oxymoron!

• malach (unregistered)

In Delphi:

function RussianPeasantMultiply(a,b: Integer); begin result := 0; while a>0 do begin if (a AND 1) = 1 then result := result + b; a := a div 2; b := b * 2; end; end;

• newlisp.org (unregistered)

in newLISP:

```(define (rmul x y , s)
(until (= x 1)
(unless (zero? (% x 2))
(inc s y))
(setq x (>> x) y (<< y)))
(+ y s)
)
```
• Dave Ingram (unregistered)

Since I got beaten to the punch with the Haskell version, here's one for vimscript:

```:fun Peasant(n1, n2)
:  if a:n1 == 1
:    retu a:n2
:  elsei a:n1 % 2 == 1
:    retu a:n2 + Peasant(float2nr(a:n1/2), a:n2*2)
:  el
:    retu Peasant(float2nr(a:n1/2), a:n2*2)
:  en
:endf```

To use: save to ~/peasant.vim, :source ~/peasant.vim, then

`i<C-R>=Peasant(42,71)<CR>`
will insert the result of 42 × 71. Maybe if I have some time later, I'll make it print out the workings too ;)

• Ryan (unregistered)

Here's a PHP version that displays the process sequentially, like the example:

```<html>
<body>
<style type="text/css">
.result {
margin-right: 10px;
float: left;
}
h3 {
clear: both;
}
table {
text-align: right;
}
.final .strike {
text-decoration: line-through;
}
</style>
<?php

\$left = \$_GET['left'];
\$right = \$_GET['right'];
if (\$left && \$right && preg_match('/^[0-9]+\$/', \$left) && preg_match('/^[0-9]+\$/', \$right)) {

function mult(\$lefts, \$rights) {
echo '<div class="result">';
if (\$lefts[count(\$lefts) - 1] == 1) {
echo '';
} else {
echo '';
}

for (\$i = 0; \$i < count(\$lefts); \$i++) {
echo '<tr'.(!(\$lefts[\$i] % 2) ? ' class="strike"' : '').">";
}
echo '\$lefts[\$i]".(!\$i ? 'x' : '')."\$rights[\$i]';

\$i--;
if (\$lefts[\$i] == 1) return array_combine(\$lefts, \$rights);
\$lefts[] = floor(\$lefts[\$i] / 2);
\$rights[] = \$rights[\$i] * 2;
return mult(\$lefts, \$rights);
}

\$result = 0;
\$dispResult = '';
foreach (mult(array(\$left), array(\$right)) as \$l=>\$r) {
if (\$l % 2) {
\$result += \$r;
\$dispResult .= \$r.' + ';
}
}

echo 'Result is: '.substr(\$dispResult, 0, strlen(\$dispResult) - 2).'= '.number_format(\$result).'';
}

?>
```<form method="get" action="wtf.php">
<div>Left Number: <input type="text" name="left" value="<?php echo \$left; ?>"/></div>
<div>Right Number: <input type="text" name="right" value="<?php echo \$right; ?>"/></div>
<input type="submit" value="Go!"/>
</form>
```
</body>
</html>```

Working demo at http://sandbox.secularcoding.com/wtf.php?left=18&right=23

• (cs) in reply to Herman
Herman:
As this is the exact implementation of the multiply function on binary computing hardware, a simple
```int Mult(int a, int b)
{
return a * b;
}```

should do for most platforms :)

That's what I was going to say, so since you beat me to it here's a more long-winded implementation in SML:

fun mult_inner(x, y, accum) = if (x = 0) then accum else if (x mod 2 = 1) then mult_inner(x div 2, y * 2, accum + y) else mult_inner(x div 2, y * 2, accum); fun mult(x, y) = mult_inner(x, y, 0);

I think this is the first recursive implementation in the comments to be truly tail-recursive (and hence use a fixed amount of memory with a non-braindead compiler).

• Whatever (unregistered) in reply to Drew
Java. Untested and recursive.

Every good WTF starts with these words.

• Bob (unregistered)

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.

• Felix Ungman (unregistered)

C#, with yield return, of course!

``````static class Program
{
public static bool IsOdd(this int value) { return (value % 2) != 0; }

public static IEnumerable<KeyValuePair<int, int>> RussianPeasantSequence(int a, int b)
{
while (a > 0)
{
yield return new KeyValuePair<int, int>(a, b);
a /= 2;
b *= 2;
}
}

static void Main()
{
System.Diagnostics.Debug.WriteLine(
RussianPeasantSequence(18, 23)
.Where(x => x.Key.IsOdd())
.Select(x => x.Value)
.Sum());
}
}
``````
• baka0815 (unregistered)

Well, here is a version in Pascal.

```function RussianMultiply(Left, Right: Integer): Integer;
begin
if (Left = 1) then
begin
Result := Right;
Exit;
end;

Result := 0;
while Left <> 1 do
begin
Left := Left div 2;
Right := Right * 2;

if ((Left mod 2) <> 0) then Inc(Result, Right);
end;
end;```

Anyone noticed this only works if the left number is even?!

1823 works fine (414), bit 2318 would be 396.

• (cs)

code golf: Python 3, 1 statement, 1 line, 70 characters:

```m=lambda a,b:sum(b<
```

Oh hey, I did this in my first algorithms class lecture a while back.

```import Data.Bits (shiftL, shiftR)

x :: Integer -> Integer -> Integer
1 `x` b             = b
a `x` b | a > b     = b `x` a
| otherwise = (if a `mod` 2 == 0 then 0 else b) +
((a `shiftR` 1) `x` (b `shiftL` 1))```
• MP (unregistered)

LISP

((defun russianpeasant ("They start by writing the two numbers to be multiplied at the head of two columns.) (Then they repeatedly divide the number in the left column by (two ) (dropping any remainder) and ((double) the number in the right column), writing the (two new numbers) immediately below their predecessors, until the number in the left column is one.) ((Then they) (cross out all rows) where the number in the left column is even), and (((add the remaining numbers) in the right column), which is the desired product)). (For instance, the product eighteen times twenty-three is found like this.")))))

• Clark S (unregistered) in reply to Clark S
Clark S:
I'll see that and raise you:
```<?php
function russkiply(\$a, \$b) {
\$product = 0;
while (\$a >= 1) {
if (\$a % 2)
\$product += \$b;
\$a = floor((float)\$a /= 2);
\$b *= 2;
}
return \$product;
}```
Actually, I just realized that my function doesn't take into account negatives. In order to be functionally complete I must do this:
```<?php
function russkiply(\$a, \$b) {
\$product = 0;
if (\$a < 0) {
\$a = -\$a;
\$b = -\$b;
}
while (\$a >= 1) {
if (\$a % 2)
\$product += \$b;
\$a = floor((float)\$a /= 2);
\$b *= 2;
}
return \$product;
}```
The new check at the beginning will reverse the signs if the first part is less than 0; That way, if just \$a is negative, it switches \$b to the negative, and if both are negative, they both switch to positive.

CAPTCHA: appellatio -- sounds like a dirty fruit fetish

• whileloopsareugly (unregistered)

int mul(unsigned a, unsigned b) { for (int s=0; a; a>>=1, b<<=1) s+=a&0x1?b:0; return s; }

• Jeff Kemp (unregistered) in reply to Bob
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.

• Tempura (unregistered)

```In : def russia_peasants(x, y):
....:     x, y = float(x), float(y)
....:     if x <= 1:
....:         return 0
....:     elif (x%2) == 1:
....:         return (x*y) + russia_peasants(x/2, y*2)
....:     else:
....:         return russia_peasants(x/2, y*2)

In : russia_peasants(18, 23)
Out: 414.0
```
• TerraNova (unregistered)
```#define F(name, op)\
int name(int num) {\
int i, j = 0;\
for (i = 0; i < 32; ++i) {\
op;\
}\
return j;\
}

#define _BUFFER_SIZE 16
long b[_BUFFER_SIZE]; // long to avoid integer overflow

F(explode, j = 1; i[b] = num & j << i; i[b] >>= i)
F(implode, i[b] *= num << i)
F(deplode, j+= i[b])

#include <stdio.h>

void main(int argc, char *argv[]) {
if (argc != 3) return 1; // TODO: Display help text

int i;

printf("%d\n", (explode(atoi(argv)), implode(atoi(argv)), deplode(0)));
}
```

"Features":

• Uses the , operator
• buffer overflow (which passes valgrind!)
• The ever-popular TODO - commenting on the one piece of verification code
• Macros
• arrays-as-pointer - need i say more?
• Does not implement the actual algorithm, just something deceptively similar to what the requirements talk about
• Violates the language standard for no good reason
• baka0815 (unregistered)

Ok, screw that about the left number needing to be even. Just forgot to use that one, too.

Well, guess it goes with my name. ;)

```function RussianMultiply(Left, Right: Integer): Integer;
begin
if (Left = 1) then
begin
Result := Right;
Exit;
end;

Result := 0;

// Check if the first one is odd and add it
if ((Left mod 2) <> 0) then Inc(Result, Right);

while Left <> 1 do
begin

Left := Left div 2;
Right := Right * 2;
if ((Left mod 2) <> 0) then Inc(Result, Right);
end;
end;```
• (cs) in reply to Dave Ingram

Better Haskell version: (this one pretty much follows the algorithm given part by part).

```peasant :: Integer -> Integer -> Integer
peasant = curry (sum . map snd . filter (odd . fst) . unfoldr gen)
where gen (0, _) = Nothing
gen (x, y) = ((x, y), (x `div` 2, y * 2))
```

Sometimes the unfoldr function feels silly.

And to satisfy your craze for testing:

```import Test.QuickCheck
prop_peasant x y = (x > 0 && y > 0) ==> peasant x y == x * y
```
• Arjan (unregistered)

Recursive Java version. Also works with negative and zero.

```public class Russian {
public static long multiply(long a,long b){long r=multiply(a>0?a:-a,b>0?b:-b,0);return a<0^b<0?-r:r;}
private static long multiply(long a,long b,long r){if(a%2==1)r+=b; return a<=1?r:multiply(a>>1,b<<1,r);}
}
```
• Stalin (unregistered)
```def inSovietRussiaIntegerMultipliesYou(
a: "foul capitalist pig",
) -> "glorious empowerment of the proletariat for the motherland":
assert isinstance(a, int) and a > -1 and\
isinstance(b, int) and b > -1
al = [a]
bl = [b]
while 1 not in al:
al.append(al[-1]//2)
bl.append(bl[-1]*2)
return sum(b for a, b in zip(al, bl) if a%2)```

Only works under Python 3.x

• leppie (unregistered)

#!r6rs ;Scheme (for Phil :)

(define (russian* x y) (cond [(zero? x) 0] [else (let-values (((d m) (div-and-mod x 2))) (+ (if (zero? m) 0 y) (russian* d (bitwise-arithmetic-shift-left y 1))))]))

• Zishan (unregistered)
```function ruM (input) {
var left=0,right=0,remainder=0,sum=0,num;
input = input.replace(/\s+/g, '').replace(/x/g,'*');
if (input.indexOf('*')) num = input.split('*');
if (num) for (var i=1; i<num.length; i++) {
left = (i==1 ? parseInt(num[i-1], 10) : sum);
right = parseInt(num[i], 10);
while (left>1) {
if (left % 2 != 0) {
remainder += right;
left -= 1;
}
left /= 2;
right *= 2;
}
sum = right + remainder;
remainder = 0;
}
return sum;
}

String input:
ruM("18 x 23 x 23 x 23");
```
• douglas (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
``````
You're doing it wrong. The correct peasant algorithm here is:
```45   x  76	76
22	152	0
11	304	304
5	608	608
2	1216	0
1	2432	2432
======================
3420
```

Note the first line in particular.

• (cs)

Perl, with some nice recursion...

Code:
sub mul(\$\$) { my(\$a,\$b)[email protected]_; return \$a?((\$a&1?\$b:0)+mul(int(\$a/2),\$b*2)):0; }
Probably already mentioned before in some variations, but I just want to have such a cool WTF-sticker :-)