• OhComeOn (unregistered)

    VERY literal Javascript implementation:

    russian_peasant_mult = function(left, right) {
      var lines, line, position, result = 0;
      left = parseInt(left); right = parseInt(right);
      if (isNaN(left) || isNaN(right)) {
        return NaN;
      }
      lines = [left + 'x' + right];
      while (!((line = lines[lines.length-1]).match(/^1x/))) {
        position = line.match(/[02468]x/) ? lines.length - 1 : lines.length;
        lines[position] = (Math.floor(line.split('x').shift() / 2)) + 'x' + (line.split('x').pop() * 2);
      }
      for (i = 0; i < lines.length; i++) {
        result += parseInt(lines[i].split('x').pop());
      }
      return result;  
    }
    
  • Bob Archer (unregistered)

    I'm a latecomer. Still fun to do.

    Code handles negative values OK.

    2 VB.Net ways:

    Way 1 - Recursive:

    Protected Sub RussianPeasantMultiplication(ByVal n1 As Integer, ByVal n2 As Integer, ByVal n3 As Integer)
        If Math.Abs(n1) >= 1 Then
            Console.WriteLine(n1 & " x " & n2)
            n3 = n3 + IIf(n1 Mod 2, Math.Abs(n2), 0) * IIf(n1 < 0, -1, 1) * IIf(n2 < 0, -1, 1)
            RussianPeasantMultiplication(Math.Floor(Math.Abs(n1 / 2)) * IIf(n1 < 0, -1, 1), n2 * 2, n3)
        Else
            Console.WriteLine("TOTAL: " & n3)
        End If
    End Sub
    

    Way 2 - While Loop:

    Protected Sub RussianPeasantMultiplication1(ByVal n1 As Integer, ByVal n2 As Integer)
        Dim RunningTotal As Integer = 0
        While (Math.Abs(n1))
            Console.WriteLine(n1 & " x " & n2)
            RunningTotal = RunningTotal + IIf(n1 Mod 2, Math.Abs(n2), 0) * IIf(n1 < 0, -1, 1) * IIf(n2 < 0, -1, 1)
            n1 = Math.Floor(Math.Abs(n1 / 2)) * IIf(n1 < 0, -1, 1)
            n2 = n2 * 2
        End While
        Console.WriteLine("TOTAL: " & RunningTotal)
    End Sub
    
  • Alex Elder (unregistered)

    unsigned int mu_ru(a, b) { unsigned int c = 0;

        while ((c += (a & 1) * (b <<= 1) >> 1) && (a >>= 1))
            ;
        return c;
    

    }

  • your mom (unregistered) in reply to mol1111
    package test;

    public class RussianPeasantMultiplication {

    public static void main(String[] args) {
        RussianPeasantMultiplication ruskie = new RussianPeasantMultiplication();
        ruskie.publish(18, 23);
        ruskie.publish(13, 13);
        ruskie.publish(15, 0);
        ruskie.publish(0, 15);
        ruskie.publish(-2, 2);
        ruskie.publish(2, -2);
    }
    
    private void publish(int a, int b) {
        System.out.println(a + " X " + b + " = " + multiply(a, b) + " "
                + m(a, b, 0));
    
    }
    
    public int multiply(int a, int b) {
        return recursiveMultiply(a, b, 0);
    }
    
    /**
     * Tail recursive Russian peasant multiplication
     */
    private int recursiveMultiply(int a, int b, int total) {
        if (Math.abs(a) >= 1) {
            if (a % 2 == 0) {
                return recursiveMultiply(a / 2, b * 2, total);
            } else {
                if (a < 0) {
                    return recursiveMultiply(a / 2, b * 2, total - b);
                } else {
                    return recursiveMultiply(a / 2, b * 2, total + b);
                }
            }
        } else {
            return total;
        }
    }
    
    /**
     * In Soviet Russia, tail recurse you.
     * 
     * @param a
     * @param b
     * @param t
     * @return a==0?t:a%2==0?m(a/2, b*2, t):m(a/2, b*2, a<0?t-b:t+b);
     */
    private int m(int a, int b, int t) {
        return a == 0 ? t : a % 2 == 0 ? m(a / 2, b * 2, t) : m(a / 2, b * 2,
                a < 0 ? t - b : t + b);
    }
    

    }

  • your mom (unregistered) in reply to your mom

    Java

  • JavaGuru (unregistered)

    public class Praxis {

    public static int multiply(int a, int b) { if(a < 0) { a *= -1; b *= -1; }

    int c = 0;
    while(a >= 1)
    {
    	if((a & 0x1) == 1) c += b;
    	a >>= 1;
    	b <<= 1;
    }
    return c;
    

    }

    public static void main(String[] args) { int a = Integer.parseInt(args[0]); int b = Integer.parseInt(args[1]); int c = multiply(a, b); System.out.println(a + " x " + b + " = " + c); }

    }

  • M (unregistered)

    Maude solution

    mod RUSSIAN is
      including NAT .
      sorts Obj .
      op <_,_,_> : Nat Nat Nat -> Obj .
      vars A B R : Nat .
      crl < A, B, R > => < A quo 2, B + B, R + if A rem 2 == 1 then B else 0 fi > if A > 0 . 
    endm
    
    rew < 18, 23, 0 > .
    
    rewrite in RUSSIAN : < 18,23,0 > .
    rewrites: 41 in 139000ms cpu (0ms real) (0 rewrites/second)
    result Obj: < 0,736,414 >
    
  • aMo (unregistered)

    int ru_mult(int a, int b) { int result = 0; do { if(a % 2) result += b; b <<= 1; } while(a >>= 1); return result; }

    i can't do it smaller + faster than that..

  • aMo (unregistered) in reply to Alex Elder

    this doesn't work for me..

  • (cs) in reply to egilhh

    I'm teaching myself Clojure, so I created a version of this in Clojure using sequence transformations:

    (defn peasant-step
      "Performs one step in the peasant multiplication algorithm, taking a 
      two-element vector as input, and returning a two-element vector"
      [[a b]]
      [(quot a 2) (* b 2)])
    
    (defn all-peasant-steps
      "For a given pair of numbers, returns all peasant multiplication steps"
      [a b]
      (for [s (iterate peasant-step [a b]) :while (#(not (zero? (first %))) s)] s))
    
    (defn odd-peasant-steps
      "Return all peasant steps where the first element is odd"
      [steps]
      (for [s steps :when (odd? (first s))] s))
    
    (defn peasant-multiply
      "Perform peasant multiplication on two numbers"
      [a b]
      (reduce + 
        (map second (odd-peasant-steps (all-peasant-steps a b)))))
    
  • Rodrigo Alfonso (unregistered)

    Kind of late but:

        private static int RussianMultiply(int firstNumber, int secondNumber)
        {
            if (firstNumber == 0 || secondNumber == 0)
                return 0;
            if (firstNumber == 1)
                return (secondNumber);
            return (RussianMultiply(firstNumber / 2, secondNumber * 2) + (firstNumber % 2 == 0 ? 0 : secondNumber));
        }
    
  • joy (unregistered)

    Plus size beachchanel sale and swimwear chanel jewelryhas been especially made to support the contours of your body. In plus size swim suits and bikinis,chanel Brooches you can feel chanelchanel jewelry sale necklaces for salerelaxed and comfortable on the beach. Finding a beautifulchanel jewelry for sale wedding gown is getting easier too. With the availability of plus size bridal wear, kisschanel Banglesyour worries goodbye. Plus size bridal wear is readily available in most department chanel Braceletsand bridal stores with a large range to chose from. There are plentychanel Earrings of plus size designs and clothing available in the shops and alternatively mailchanel Necklaces order from catalogues or from the Internet. So you can now shop till you drop.

  • anonymous (unregistered)

    #!usr/bin/perl6 -e

    Int $i; Int $j; Int @i; Int @j; $i = +(input());

    $j = +(input());

    while i != 1 { @i ,= $i; @j ,= $j; $i +>= 1; $j +<= 1; } @j = gather for @i Z @j -> $test, $result { take $result if $test % 2 } say([+] @j);

  • juli (unregistered)

    import java.io.DataInputStream; import java.io.IOException; public class PergjysmoShumezo {

    long k1=System.currentTimeMillis();
    /**
     * @param args
     */
    static boolean tek(int numer1)
    {
    	if ((numer1%2)!=0)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    public static void main(String[] args) throws IOException
    {
    	//Numrat duhet te jene te plote
    	
    	int numer1;
    	int numer2;
    	int shuma=0;
    	DataInputStream in =new DataInputStream(System.in);
    	System.out.println("vendosni numrin1");
    	numer1=Integer.parseInt(in.readLine());
    	System.out.println("vendosni numrin2");
    	numer2=Integer.parseInt(in.readLine());
    	
    	//Numri i pare duhet te jete pozitiv
    	while(numer1>0)
    	{
    		if(tek(numer1))
    		{
    			shuma=shuma+numer2;
    		}
    		numer1=numer1/2;
    		numer2=numer2*2;
    	}
    	
    	System.out.println("vlera eshte:"+shuma);
    	
    
    }
    

    long k2=System.currentTimeMillis();

    { System.out.println("Koha e e ekzekutimit eshte k2-k1=" +(k2-k1)); } }

  • J (unregistered)
       bs =: 4 : '#.(#:x),y#0'
       rm =: 4 : '+/y bs"0 I.|.#:x'
       18 rm 23
    2304

    x is the left argument, y the right argument.

    x bs y: bitshift (x<<y) y#0 A list of y 0's. (#:x) The binary representation of x. , Join these together. #. Convert binary list to a number.

    x rm y: russian peasant multiplication. |.#:y Reverse binary of x (lowest bit first) I. Get indices of all 1's y bs"0 Bitshift each element in the list with y as left argument. +/ Sum.

  • Limao Luo (unregistered)
    public static long multiply(int a, int b) {
        long tot = 0;
        while (a > 0) {
            if ((a & 1) == 1)
                tot += b;
            a >>= 1;
            b <<= 1;
        }
        return tot;
    }
    

    captcha: "iusto" = I have gusto.

  • Anders (unregistered)

    function rpm(x,y){return x?rpm(x>>1,y+y)+y*(x&1):0}

    Very tweetable JavaScript indeed! :)

  • Adeel Zafar Soomro (unregistered)

    A solution in Factor programming language:

    : 2* ( x -- y )
        1 shift ; inline
    
    : rpm ( x y -- x*y )
        [ dup 0 > ]
        [ dup odd? [ over ] [ 0 ] if
          [ [ 2* ] [ 2/ ] bi* ] dip ]
        produce sum 2nip ;

    For integers, it produces the correct result so long as the second argument is non-negative.

  • Alexander Schneider (unregistered)

    I got a Clojure solution here. (I don't even know if the post is being still watched)

    (defn russian-mult
      "Multiplies two number the russian way. Na sdorowje!"
      [fnum snum]
      (loop [left fnum
             right snum
             sum 0]
        (if (= left 1)
          (+ sum right)
          (recur (quot left 2)
                 (* right 2)
                 (if (even? left) sum (+ sum right))))))
    
  • AI (unregistered)

    I wrote it in Befunge. Hopefully nothing was changed when I copied it...

    >&&v     >01g84*-.@
        >:0`!|
    >   ^    >:2%!v
                 v_\:01g+01p\v
                 >v          <
    ^       \*2\/2<
    ^  <

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #:

« Return to Article