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

halber_mensch · 2009-07-22 Reply Admin

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)

2009-07-22 Reply Admin

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
  }

2009-07-22 Reply Admin

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.

2009-07-22 Reply Admin

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.

If you fancy a return to normal we could have a slanging match about earnt/earned ;o)

2009-07-22 Reply Admin

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

darklajid · 2009-07-22 Reply Admin

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)

2009-07-22 Reply Admin

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

halber_mensch · 2009-07-22 Reply Admin

No, this fails if a is even. damn

WarheadsSE · 2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

WarheadsSE · 2009-07-22 Reply Admin

love that russian translation function name!

2009-07-22 Reply Admin

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<

2009-07-22 Reply Admin

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 }

Archimidas · 2009-07-22 Reply Admin

Where's the Shakespeare version?

2009-07-22 Reply Admin

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

a=read();b=read();while(a){c+=b*(a%2);a/=2;b*=2};c

2009-07-22 Reply Admin

#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 :/

WarheadsSE · 2009-07-22 Reply Admin

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.

halber_mensch · 2009-07-22 Reply Admin

Better recursive python solution:

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

kastein · 2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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)}"

MeesterTurner · 2009-07-22 Reply Admin

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!

WarheadsSE · 2009-07-22 Reply Admin

Nick Pope:
WarheadsSE:
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:
a=read();b=read();while(a){c+=b*(a%2);a/=2;b*=2};c

Did you check the output? ;)

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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"

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

// In Soviet Russia, functions write You

2009-07-22 Reply Admin

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;

        return tot;
    }

2009-07-22 Reply Admin

Kook:
... if (right < 0) { multiplier *= -1; right *= -1; } ... [/code]

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

hh10k · 2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

Ruby: 49 characters, counting spaces.

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

Ball's in your court.

2009-07-22 Reply Admin

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)

2009-07-22 Reply Admin

WarheadsSE:
Did you check the output? ;)

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

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

You do know about this, don't you?

2009-07-22 Reply Admin

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 ;

2009-07-22 Reply Admin

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

But surely that's just..

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

..with the returns stripped out..

2009-07-22 Reply Admin

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

halber_mensch · 2009-07-22 Reply Admin

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)

groknroll · 2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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.

2009-07-22 Reply Admin

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

buzkie · 2009-07-22 Reply Admin

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

shub · 2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

Rootbeer · 2009-07-22 Reply Admin

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.

Russian Peasant Multiplication

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

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

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

Leave a comment on “Russian Peasant Multiplication”

Russian Peasant Multiplication

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

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

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

Leave a comment on “Russian Peasant Multiplication”

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