• halber_mensch (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.

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

  • 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
  • darklajid (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)
    Comment held for moderation.
  • halber_mensch (cs) in reply to halber_mensch

    No, this fails if a is even. damn

  • WarheadsSE (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 } }

  • WarheadsSE (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 }

  • Archimidas (cs)

    Where's the Shakespeare version?

  • Nick Pope (unregistered) in reply to WarheadsSE
    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
  • 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 :/

  • WarheadsSE (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.

  • halber_mensch (cs)

    Better recursive python solution:

    def умножить(a,b):
        if (a==1): return b
        return b*(a%2)+умножить(a>>1,b<<1)
    
  • kastein (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)}"

  • MeesterTurner (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!
    
  • WarheadsSE (cs) in reply to Nick Pope
    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? ;)

  • Osno (unregistered) in reply to Stefan
    Comment held for moderation.
  • 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;
    
            return 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.

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

    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

  • Nicholas Laux (unregistered) in reply to WarheadsSE

    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.

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

  • Nick Pope (unregistered) in reply to WarheadsSE
    WarheadsSE:
    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)
    Comment held for moderation.
  • 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
    Comment held for moderation.
  • 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
    
  • halber_mensch (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)
    
  • groknroll (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

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

  • shub (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.

  • Rootbeer (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.

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #:

« Return to Article