The Daily WTF: Curious Perversions in Information Technology

2009-08-01 Reply Admin

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

2009-08-04 Reply Admin

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

2009-08-04 Reply Admin

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

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

}

2009-08-05 Reply Admin

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

}

2009-08-05 Reply Admin

Java

2009-08-11 Reply Admin

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

}

2009-08-12 Reply Admin

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 >

2009-12-29 Reply Admin

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

2009-12-29 Reply Admin

this doesn't work for me..

Matthew Justin · 2010-01-11 Reply Admin

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

2010-03-30 Reply Admin

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

2010-04-07 Reply Admin

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.

2010-06-15 Reply Admin

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

2011-01-17 Reply Admin

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

2011-07-11 Reply Admin

   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.

2012-02-14 Reply Admin

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.

2013-02-27 Reply Admin

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

Very tweetable JavaScript indeed! :)

2013-03-08 Reply Admin

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.

2014-03-13 Reply Admin

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

2014-05-22 Reply Admin

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

Russian Peasant Multiplication

Leave a comment on “Russian Peasant Multiplication”