• (cs)

This is my quick hack using VBScript.

I don't feel it fully implements the algorithm (no "maintaining two columns"), or is as efficient as it could be.... but, it's a start of what your code should NOT end up like...

Function Mult( a, b ) While a > 1 a = a \ 2 ' Surprise: "" is Int division! b = b * 2
If a Mod 2 = 1 Then Mult = Mult + b Wend End Function

• Tim (unregistered)
```int Multiply(int a, int b)
{
int c = 0;
do
{
if (a & 1)
c += b;
a >>= 1;
b <<= 1;
} while (a > 0);
return c;
}
```

Untested, might not work for negative numbers.

• Tim (unregistered)

Actually not sure why I did do..while instead of just while... Oh well.

Cheeky Java solution..

private int multiple(int a, int b) {

``````int rtn = 0;
while (a > 0) {

if (a % 2 != 0) {
rtn += b;
}

a = a / 2;
b = b * 2;
}

return rtn;
``````

}

• Jay (unregistered)

public static int multiply(int first, int second){ if(first == 1){ return second; }

``````int result = 0;

if(first%2 != 0){
result += second;
}
result += multiply(first/2, second * 2);
return result;
``````

}

• (cs)

And in PHP:

```<?php

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

?>```
• The Dopefish (unregistered)

A recursive C# solution:

``````    static int Multiply(int a, int b)
{
if (a < 2)
return (a == 1 ? b : 0);
if (a % 2 == 1)
return b + Multiply(a / 2, b * 2);
return Multiply(a / 2, b * 2);
}
``````
• ath (unregistered)

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
```
• (cs)

Waiting for a solution in brainfuck...

• mat (unregistered)

This is my implementation of the algorithm using standard *nix bash script (with the addition of awk):

#!/bin/bash

X="\$1" Y="\$2"

if [ \$X -lt 0 ] then SIGN=-1 X=\$(( X * -1 )) else SIGN=1 fi

LEFT="\$X" RIGHT="\$Y"

while [ "\$X" -ne 1 ] do X=\$(( X / 2 )) Y=\$(( Y * 2 )) LEFT="\$LEFT \$X" RIGHT="\$RIGHT \$Y" done

L=`echo \$LEFT | wc -w` RESULT=0 for I in `seq 1 \$L` do X=`echo \$LEFT | awk "{print \$"\$I"}"` Y=`echo \$RIGHT | awk "{print \$"\$I"}"` if [ \$(( X % 2 )) -ne 0 ] then RESULT=\$(( RESULT + Y )) fi done

RESULT=\$(( RESULT * SIGN ))

echo "\$1 x \$2 = \$RESULT"

• hydrus (unregistered)

Obligatory Clojure entry:

```(defn rmult
([x y] (rmult x y 0))
([x y p]
(if (= x 1)
(+ y p)
(recur (quot x 2) (* y 2) (if (odd? x) (+ p y) p)))))
```
• Dascandy (unregistered)

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
```

• (cs)

Wow! I had not time to submit a solution. Everyone was too busy Russian to provide an answer!

• SQLDork (unregistered)

And a SQL implementation...

create function wtf.RussianMultiply(@m1 bigint, @m2 bigint) returns bigint as begin declare @out bigint set @out =0 while @m1 > 1 select @m1 = @m1 / 2, @m2 = @m2 * 2, @out = @out + case when @m1 & 1 = 1 then @m2 else 0 end return(@out) end go

• Z (unregistered)

function ruM (left, right) { var route = '', remainder = 0; while (left>1) { if (left % 2 != 0) { remainder += right; left -= 1; //route += 'remainder: ' + remainder + '\n'; } left /= 2; right *= 2; //route += left + 'x' + right + '\n'; } return right + remainder; }

• Erin (unregistered)

A simpler PHP version:

<?php function in_mother_russia(\$x, \$y) { \$z = 0; while (\$x) { if (\$x % 2) \$z += \$y; \$x = floor(\$x / 2); \$y *= 2; } return \$z; } echo 'In mother Russia, 18 x 23 = '.in_mother_russia(18, 23);
• Larry H. (unregistered)
```unsigned russian(unsigned a, unsigned b)
{
return ((a & 1) ? b : 0) + ((a & ~1) ? russian(a>>1, b<<1) : 0);
}```

Not tested.

• (cs) in reply to The Wolf

Not sure why I used that array bullcrap, too used to string manipulation I guess. Here's a better version for PHP:

```<?php

function russian(\$x, \$y) {
\$result = 0;

while (\$x > 1) {
if (\$x % 2) \$result += \$y;

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

return \$y + \$result;
}

echo russian(41238, 193625);

?>```
• dv (unregistered)

using ABAP (only a bit esoteric:-))

```FORM multiply USING   a TYPE I
b TYPE I
CHANGING c TYPE I.
CLEAR c.
WHILE a GT 0.
IF ( a MOD 2 EQ 1 ).
ENDIF.
DIVIDE a BY 2.
MULTIPLY b BY 2.
ENDWHILE.
ENDFORM.
```
• Paula (unregistered)

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

• Mat Rantell (unregistered)

A short recursive Java version:

public static long multiply( long left, long right ) { return ( ( left % 2 ) == 0 ? 0 : right + ( left == 1 ? 0 : multiply( left / 2, right * 2 ) ); }

• Kees (unregistered)

Function Diederick ( Jan, Piet ) While Jan > 1 Jan = Jan \ 2 Piet = Piet * 2 If Jan Mod 2 = 1 Then Diederick = Diederick + Piet Wend End Function

• Bosshog (unregistered)
```	;  6502 Assembler (4-bit operands only)
;  \$0001 should contain operand 1 (not preserved)
;  \$0002 should contain operand 2 (not preserved)

LDA #0
LDX #0
loop:
CPX \$02
BEQ done
CLC
LSR \$02
BCC skip
CLC
skip:
ASL \$01
JMP loop

done:
STA \$00
```
• ath (unregistered)

Another Python version. This time it handles zero and negative numbers properly... Floats works as second arg but not as first. Seems like too much work to fix it though...

```def is_odd(n):
return (n % 2) != 0

def rmul(x, y):
if(x < 0):
sgn = -1
x = -x
else:
sgn = 1

s = 0
while(x >= 1):
if is_odd(x):
s += y
x /= 2
y *= 2
return sgn*s
```
• Me (unregistered)

Bah to all your bloaty solutions. Perlmongers do it in one line :P

sub m(){my(\$a,\$b)=@_;my \$t;while(\$a){\$t+=\$b if (\$a&1);\$a>>=1;\$b<<=1;}return \$t;}

• Anonymous (unregistered) in reply to Paula

Win!

• (cs)

In Soviet Russia, peasants multiply you.

• phihag (unregistered)

Various iterative solutions in python:

```# python3 only, one-liner!
def mul3(a,b):
return sum(b << i if (a>>i)&1 else 0 for i in range(a.bit_length()))

def bits(value):
while value > 0:
yield value & 1
value = value // 2

def mul1(a,b):
res = 0
for a in bits(a):
if a:
res += b
b *= 2

return res

def mul2(a,b):
return sum(b << i if abit else 0 for i,abit in enumerate(bits(a)))

try:
mul = mul3
except AttributeError:
mul = mul2
```
• (cs)

Ta for the teaser, well back to my reports :(

```        static void Main(string[] args)
{
Console.WriteLine(RM(18, 23, 0));
}

public static int RM(int val1, int val2, int rem)
{
int mod = val1 % 2;
int _rem = (mod * val2) + rem;
int _v1 = val1 / 2;
int _v2 = val2 * 2;
if (val1 != 1)
{
return RM(_v1, _v2, _rem);
}
return _v1 + _rem;
}
```

```        public static int RM(int val1, int val2, int rem)
{
if (val1 != 1)
{
return RM((val1 / 2), val2 * 2, ((val1 % 2) * val2) + rem);
}
return (val1 / 2) + ((val1 % 2) * val2) + rem;
}
```
• Stefan (unregistered)

simple c with a little optimization

```unsigned int mul(unsigned int x, unsigned int y)
{
unsigned int r = 0;
unsigned int t;
if (y > x)
{
t = y;
y = x;
x = t;
}
while(x)
{
if (x & 1)
r += y;
x >>= 1;
y <<= 1;
}
return r;
}
```
• Takis (unregistered)

VB.Net

```Private Function Russiply(ByVal a As Long, ByVal b As Long) As Long

Do
If (a And 1) = 1 Then Russiply += b
a = a >> 1
b = b << 1
Loop Until a <= 1

If (a And 1) = 1 Then Russiply += b

End Function
```
• Zombywuf (unregistered)
```template<int x, int y, int accum, int mutliple>
struct multiply_ {
static const int value = multiply_<x / 2, y * 2, accum, (x / 2) & 1>::value;
};

template<int x, int y, int accum>
struct multiply_<x, y, accum, 1> {
static const int value = multiply_<x / 2, y * 2, accum + y, (x / 2) & 1>::value;
};

template<int y, int accum>
struct multiply_<0, y, accum, 0> {
static const int value = accum;
};

template<int x, int y>
struct multiply : multiply_<x, y, 0, x & 1> {};
```
• KnowOracle (unregistered)

Oracle SQL version:

```14:55:42 SQL> set echo on
SQL> @russian_mult 18 23
SQL> select sum(b)
2  from (select floor(a / power(2, rn)) as a,
3               b * power(2, rn) as b
4        from (select &1 as a,
5                     &2 as b,
6                     rownum as rn
7              from dual
8              connect by level < log(2, 18)))
9  where mod(a, 2) <> 0
10  /
old   4:       from (select &1 as a,
new   4:       from (select 18 as a,
old   5:                    &2 as b,
new   5:                    23 as b,

SUM(B)
----------
414

1 row selected.
```
• Captain Obvious (unregistered)

I haven't done APL in a LONG time...

```     Z <- A RUSSIAN B
  Z <- 0
 TOP:
  Z <- Z + A * 0 = 2 | B
  A <- |_ A (divide) 2
  B <- B x 2
  -> (A>0) / TOP
```
• phihag (unregistered)

An addition to my solution (see above): The python3 version is not only one line, but only one statement! Is there any other language where you can implement it in one statement without recursion?

• freakpants (unregistered)

seems like you killed esolangs :D

Bah. Looks like we've bost the esolangs.org server.

esolangs.org:
Esolang has a problem

Sorry! This site is experiencing technical difficulties.

(Can't contact the database server: Can't connect to local MySQL server through socket '/tmp/mysql.sock' (61) (localhost))

Anyone know if ColdFusion was on there? ;o)

• KnowOracle (unregistered)

log(2, 18) should read log (1, &1)

• Fenris (unregistered)

Handle Negs

def mult(a,b): ... neg = (a < 0) ... if neg: ... a *= -1 ... res = 0 ... while a >= 1: ... if a % 2 != 0: ... res += b ... a /= 2 ... b *= 2 ... if neg: ... return res * -1 ... else: ... return res ...

• KnowOracle (unregistered)

Correct Oracle SQL

```select sum(b)
from (select floor(a / power(2, rn)) as a,
b * power(2, rn) as b
from (select &1 as a,
&2 as b,
rownum as rn
from dual
connect by level < log(2, &1)))
where mod(a, 2) <> 0
/
```
• arnemart (unregistered)

Here's a recursive version in Ruby:

```class Integer
def russianmultiply num
return num if self == 1
return num + (self/2).russianmultiply(num*2) if self%2 == 1
(self/2).russianmultiply(num*2)
end
end

puts 18.russianmultiply(23)```

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 :)

• Matthew Verleger (unregistered)

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

• (cs)

```public static int russianMultiplication(int left, int right) {
int result = 0;

while(left > 1) {
result += left%2==1?right:0;

left /= 2;
right *= 2;
}
return result + right;
}
```
• Mike Dotterer (unregistered)

A ruby version:

def russian_peasant_multiply(numerator, denomenator) table = [[numerator, denomenator]] while table.last != 1 (n, d) = table.last table << [n / 2, d * 2] end table.reject { |r| r % 2 != 1 }. inject(0) { |sum, r| sum + r} end

• gosse (unregistered)

// todo: implement russian algorithm #define multiply(a, b) ((a)*(b))

• Will (unregistered)

Java

public int mult(int a, int b){ return (b*(a%2)) + (a==1?0:mult(a/2,b*2)); }

• darkwraith (unregistered)

My solutions with unit testing goodness:

#include <iostream>

using namespace std;

void assert_equals(unsigned long a, unsigned long b) { if (a != b) { cerr << a << " != " << b << endl; exit(1); } }

unsigned long russianMult(unsigned a, unsigned b) { unsigned long ret = 0; while (a > 0) { if (a % 2) ret += b; a >>= 1; b <<= 1; } return ret; }

int main() { assert_equals(414, russianMult(18, 23)); assert_equals(0, russianMult(0, 2)); assert_equals(0, russianMult(2, 0));

``````return 0;
``````

}

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

Whoops... Shoulda logged in first. :)

• Dan (unregistered)

Non-recursive C#:

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

while (i != 0) { accum += (i / Math.Abs(i)) * ((0 - (i & 1)) & j); i /= 2; j *= 2; }

return accum; }