Comment On Russian Peasant Multiplication

And of course in Haskell:

multiply n m = sum $ map snd $ filter (odd . fst) $ russian n m
where russian 1 m = [(1,m)]
russian n m = (n,m) : russian (n `div` 2) (m * 2)

My take using Progress V9 (will probably work in most older versions as well)
Code:

function multiply returns integer (input ip_int1 as integer, input ip_int2 as integer):

define variable v_result as integer no-undo.



if ip_int1 = 1 then

return ip_int2.



if ip_int1 mod 2 <> 0 then

v_result = v_result + ip_int2.



v_result = v_result + multiply(integer(truncate(ip_int1 / 2, 0)), (ip_int2 * 2)).

return v_result.

end.



message "Russian Peasant Notation: " multiply(18, 23) view-as alert-box info buttons ok.

static int m(int x,int y){return x==1?y:x%2==0?m(x/=2,y*=2):y+m(x/=2,y*=2);}

I've been a TDWTF reader for the past few months, and I'm dedicating my first comment to this interesting question here:

In PHP:

<?

function multiply($x, $y, $o = 0) {
return $x > 1 ?
multiply(floor($x / 2), $y * 2, $o + $x % 2 * $y) :
$o + $y;
}

echo multiply(18, 23);

?>

Also available at:
http://phpieceofcake.com/?83344437

Not sure if anyone posted this solution yet. Here's mine:

private int Multiply(int x, int y)
{
return x == 1 ? y : Multiply(x / 2, y * 2) + x % 2 * y;
}

Mike5:

Anonymous Coward:

Prolog...

"optimized" with bit-shifting ...

To get the real prolog feeling:

%% russian(?A,?B,?P).

%% multiplies A and B the russian way, 

%% all parameters are optional

russian(A,B,P) :- nonvar(A), var(B), !, russian(B,A,P).

russian(A,B,P) :- var(A), (nonvar(B),!;length(_,P),between(0,P,B)), 

                  row(A,B,P,0,P).

russian(A,B,P) :- nonvar(A), row(A,B,P,0,P), !.



row(_,_,P,F,_) :- nonvar(P), P < 1<<(F-1), !, fail.

row(0,_,_,_,0).

row(A,B,P,F,R) :-

    row(Ax,B<<1,P,F+1,Rx),

    double(Ax,A,Odd),

    R is Rx+B*Odd.

    

double(0,1,1) :- !.

double(X,X2,Odd) :- (Odd=0;Odd=1), X2 is X*2+Odd.

may need some optimization though...

Mike5:

Anonymous Coward:

Prolog...

"optimized" with bit-shifting ...

To get the real prolog feeling:

%% russian(?A,?B,?P).

%% multiplies A and B the russian way, 

%% all parameters are optional

russian(A,B,P) :- nonvar(A), var(B), !, russian(B,A,P).

russian(A,B,P) :- var(A), (nonvar(B),!;length(_,P),between(0,P,B)), 

                  row(A,B,P,0,P).

russian(A,B,P) :- nonvar(A), row(A,B,P,0,P), !.



row(_,_,P,F,_) :- nonvar(P), P < 1<<(F-1), !, fail.

row(0,_,_,_,0).

row(A,B,P,F,R) :-

    row(Ax,B<<1,P,F+1,Rx),

    double(Ax,A,Odd),

    R is Rx+B*Odd.

    

double(0,1,1) :- !.

double(X,X2,Odd) :- (Odd=0;Odd=1), X2 is X*2+Odd.

may need some optimization though...

PHP and Perl, and gives the same output for both:

#

#<?php echo "\x8";ob_start();

$rm='return int($a/2)==1?$b*2:(int($a/2)%2==1?$b*2+rm(int($a/2),$b*2):rm(int($a/2),$b*2));';

#?><?php function int($a){return floor($a);}$a=$argv[1];$b=$argv[2];eval('function rm($a, $b){'.$rm.'}');?>

$a=$ARGV[0];$b=$ARGV[1];eval("sub rm{\$a=shift;\$b=shift;$rm}");#<?php ob_end_clean();

print rm($a,$b);

Came up with a more condensed PHP function after another 45 minutes or so:

function multiply($x, $y) {
return $x % 2 * $y + ($x > 1 ? multiply(floor($x / 2), $y * 2) : 0);
}

LatecomerX:

I've been a TDWTF reader for the past few months, and I'm dedicating my first comment to this interesting question here:

In PHP:

<?

function multiply($x, $y, $o = 0) {
return $x > 1 ?
multiply(floor($x / 2), $y * 2, $o + $x % 2 * $y) :
$o + $y;
}

echo multiply(18, 23);

?>

Also available at:
http://phpieceofcake.com/?83344437

Here's some Lua code:

function russian(a, b)

	if a==1 then

		return b

	else

		if a%2==1 then

			return b+russian(math.floor(a/2), b*2)

		else

			return russian(math.floor(a/2), b*2)

		end

	end

end

Code only: 189 bytes
Code with BBCode coloring: 1190 bytes

Someone:

An ABAP solution that compiles:

REPORT MULTIP.



DATA: product TYPE i,

      left_num TYPE f VALUE 18,

      right_num TYPE f VALUE 23,

      half_left TYPE f,

      half_left_floor TYPE f.



WHILE left_num > 0.

  "check for even number and add to product (there must be a better way...)

  half_left = left_num / 2.

  half_left_floor = FLOOR( left_num / 2 ).

  IF half_left <> half_left_floor.

    product = product + right_num.

  ENDIF.



  "move to next set

  left_num = FLOOR( left_num / 2 ).

  right_num = right_num * 2.

ENDWHILE.



WRITE product.

Yes there is a better way, the MOD operator. Also, when creating a whole report for it, why not include a nice, verbose, selection screen?

SELECTION-SCREEN BEGIN OF BLOCK 1 WITH FRAME TITLE 'Input'.

PARAMETER p_num1 TYPE I DEFAULT 18 OBLIGATORY.

PARAMETER p_num2 TYPE I DEFAULT 23 OBLIGATORY.

SELECTION-SCREEN END OF BLOCK 1.

#! -*- Encoding: Latin-1 -*-

import threading
import Queue

# classic spaghetti code
def rupmul1(a,aa):
aaa = lambda:(a % 2) and aa
aaaa = aaa()
while a > 1:
a, aa = a/2, aa*2
aaaa += aaa()
return aaaa

# functional programming
rupmul2 = lambda a,b: sum(map(
lambda b:a&b[0] and b[1],zip(map(
lambda a:pow(2,a),range(31)),map(
lambda a:b*pow(2,a),range(31)))))

# multicore power using threads + functional programming = TOTAL WIN!
def rupmul3(a,b,__=Queue.Queue()):
return sum(map(lambda _:__.get(),map(lambda _:[threading.Thread(target=lambda _:
__.put((a&1<<_) and b<<_),args=(_,)).start(),_][-1],range(32))))

def selftest():
import random

for k in range(60):
a = random.randrange(1,10000)
b = random.randrange(1,10000)

n = a*b
assert rupmul1(a,b) == rupmul2(a,b) == rupmul3(a,b) == a*b

if __name__ == "__main__":
selftest()

ParkinT:

Wow!
I had not time to submit a solution.
Everyone was too busy Russian to provide an answer!

OH DEAR!!! LOL!

That ARM code is both wrong and far too long. This is perhaps slightly less wrong:

    mov    r2,#0

loop:

    movs   r1,r1,lsr #1

    addcs  r2,r2,r0

    mov    r0,r0,lsl #1

    bne    loop

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

Apologies if this has been pointed out already but you can shorten that slightly.

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

Tail recursive in IL (based on 278641, not sure if C# can compile a tail recursivity, I'll have to check later). The first param is the acumulator and should be initialized to 0 (or wrapped in another method):

.method private hidebysig static int64 Russian(int64 a, int64 f, int64 s) cil managed
{
.maxstack 4
ldarg.0
dup
ldarg.1
brfalse.s done
ldarg.1
ldc.i4.1
and
ldarg.2
mul
add
ldarg.1
ldc.i4.1
shr
ldarg.2
ldc.i4.1
shl
tail.
call int64 RussianMult.Program::Russian(int64, int64, int64)
done:
ret
}

BTW, I think I've never seen a post in this site with 12 pages of comments.

C++ with a 'simple' iterator.

#include <numeric>

struct gen {

    int a, b;

    gen(int a=0, int b=0) : a(a), b(b) { }

    gen operator*() { return *this; }

    void operator++() { a /= 2; b *= 2; }

    bool operator!=(gen b) { return a != b.a; }

    gen operator+(gen r) {

        if (r.a % 2)

            return gen(0, b + r.b);

        return gen(0, b);

    }

};



int mul(int a, int b) {

    return std::accumulate(gen(a, b), gen(), gen()).b;

}

Python, nominate for shortest one :)
49 characters.
And, with python, numbers multiply peasants.

m=lambda a,b:sum(b<<i for i in range(a)if a&1<<i)

Java:

public static long multiply(int a, int b) {

    if (a < 0) {

        a = -a;

        b = -b;

    }

    int result = 0;

    while (a > 0) {

        int tz = Integer.numberOfTrailingZeros(a);

        result += b << tz;

        a = a >> ++tz << tz;

    }

    return result;

}

This nearly works; I'll leave the rest to the in-house coders.

    public static int multiply(int x, int y) {

        StringBuffer sb = new StringBuffer();

        sb.append("" + x);

        sb.append(" x "); // prettify output

        sb.append(y + "");



        while (doIt(sb));



        System.err.println(sb.toString());



        String str = sb.toString();

        StringTokenizer st = new StringTokenizer(sb.toString(), "\n ");

        int o = 0;

        while (st.hasMoreTokens()) {

            if (Integer.parseInt(st.nextToken()) % 2 == 0) {

                //do nothing

            } else {

                o += Integer.parseInt(st.nextToken());

            }

        }



        return o;

    }



    public static boolean doIt(StringBuffer sb) {

        int line = sb.lastIndexOf("\n");

        line++; //need this for some reason!!!!!1!



        //if(line<0){

        //      line++;

        //}



        int split = sb.indexOf(" ", line);

        String x = sb.substring(line, split);

        String y = sb.substring(split);



        sb.append("\n");

        sb.append(Integer.parseInt(x) / 2);

        sb.append(" ");

        sb.append(Integer.parseInt(y.trim()) * 2);



        if (x.equalsIgnoreCase("1")) {

            return false;

        }



        return true;

    }

    

//    public static int multiply(int x, int y) {

//        int out = 0;

//        while (x != 1) {

//            if (x % 2 != 0) {

//                out += y;

//            }

//            x = x >> 1;

//            y = y << 1;

//        }

//        return out + y;

//    }

Wow, the number of unreadable and unmaintainable examples outweight the readable and maintainable ones by about 50:1!
That's the real WTF...

my crappy C version that doesn't work for negative numbers ;)
----------------------- <snip> --------------------------

#include <stdio.h>



main( argc, argv)

int argc;

char *argv[3];

{

	int n1 = 0;

	int n2 = 0;

	int n3 = 0;

	

	n1 = atoi(argv[1]);

	n2 = atoi(argv[2]);

	/* Implement Russian Peasant Multiplication algorithm */

	if ( argc != 3 )

	{

	   printf("USAGE: rpm n n\nrpm multiplies two numbers via the Russian peasant method\n");

	   return(1);

	}

	

	/* if either parameter is zero, the answer is zero */

	if ( n1 == 0 || n2 == 0 )

	{

	   printf("Result of %d * %d via Russian peasant method is: 0.\n", n1, n2);

	   return(0);		

	}

	

	if ( n1 == 1 || n2 == 1 )

	{

	   printf("Result of %d * %d via Russian peasant method is: %d.\n", n1, n2, n1*n2);

	   return(0);		

	}

	

	if ( (n1 % 2) != 0 )

	{

	      n3 = n2;

	}

	      

	while ( n1 >= 1 )

	{

		n1 = n1 / 2;

		n2 = n2 * 2;

		if ( (n1 % 2) != 0 )

		{

			  n3 = n3 + n2;  

		} 

  }				

	

	printf("Result of %d * %d via Russian peasant method is: %d.\n", atoi(argv[1]), atoi(argv[2]), n3);

	

	return(0);

} 

----------------------- <snip> ---------------------

The C# compiler does tail call optimisation only on x64 afaik.

Smalltalk

Note that this overwrites the System's definition of *
and everything still works.

* aNumber



	self isZero ifTrue: [^0].

	self < 0

		ifTrue: [^(self negated * aNumber) negated]

		ifFalse:  [^ ((self bitShift: -1) * (aNumber + aNumber)) + ((self bitAnd: 1) = 1 ifTrue: [aNumber] ifFalse: [0])]

Another SQL (T-SQL) Answer:
DECLARE @X INT, @Y INT, @Z INT
SELECT @X=18,@Y=23,@Z=0
WHILE @X!=1
BEGIN
IF (@X%2)!=0
SET @Z=@Z+@Y
SET @X=@X/2
SET @Y=@Y*2
END
SET @Z=@Z+@Y
SELECT @Z

577 comments later and still no recursive VB.Net solution, so here's my second try; it handles negatives as well and doesn't use multiplication:

Function Russiply2(ByVal a As Long, ByVal b As Long) As Long



  Return If(a < 0, Russiply2(-a, -b), If(a > 1, If((a And 1) = 1, b, 0) + Russiply2(a >> 1, b << 1), If(a = 1, b, 0)))



End Function

Just checked on an x64. At least by default, it doesn't do tail recursion. Also, when compiled in Release the output is really really close to my solution. The only real difference is that it branches on non-equal instead of false.

joeyadams:

zcl:

Yes ,your article is very good, we have the same belief with you,so let me introduce the area to you.Now Juicy Jewelry become more adn more popular within all kind of people. Juicy couture is a kind of juicy series . It won a good reputation. Juicy sale often held its regular discount juicy activities,such as juicy charms,cheap juicy and so on.In these activities juicy couture sale got great success. juicy couture consists of two main aspects, juicy couture jewelry and juicy couture accessories
Juicy couture series are worthwhile than other juicy on sales. They have a lot of discounted jewelry,for example discount Juicy Couture necklaces, juicy earrings , juicy bracelets and rings on sale. Benefit from the discount,you can get juicy jewelry save up to 30%, We assure you of our best services at all times.

Can we please end the off-topic rants about Russian peasant multiplication and get back to our juicy jewelry discussion?

I believe the problem is that we've made this poor russian peasant thirsty, after warping his brain with such compressed algorithms in as many languages we could come up with. PDP-8, nice touch, but its still ASM! CP/M shell anyone???

Lom:

Python, nominate for shortest one :)
49 characters.
And, with python, numbers multiply peasants.

m=lambda a,b:sum(b<<i for i in range(a)if a&1<<i)

There is a 44 character python, and a 40 characther bc, although you still have several characters to go to catch perl :)

rjp:

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

Apologies if this has been pointed out already but you can shorten that slightly.

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

It has, but then its perl.. TIMTOW! stub..! oww.

Only works with positive integers.

<?xml version="1.0"?>

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">



    <!-- get initial values out of xml -->

    <xsl:template match="/">

        <xsl:variable name="number1">

            <xsl:value-of select="*/number[1]"/>

        </xsl:variable>



        <xsl:variable name="number2">

            <xsl:value-of select="*/number[2]"/>

        </xsl:variable>



        <!--call the loop for the first time-->

        <xsl:call-template name="loop">

            <xsl:with-param name="a" select="$number1"/>

            <xsl:with-param name="b" select="$number2"/>

            <xsl:with-param name="r" select="0"/>

        </xsl:call-template>

    </xsl:template>



    <!-- the loop to recurse over-->

    <xsl:template name="loop">

        <xsl:param name="a"/>

        <xsl:param name="b"/>

        <xsl:param name="r"/>

        <xsl:choose>

            <xsl:when test="$a = 1">

                <!-- we have finished print the result -->

                <xsl:value-of select="$b + $r"/>

            </xsl:when>

            <xsl:otherwise>

                <!--call the template again. each time divide "a" by 2 multiple "b" by 2, and sum "b" to the remainder if "a" is odd -->

                <xsl:call-template name="loop">

                    <xsl:with-param name="a" select="round(($a div 2) - 0.5)"/>

                    <xsl:with-param name="b" select="$b * 2"/>

                    <xsl:with-param name="r" select="($a mod 2) * $b + $r"/>

                </xsl:call-template>

            </xsl:otherwise>

        </xsl:choose>

    </xsl:template>



</xsl:stylesheet>

Another version, now in Rebol.

multru: func [a b /local res] [

	res: copy []

	append res [res: 0]

	append res compose [(either a < 0 [[-res]] [[res]])]

        res: back tail res

	until [

		insert res compose/deep [either odd? (a) [add res (b)] [res]]

		insert res to-set-word 'res

		set [a b] compose [(round/down divide a 2) (multiply b 2)]

		zero? a

	]

	do head res

]

It generates rebol code composed from additions and checks for oddity and then executes it. For 23 and 18 generated code looks like:

[res: 0 res: either odd? 1 [add res 288] [res] res: either odd? 2 [add res 144] [res] res: either odd? 5 [add res 72] [

res] res: either odd? 11 [add res 36] [res] res: either odd? 23 [add res 18] [res] res]

Ok, I couldn't resist. Here's an (amended!) brainfuck interpreter in Java, running the brainfuck code from Qwertyuiopas:

public class BrainfuckJavaRussianMultiplication {

  private static final String input = 

    ">>>>>,>>,[->+>+<<]<<[[-[>+<-]>[>+>>>+<<<<-[[<+>-]>[-]<]]<]>>[>>[-]" +

    "<<[-]]+>[->>>>>++>++<<<<<<]>>]>>>>[-]<<<<<<<[<<<<<]>>>>>[>>[->>>>>" +

    "+<<<<<]>>>]>>%";

	

  BrainfuckJavaRussionMultiplication(String code) {

    int ptr = 0;

    int [] cell = new int[10000];

		

    for (int i = 0; i < 10000; i++) {

      cell[i] = 0;			

    }

		

    char [] chars = code.toCharArray();

    for (int i = 0, n = chars.length; i < n; i++) {

      char c = chars[i];

      if (c == '>') {

        ptr++;

      } else if (c == '<') {

        ptr--;

      } else if (c == '+') {

        cell[ptr]++;

      } else if (c == '-') {

        cell[ptr]--;

      } else if (c == '.') {

        System.out.print((char) cell[ptr]);

      } else if (c == '%') {

        System.out.print((int) cell[ptr]);

      } else if (c == ',') {

        Scanner in = new Scanner(System.in);

        try {

          cell[ptr] = Integer.parseInt(in.nextLine());

        } catch (Exception e) {

	  cell[ptr] = 0;

        }

      } else if (c == '[') {

	if (cell[ptr] == 0) {

	  int counter = 0;

	  int position = i + 1;

	  while (chars[position] != ']' || counter != 0) {

	    if (chars[position] == '[') {

	      counter++;

	    }

	    if (chars[position] == ']') {

	      counter--;

	    }

	    position++;

	  }

	  i = position;

       }

     } else if (c == ']') {

       int counter = 0;

       int position = i - 1;

       while (chars[position] != '[' || counter != 0) {

         if (chars[position] == ']') {

	   counter++;

	 }

	 if (chars[position] == '[') {

	   counter--;

	 }

	 position--;

       }

       i = position - 1;				

     }

   }

  }

	

  public static void main(String [] args) {

    new BrainfuckJavaRussianMultiplication(input);

  }

}

As you can see, you may enter integers (instead of characters whose ASCII code is interpreted), also we are dealing with Brainfuck++ here, since it has the % command ;)

Haskell (with quickCheck to test it) :

import Test.QuickCheck



pm 0 y = 0 

pm 1 y = y 

pm x y 

  | x < 0     = - pm (-x) y 

  | even x    = next

  | otherwise = y + next 

 where next = pm (x `div` 2) (y*2) 



prop_PMOK x y = pm x y == x*y

   where types = (x::Int,y::Int) 



quickCheck prop_PMOK 

#!/usr/bin/python



from sys import argv



if len(argv) < 3:

	print "input values missing"

	print "usage: "

	print argv[0] + " value1 value2"

	exit()



a = int(argv[1])

b = int(argv[2])

acc = 0

sep = " x "



justWidth = 5



while (a > 0):

  if a & 0x1:

    acc = acc + b

    print "  ",

  else:

    print "--",



  print str(a).rjust(justWidth) + sep + str(b).rjust(justWidth)

  sep = "   "



  a = a >> 1

  b = b << 1



print "   " + "-" * ((justWidth*2)+len(sep))

print "  =" + str(acc).rjust((justWidth*2)+len(sep))

The output:

>pmath.py 18 23

--    18 x    23

       9      46

--     4      92

--     2     184

       1     368

   -------------

  =          414

The lines starting with -- should be considered crossed out

soulution as c++ template:

//////////////////////////////

template <int I, int J>

struct Pmul

{

  operator int()	

  {

    return (I%2)?J+Pmul<I/2,J*2>():Pmul<I/2,J*2>();

  }

};

//////////////////////////////

template <int J>

struct Pmul<1, J>

{

  operator int()	

  {

    return J;						

  }

};

//////////////////////////////

i.e.:

int res = Pmul<2311, 1234>();

Well, I wanted to go back and make this more "clever", but this works just fine (C#):

public static int MultiplyLikeARussianPeasant(int x, int y)

{

    int sum = 0;

    do

    {

        sum += (x%2 == 1) ? y : 0;

        x /= 2;

        y *= 2;

    } while (x >= 1);

    return sum;

}

(I haven't checked the comments for this solution, that would have been cheating!)

WarheadsSE:

Lom:

Python, nominate for shortest one :)
49 characters.
And, with python, numbers multiply peasants.

m=lambda a,b:sum(b<<i for i in range(a)if a&1<<i)

There is a 44 character python, and a 40 characther bc, although you still have several characters to go to catch perl :)

37 using * and /

m=lambda a,b:a and(a&1)*b+m(a/2,b+b)

41 without

m=lambda a,b:a and[0,b][a&1]+m(a>>1,b+b)

Function peasant(factor1, factor2)
peasant = 0
If factor1 < 0 Then factor2 = -factor2
While factor1 <> 0
If (factor1 / 2) <> Round(factor1 / 2, 0) Then peasant = peasant + factor2
factor1 = factor1 / 2 - (factor1 Mod 2) / 2
factor2 = 2 * factor2
Wend
End Function

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.

When you start with the 45 in the left column, you forgot to include the 76 in your sum.

Oh, and by the way:

(define (pm x y)

  (define (pm2 acc x y)

    (cond

      [(= x 0) acc]

      [(= (remainder x 2) 0) (pm2 acc (floor (/ x 2)) (+ y y))]

      [else (pm2 (+ acc y) (floor (/ x 2)) (+ y y))]

    )

  )

  

  (pm2 0 x y)

)

In rebol with caching of generated code stuff.

multru: func [a b /local res cached] [	

	if not value? 'cache [

		set/any in system/words 'cache []		

	]	

	select-cache: func [a b /local cached] [select/only cache compose [(a) (b)]]	

	case [

		found? cached: any [select-cache a b select-cache b a] [return do cached]		 

		true [

			append/only cache compose [(a) (b)]			

			res: copy []

			append res [res: 0]	

			append res compose [(either a < 0 [[-res]] [[res]])]

			res: back tail res

			until [		

				insert res compose/deep [either odd? (a) [add res (b)] [res]]

				insert res to-set-word 'res

				set [a b] compose [(round/down divide a 2) (multiply b 2)]

				zero? a

			]			

			append/only cache head res	

		]

	]

	do last cache

]

I'm in the process of learning Haskell so here's my haskell solution. Feel free to give feedback so I can improve.

rus 0 _ = 0
rus a b
| a < 0 = (-1) * (rus (abs a) b)
| b < 0 = (-1) * (rus a (abs b))
| odd a = b + (rus (div a 2) (b*2) )
| otherwise = (rus (div a 2) (b*2) )

Erlang, as a module.

-module(peasant).

-export([peasant/2]).



peasant (1,Y) -> Y;

peasant (X,Y) when (X rem 2 == 1) ->

    Y + peasant ((X bsr 1),(Y bsl 1));

peasant (X,Y) ->

    peasant ((X bsr 1),(Y bsl 1)).

c++ templates


template <unsigned int a, unsigned int b> struct RM_ {
static const unsigned int result = a & 0x1 ? b + RM_<a / 2, b * 2>::result : RM_<a / 2, b * 2>::result;
};
template <unsigned int b> struct RM_<1, b> {
static const unsigned int result = b;
};

unsigned int c = RM_<18, 23>::result;

The only real solution:

<?php

function ymhoxntb($n1, $n2)

{

  $written = "$n1 x $n2";



  // Create the next line, dividing the left number by two and

  // doubling the right.

  do {

    // Get the last line

    $lines = split("\n", $written);

    $line = $lines[count($lines)-1];

    preg_match("/([0-9]*)\s+[x]?\s*([0-9]*)/", $line, $matches);

    $a1 = intval($matches[1]);

    $a2 = intval($matches[2]);



    // Make the next line

    $a1 = floor($a1/2);

    $a2 *= 2;

    $written .= "\n$a1 $a2";

  }

  while($a1 > 1);

  echo $written."\n\n";



  // Cross out the even numbers on the left side

  $docrossout = TRUE;

  for($i = 0; $i < strlen($written); $i++) {

    if($written[$i] == "\n") {

      $docrossout = FALSE;

      if(intval(substr($written, $i)) % 2 == 0)

        $docrossout = TRUE;

      continue;

    }



    if($docrossout)

      $written[$i] = "-";

  }

  echo $written."\n\n";



  // Add the remaining right columns

  $lines = split("\n", $written);

  $result = "";

  foreach($lines AS $line) {

    if(!preg_match("/([0-9]*)\s+[x]?\s*([0-9]*)/", $line, $matches))

      continue;



    if($result == "")

      $result .= $matches[2];

    else

      $result .= " + ".$matches[2];

  }

  echo $result." = ";

  eval("echo ".$result.";");

  echo "\n";

}

ymhoxntb(18, 23);

This is in Java. It was tested and works for negatives.

public static int doRussianMultiply(int a, int b)

{

   if (a < 0) return -doRussianMultiply(-a,b); 

      

   int sum = 0;

   while (a > 1) {

      if ((a & 1) == 1) sum += b;

      a >>= 1;

      b += b;

   }

   if (a == 1) sum += b;

   

   return sum;

}

Late to the game, I guess. Replying without viewing comments, wonder if mine is original :)

http://pastebin.com/f50d7e6d5

I guess I should post the code, not just a link to it:

/**
* Submission for TDWTF Programming Praxis 1: Russian Peasant Multiplication
* July 23, 2009
*/
#include <stdio.h>
#include <stdlib.h>

void
usage (void)
{
printf ("usage: rmult <int> <int>\n") ;
exit (-1) ;
}

int
main (int argc, char **argv)
{
int a, b, total = 0 ;

if (argc != 3)
usage () ;

a = atoi (argv[1]) ;
b = atoi (argv[2]) ;
if (a <= 0 || b <= 0)
usage () ;

printf ("%i * %i = ", a, b) ;

while (1) {
if (a % 2)
total += b ;

if (a == 1)
break ;

a /= 2 ;
b *= 2 ;
}

printf ("%i\n", total) ;

return 0 ;
}

public static double RussianMultiply(int left, int right)
{
var columns = new Dictionary<int, int> {{left, right}};
var product=0;
while (left > 1)
columns.Add(left /= 2, right *= 2);

foreach (var row in columns)
product += row.Value * (row.Key % 2);

return product;
}