The Daily WTF: Curious Perversions in Information Technology

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