• (cs)

A recursive python solution

def умножить(a,b):
if (a==1): return b
_b = b
while(1):
a=a>>1
b=b<<1
if(a%2): break
return _b+умножить(a,b)

• Alex Ciarlillo (unregistered)

recursive scala soln.

def do_mult(left : Int, right : Int) : Int = {
if (left == 1) right
else if (left%2 == 0) do_mult(left/2, right*2)
else do_mult(left/2, right*2) + right
}

• Anonymous Coward (unregistered)

Prolog:

rusmul(0,_,0). rusmul(A,B,X) :- C is A//2, D is B*2, rusmul(C,D,E), X is E+(A mod 2)*B.

• SR (unregistered) in reply to Anonymous
Anonymous:
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.

• Jeff Kemp (unregistered)

IMHO any multiplication and division operators (and related ones like the "-" unary operator) should be disallowed. Only bitwise ops!

New & improved Python implementation, borrowed "YES WE CAN!"'s trick for negating using ~; handles all combinations of positive/negative/zero integers, and only uses the ~, >> and << operators (apart from comparison ops):

def rusky_mult(l,r):
if l<0 and r<0:
l,r=~l+1, ~r+1
elif l<0:
l,r=r,l
p=0
while l>=1:
if l&1: p+=r
l>>=1
r<<=1
return p
• (cs)

Another F# take. This time without recursion. I love "infinite" sequences..

let russianMultiplication x y =
Seq.initInfinite (fun i -> (x >>> i, y <<< i))
|> Seq.takeWhile (fun t -> fst t > 0)
|> Seq.filter (fun f -> fst f % 2 = 1)
|> Seq.sumBy (fun z -> snd z)

• Will (unregistered)

Not tested and not guaranteed correct (It's been years since I've used this stuff), but here's my attempt at a MUSH code solution.

@create peasant &cmd_russianMult peasant = \$russianMult *: @emit v(russianMult, %0, %1) &russianMult peasant = add(mult(mod(%0,2),%1), switch(%0,1,0,v(russianMult, div(%0,2), mult(%1,2))))

• (cs) in reply to halber_mensch

No, this fails if a is even. damn

• (cs) in reply to Me

Perl >> 1 line >> 55 chars ... beat that python :) sub r{(\$[0]?r(\$[0]>>1,\$[1]<<1):0)+(\$[0]&1)*\$_[1];}

• SR (unregistered)

function russianMultiplication(a, b) { if (frist) { alert('FRIST'); } else { // do nothing } }

• (cs) in reply to halber_mensch

love that russian translation function name!

• Romeo (unregistered) in reply to Jim

This way, you won't make much money on those "pay-per-line" jobs...

Jim:
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<
• Matt (unregistered)

Didn't see Groovy listed, so:

import static Math.floor

def multiply(ln, rn){ def results = [[left: ln, right: rn]] def product = 0 while ( results[-1]["left"] > 1){ results << [left: floor(results[-1]["left"]/2) as int, right: results[-1]["right"]*2] } results.findAll{it["left"] % 2 != 0}.each{product += it["right"]} product }

• (cs)

Where's the Shakespeare version?

Perl >> 1 line >> 55 chars ... beat that python :) sub r{(\$_[0]?r(\$_[0]>>1,\$_[1]<<1):0)+(\$_[0]&1)*\$_[1];}

Easy... I beat that with bc :) New target is sub 50 characters!

Code:
• ponky (unregistered)
#define HALF(X,Y) y*(1&Y)+a

int multiply(int x, int y)
{
int a = 0;
while (a=HALF(x,x),y<<=1,x>>=1);
return HALF(a,x);
}

maybe trying too hard :/

• (cs) in reply to Romeo
Romeo:
This way, you won't make much money on those "pay-per-line" jobs...
Jim:
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<

And they still have 9 characters to go to catch up with perl.

• (cs)

Better recursive python solution:

def умножить(a,b):
if (a==1): return b
return b*(a%2)+умножить(a>>1,b<<1)

• (cs)

Also, I'm disappointed... no MUMPS? no MS-DOS batch?

• Fabio Lima (unregistered) in reply to Fabio Lima

I stand corrected. Was missing the case where the first parameter was odd.

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

• Nicholas Laux (unregistered)

Ruby non-recursive:

print "First number: " q = gets.chomp.to_i print "Second number: " t = gets.chomp.to_i

def ahh_motherland!(a, z) p = (a > 0) == (z > 0) a, z = (a > 0 ? a : -a), (z > 0 ? z : -z) s = 0 while a > 0 do s += a % 2 == 0 ? z : 0 a /= 2 z *= 2 end return p ? s : -s end

puts "#{q} * #{t} = #{ahh_motherland!(q, t)}"

• (cs)

Some lunchtime T-SQL: DECLARE @N1 int DECLARE @N2 int DECLARE @tblMult TABLE(N1 int, N2 int)

SELECT @N1 = 18, @N2 = 23 -- The two numbers to multiply peasantly

WHILE @N1 >= 1
BEGIN
INSERT INTO @tblMult VALUES (@N1, @N2)
SELECT @N1 = @N1 * 0.5, @N2 = @N2 * 2

END

DELETE FROM @tblMult WHERE (N1 * 0.5) - (CAST((N1 / 2) AS INT)) = 0

SELECT SUM(N2) FROM @tblMult -- The Answer!

• (cs) in reply to Nick Pope
Nick Pope:
Perl >> 1 line >> 55 chars ... beat that python :) sub r{(\$_[0]?r(\$_[0]>>1,\$_[1]<<1):0)+(\$_[0]&1)*\$_[1];}

Easy... I beat that with bc :) New target is sub 50 characters!

Code:

Did you check the output? ;)

• Osno (unregistered) in reply to Stefan

@Stefan Agreed, but I don't think a russian counting peasants is counting negative peasants.

• GWO (unregistered) in reply to Romeo

K&R C: int m(a,b){c=0;while(a!=0)c+=a%2b,a/=2,b=2;return c}

54 characters - 59 if you include "K&R C"

• Kook (unregistered)

Takes care of zeroes and negatives --

public static int compute(int left, int right) {
int result = 0;
int multiplier = 1;

if (left < 0) {
multiplier = -1;
left *= -1;
}

if (right < 0) {
multiplier *= -1;
right *= -1;
}

while (left > 0) {
if (left % 2 == 1) {
result += right;
}

left /= 2;
right *= 2;
}

return result * multiplier;
}

• GWO (unregistered) in reply to GWO
GWO:
K&R C: int m(a,b){c=0;while(a!=0)c+=a%2*b,a/=2,b*=2;return c}

54 characters - 59 if you include "K&R C"

Oops : I meant

m(a,b){int c=0;while(a!=0)c+=a%2,a/=2,b*=2;return c;}

• GWO (unregistered) in reply to GWO
GWO:
GWO:
K&R C: int m(a,b){c=0;while(a!=0)c+=a%2*b,a/=2,b*=2;return c}

54 characters - 59 if you include "K&R C"

Oops : I meant

m(a,b){int c=0;while(a!=0)c+=a%2,a/=2,b*=2;return c;}

m(a,b){int c=0;while(a)c+=a%2*b,a/=2,b*=2;return c;}

Stupid stale clipboard

• Matt (unregistered)

int russianPeasantMultiplication(double a, double b) { cout << "You"; return 0; }

// In Soviet Russia, functions write You

• Jonathan (unregistered)

Recursive version that handles negatives:

public int PeasantMultiply(int n1, int n2)
{
bool negate = false;
if (n1 < 0){
negate = true;
n1 = -n1;
}
int tot = n1 > 1 ?  tot += PeasantMultiply(n1 / 2, n2 * 2) : 0;

if (n1 % 2 == 1) tot += n2;
if (negate) tot = -tot;

}

• Jeff Kemp (unregistered) in reply to Kook
Kook:
... if (right < 0) { multiplier *= -1; right *= -1; } ... [/code]

You can remove this bit and it'll still work.

• (cs)

Here's my specially optimised version, for all you C++ lovers:

unsigned do_it_like_a_russian(unsigned a, unsigned b)
{
// Make rows
std::stringstream rows;
rows << a << " x " << b << "\n";
while (a > 0)
{
rows << (a>>=1) << " " << (b<<=1) << "\n";
}

// Cross out even rows
std::string line;
std::stringstream crossed;
crossed.fill('-');
while (std::getline(rows, line))
{
std::stringstream(line) >> a;
crossed.width(line.size());
crossed << ((a & 1) ? line : "") << "\n";
}

// Total remaining rows
unsigned total = 0;
while (std::getline(crossed, line))
{
std::string::size_type p = line.find_last_of(' ');
if (p != std::string::npos)
{
std::stringstream(line.substr(p)) >> b;
total += b;
}
}
}

• Frits (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

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 forgot the first line contains an odd number, wich adds up to the total, there's your missing 76

Ruby: 49 characters, counting spaces.

def a(b,c) return b==1?c:c*(b%2)+a(b>>1,c<<1) end

• Osno (unregistered)

Btw, it's not in the spirit of the thread to criticize without chipping in. C#. Doesn't handle negative numbers, as per my previous logic:

private static long Multiply(long firstNum, long secondNum) { long acum = 0; while (firstNum > 0) { if ((firstNum & 1) == 1) acum += secondNum; firstNum = firstNum >> 1; secondNum = secondNum << 1; } return acum; }

captcha: ludus (programming is always a game)

Did you check the output? ;)

Aye, I did. And still seems to work fine... Are you having a problem with it?

• Real russian peasant :) (unregistered) in reply to Eutactic

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

I corrected yor translation a bit :)

# Модуль умножения, используемый русскими крестьянами

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

• jcs (unregistered)

• Samuel A. Falvo II (unregistered)

I didn't see a Forth version yet. Maybe I scanned too quickly.

: russian* ( n1 n2 -- n3 ) 0 -rot begin dup while dup 1 and if -rot over + swap rot then 2/ swap 2* swap repeat drop nip ;

• Anonymous (unregistered) in reply to Me
Me:
Bah to all your bloaty solutions. Perlmongers do it in one line :P

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

But surely that's just..

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

..with the returns stripped out..

• rst (unregistered)

4 pages and no FORTRAN?

integer function mult (a, b)
integer a, b
logical neg
mult = 0
neg = (a .lt. 0)
if (neg) a = (-1) * a
do while (a .gt. 0)
if (mod(a, 2) .eq. 1) then
mult = mult + b
endif
a = a / 2
b = b * 2
enddo
if (neg) mult = (-1) * mult
return
end

• (cs) in reply to halber_mensch
halber_mensch:
Better recursive python solution:
def умножить(a,b):
if (a==1): return b
return b*(a%2)+умножить(a>>1,b<<1)

And one that handles all integers, not just natural numbers:

def умножить(a,b):
if (-1<=a<=1): return a*b
return b*(a%2)+умножить(a>>1,b<<1)

• (cs)

Recursive C# solution.

private int PeasantMultiply( int n1, int n2) { if ( n1 == 1 ) return n2;

return ( n1 % 2 == 0 ? 0 : n2 ) + (n1 == 0 ? 0 : PeasantMultiply( n1 >> 1, n2 << 1 )); }

• Samuel A. Falvo II (unregistered) in reply to Samuel A. Falvo II

Bugger! There's a bug in the code I posted, and I don't have time to fix it right now. :( At any rate, the Russian algorithm is what Chuck Moore used to implement his "*+" operator in his MISC processors.

• Xthlc (unregistered) in reply to arnemart

Here's a slightly shorter and bitshiftier recursive ruby version, although I like that you modified the integer class. How very Ruby. :D

def russian(a, b) return 0 if a == 0 (a & 0x1) * b + russian(a>>1, b*2) end

• (cs)

static int russianmult(int a,int b){ int total = 0; while (a >= 1){ if (a% 2 != 0){total += b;} a = a /2; b = b *2; } return total; }

Any suggestions welcomed

• (cs)
#include <stdio.h>

int peasant_multiply(int x, int y)
{
int result;
for(result = 0; x != 0 && y != 0; x /= 2, y *= 2)
{
result += (x % 2) * y;
}
return result;
}

Addendum (2009-07-22 11:03): Depending on compiler behavior you could move

result += (x % 2) * y
into the update step and save a few lines, but that would be evil and wrong. :)

• Stephen (unregistered)

This is similar to how I multiply numbers in my head, except that I will divide by any factor, and when I run into too large of a prime, I either change to estimating or play the "multiply by 7 means multiply by 8 and subtract by one" game. I don't recall where I learned to do that...

• Xthlc (unregistered) in reply to halber_mensch

Curses! More-or-less beaten by this solution. For some reason I didn't think to shift b.

• (cs) in reply to Herman
Herman:
this is the exact implementation of the multiply function on binary computing hardware

Is this so? I had assumed that most CPUs with MULtiply opcodes used hardware lookup tables, in order to achieve a fast and constant O(1) execution time, but perhaps I am mistaken. It's certainly a less sensible approach with 32- or 64-bit operands than it would have been with 8- or 16-bit operands.