Comment On Russian Peasant Multiplication

Here's another VBScript version meant to run as an Excel macro.

It assumes the values to be multipled are in cells A2 and B2 of the first Worksheet and it stores all of the intermediate numbers in the cells below as it calculates.

The final output is put in cell C2

Public Sub CalculateRussianPeasant()

    Dim curSheet As Worksheet

    Dim curRow: curRow = 2

    Dim bDone

    Dim i As Integer

    Dim total

    

    Set curSheet = Worksheets(1)

    

    Rows("3:65536").Select

    Selection.Delete Shift:=xlUp

    

    While Not bDone

        curSheet.Cells((curRow + 1), 1).Value = CInt(curSheet.Cells(curRow, 1).Value / 2)

        curSheet.Cells((curRow + 1), 2).Value = CInt(curSheet.Cells(curRow, 2).Value * 2)

        

        curRow = curRow + 1

        

        If curSheet.Cells(curRow, 1).Value = 1 Then

            bDone = True

        End If

    Wend

    

    curSheet.Cells(2, 3).Value = 0

    For i = 2 To curRow

        If curSheet.Cells(i, 1).Value Mod 2 <> 0 Then

            curSheet.Cells(2, 3).Value = curSheet.Cells(2, 3).Value + curSheet.Cells(i, 2).Value

        ElseIf i > 2 Then

            Range("A" & i & ":B" & i).Select

            With Selection.Font

                .Strikethrough = True

                .ColorIndex = 3

            End With

        End If

    Next

    

    Range("C2").Select

End Sub

A version for the D programming language; both as an interative function and a template:

// Regular version.  Can also be used in compile-time code.

long multiply(long a, long b)

{

    if( a == 0 || b == 0 ) return 0;

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

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



    long acc = 0;

    do

    {

        if( a % 2 == 1 )

            acc += b;

        a /= 2;

        b *= 2;

    }

    while( a >= 1 );

    return acc;

}



// Template version

template Multiply(long a, long b)

{

    static if( a == 0 || b == 0 )

        const Multiply = 0L;



    else static if( a < 0 )

        const Multiply = Multiply!(-a, b);



    else static if( b < 0 )

        const Multiply = Multiply!(a, -b);



    else static if( a == 1 )

        const Multiply = b;



    else static if( a % 2 == 1 )

        const Multiply = b + Multiply!(a/2, b*2);



    else

        const Multiply = Multiply!(a/2, b*2);

}

Wow, you make PHP look good, that is pretty impressive.

In Ruby,

class Fixnum

  def *(b)

    a, k = self, 0

    a, b = -a, -b if a < 0

    while a != 0

      k += b if a & 1 == 1

      a >>= 1

      b <<= 1

    end

    k

  end

end

Ruby, one line, non-recursive:

a,b,res=a/2,b*2,(res||0)+(a&1)*b while a>0

Second attempt at C#, this works with negative numbers:
public int RussianMultiply(int operand1, int operand2)
{
int res = 0;
while (operand1 != 0)
{
if (operand1 % 2 == 1) res += operand2;
else if (operand1 % 2 == -1) res -= operand2;
operand1 /= 2;
operand2 *= 2;
}
return res;
}

Different twist on a Ruby solution:

class Fixnum

        def rum n

                product = 0

                self.to_s(2).reverse.split(//).each_with_index do |bit, pos|

                        product += ( n << pos ) if bit.to_i == 1

                end

                product

        end

end



p 3.rum(2)

p 2.rum(3)

p 18.rum(23)

p 23.rum(18)

p 76.rum(45)

p 45.rum(76)

Josh Bohde:

Python 2.6

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

51 characters

I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a.

second attempt at C# recurisive, this works with negative numbers:
public int RecursiveRussianMultiply(int operand1, int operand2)
{
return operand1 == 0 ? 0 : RecursiveRussianMultiply(operand1 / 2, operand2 * 2) + (operand1 % 2 == 1 ? operand2 : 0) + (operand1 % 2 == -1 ? -operand2 : 0);
}

using System;

using System.Collections.Generic;

using System.Text;

using System.Linq;



namespace RussianPeasant

{

    class RussianPeasant

    {

        static void Main(string[] args)

        {

            if (args.Length != 2)

            {

                Console.Error.WriteLine("Peasants can't multiply " + args.Length + " operands!");

                return;

            }



            int left = 0;

            int right = 0;



            if ((!int.TryParse(args[0], out left)) || (!int.TryParse(args[1], out right)))

            {

                Console.Error.WriteLine("Peasants can't multiply non-numeric operands!");

            }





            int solution = (from pair in GetColumns(left, right)

                           where pair.First() % 2 != 0

                           select pair).Sum(p => p.ElementAt(1));



            Console.WriteLine(solution);

            Console.Read();

        }



        public static IEnumerable<IEnumerable<int>> GetColumns(int left, int right)

        {

            yield return new int[] { left, right };

            

            while (left > 0)

            {

                left = left >> 1;

                right = right * 2;



                yield return new int[] { left, right };

            }

        }

    }

}

int first = 18;
int second = 23;

int result = 0;

while ((first = first / 2) >= 1)
{
second = second * 2;

if (first % 2 != 0)
result += second;
}

Rootbeer:

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.

Yeah... it isn't really a good idea. I thought it was more sane until I considered the results...
for 8 bit multiplication we have two 8 bit inputs and a 16 bit output, so the table is 2^16 bits long with 16 bit entries... that's 1M transistors without the decoders/addressing logic. The average 8 bit CPU has a few thousand to a few tens of thousands of transistors. It just gets worse from there - multiplying two 16 bit numbers requires 4G 32-bit entries (128G transistors!) and multiplying two 32 bit numbers requires 1024E transistors... multiplying 64 bit numbers using a lookup table would require more transistors than there are on the planet (by at least a factor of 1 pentillion based on my napkin calculations...)

If you want to know how processors multiply, several methods are listed here: wikibooks: multiply
Booth's Algorithm
some more are listed here, not all easily applicable to microprocessor design: multiplication algorithms

More (basically the peasant's method in hardware!) binary multiplier

Python:

def rpmul(a, b): 

  return ((a == 1) and b or (a % 2) * b + rpmul(a/2, 2*b))

Ruby:

def rpmul a, b

  (a == 1) ?  b : (a % 2) * b + rpmul(a/2, 2*b)

end

All we need is a SAS submission and this thread will be complete.

Common Lisp

Imperative/iterative and functional solutions. Ain't it nice that Lisp's so versatile? :P

(defun rpm (m n)

  (do ((t1 m (ash t1 -1))

       (t2 n (ash t2 1))

       (r 0 (+ r (* (mod t1 2) t2))))

      ((= t1 0) r)))

(defun rpm-r (m n)

  (labels ((rec (acc m n)

	     (if (= m 0)

		 acc

		 (rec (+ acc (* (mod m 2) n)) (ash m -1) (ash n 1)))))

    (rec 0 m n)))

halber_mensch:

Josh Bohde:

Python 2.6

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

51 characters

I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a.

Yeah, I was saving some characters (at the cost of a lot of memory).

Here's a recursive version that is 48 characters

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

Postscript:
/rmul{0{2 index 0 eq{exit}if exch dup 1 bitshift 4 1 roll 3 -1 roll dup -1 bitshift 5 1 roll 1 and 1 eq {add}{pop}ifelse}loop exch pop exch pop}def

Osno:

All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail.

All the people who don't know what an optimizing compiler is also fail.

Common Lisp:

Shorter version of the recursive implementation:

(defun rpm-r1 (m n &optional (acc 0))

  (if (= m 0)

      acc

      (rpm-r1 (ash m -1) (ash n 1) (+ acc (* (mod m 2) n)))))

public String multiply(int a, int b){
return "Murray is awesome";
}

Damn, you beat me too it. But here you can has lolcode spec 1.2

(Untested)


HAI 1.2
CAN HAS STDIO?

I HAS A X
I HAS A Y
I HAS A MULTIPL
X R NUMBR
Y R NUMBR

VISIBLE "CAN HAS X?:)"
GIMMEH X
VISIBLE "CAN HAS Y?:)"
GIMMEH Y

HOW DUZ I RPM YR X AN YR Y
I HAS A MUTLIPL ITZ 0
I HAS A MODD
I HAS A LOLCAT ITZ MAEK WIN A NUMBR BTW IS DUMMY VARIABLE FOR L00P
IM IN YR RPMLOOP UPPIN YR LOLCAT WILE DIFFRINT X AN 1
X R MAEK QUOSHUNT OF X AN 2 A NUMBR
Y R PRODUKT OF Y AN 2
MODD R MOD X AN 2
BOTH SAEM MODD AN 1, O RLY?
YA RLY, MULTIPL R SUM OF MULTIPL AN Y
NO WAI, BTW NOTHING HAPPENS
OIC
IM OUTTA YR RPMLOOP
FOUND YR MULTIPL
IF U SAY SO

MULTIPL R RPM X Y

VISIBLE "PRODUKT OF " N X N " N " N Y N " IZ " N MULTIPL N ":)"

KTHXBYE

C implementation:

int russian(int a, int b) {int c=0,d=a^b;a*=(a<0)?-1:1;for(a<<=1;(a>>=1)!=0;b<<=1)c+=a&0x1?b:0;return((c^d)<0?-c:c);}

Another python version

def mult(a, b) :

    v = []

    while a != 0 :

        v.append((a % 2 != 0, b))

        print a%2, a, b

        a >>= 1

        b <<= 1

    print reduce(lambda x, y: x+y, [p[1] for p in v if p[0]])

;  6502 Assembler

;  Runs on NES, BBC, C64, Atari 2600 and Apple II :)

;  This is the 16-bit version to handle the example 18x23!



;  $0002 contains unsigned 8-bit operand 1 (not preserved)

;  $0004 contains unsigned 8-bit operand 2 (not preserved)

;  $0001:0000 will contain HI:LO bytes of 16-bit answer



	LDA #0		

	STA $00

	STA $01

	STA $03

 	LDX #0	

loop:

	CPX $04

        BEQ done	

	CLC		

	LSR $04	 	

	BCC skip 	



        CLC		

	LDA $00

	ADC $02

	STA $00

	LDA $01

	ADC $03

	STA $01

skip:

	CLC

	ASL $02

	ROL $03	

	JMP loop	

done:

Josh Bohde:

halber_mensch:

Josh Bohde:

Python 2.6

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

51 characters

I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a.

Yeah, I was saving some characters (at the cost of a lot of memory).

Here's a recursive version that is 48 characters

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

m(-1,2)
....
File "<stdin>", line 1, in <lambda>
File "<stdin>", line 1, in <lambda>
RuntimeError: maximum recursion depth exceeded

=(

package com.timepass;



public class RussianMultiply {



	private int mulTotal = 0;

	RussianMultiply(){

      super();

	}

	private void multiply(int first,int second, boolean isFirstTime){

		if(first == 0 || second ==0){

			return;

		}

		if(isFirstTime && first%2!=0){

			mulTotal = mulTotal + second;

		}

		int tempFirst = first/2;

		int tempSecond = second*2;

		if(tempFirst%2!=0){

			mulTotal = mulTotal + tempSecond;

		}	

		if(tempFirst != 1){

			multiply(tempFirst,tempSecond,false);

		}	

	}

	public void multiply(int first,int second){

		multiply(first,second,true);

	}

	

	public void clearMulTotal(){

		setMulTotal(0);

	}



	public int getMulTotal() {

		return mulTotal;

	}

	public void setMulTotal(int mulTotal) {

		this.mulTotal = mulTotal;

	}

	

	

	/**

	 * @param args

	 */

	public static void main(String[] args) {

		RussianMultiply rm = new RussianMultiply();

		

		rm.clearMulTotal();

		rm.multiply(18, 23);

		System.out.println("Multiplication of 18 and 23:" + rm.getMulTotal());

		

		rm.clearMulTotal();

		rm.multiply(13, 13);

		System.out.println("Multiplication of 13 and 13:" + rm.getMulTotal());



		

		

	}

	 



}

result:
Multiplication of 18 and 23:414
Multiplication of 13 and 13:169

C# using the delightful LINQ to objects

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;



namespace RussianPeasantMultiplication

{

    class Program

    {

        static void Main(string[] args)

        {

            Console.WriteLine("Russian Peasant Multiplication");

            

            Console.Write("Number 1: ");

            int number1 = Convert.ToInt32(Console.ReadLine());

            Console.Write("Number 2: ");

            int number2 = Convert.ToInt32(Console.ReadLine());



            List<Gimley> steps = new List<Gimley>();

            steps.Add(new Gimley(number1, number2));



            Console.WriteLine("Mutiply {0} by {1}", number1, number2);



            while (steps.Last().Left != 1)

            {

                Gimley lastStep = steps.Last();



                int newLeft = lastStep.Left / 2;

                int newRight = lastStep.Right * 2;



                steps.Add(new Gimley(newLeft, newRight));



                Console.WriteLine("Interim step: {0}, {1}", newLeft, newRight);

            }



            // discard even lefts and sum remaining rights

            decimal answer = (from g in steps

                              where g.Left % 2 != 0

                              select g.Right).Sum();



            Console.WriteLine("Answer is: {0}", answer);



            Console.ReadLine();

        }



        class Gimley

        {

            public int Left { get; set; }

            public int Right { get; set; }



            public Gimley(int left, int right)

            {

                Left = left;

                Right = right;

            }

        }

    }

}

Alex thats nice, and very similiar to my ruby/python versions, except where summarization occurs.

I didn't bother with the 3rd acc parameter because
ruby/python don't do tail-end optimization on recursive calls any way.

That's probably why many diss recursive solutions,
but my profiler tells me theres little difference especially if you compare to solutions using python list comprehensions or ruby's .each iteration.

NO U!

#!/usr/bin/env python
import sys

try:
sys.argv[1]
sys.argv[2]
except IndexError:
numbers = raw_input("Please enter the two integers you wish to multiply separated by a space: ").split(' ')
else:
numbers = sys.argv[1:3]

left = int(numbers[0].strip())
right = int(numbers[1].strip())
product = 0


while left != 0:
if left % 2 != 0:
product += right
left /= 2
right*= 2

print "The product of " + numbers[0].strip() + " x " + numbers[1].strip() + " is " + str(product)

Some thoughts...

------------8<-------------------
int mult(int a, int b) {
int result = 0;

while(a) {
if(a & 0x01) {
result += b;
}

a >>= 1;
b <<= 1;
}

return result;
}
------------8<-------------------
int mult2(int a, int b) {
int result = 0;

if(a != 0) {
result = mult2(a >> 1, b << 1);

if(a & 0x01) {
result += b;
}
}

return result;
}

My functional-style java version...

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

    if (a == 0 || b == 0)

        return 0;

    else if (a == 1)

        return b;

    else

        return multiply(a/2, b*2) + ((a % 2 == 1) ? b : 0);

}

All the people who don't know what an optimizing compiler is also fail.

So you're basically agreeing with the " a * b " solution? Because defining multiplication by using multiplication is kind of weird (ok, I agree is in the spec, but anyway).

And no, when you're using rounding in vb.net (or the "\" operator) I can assure you that doesn't get optimized. And C# doesn't get optimized, at least not in IL (but maybe at the JIT level).

http://www.phy6.org/outreach/edu/roman.htm

This is not a Russian method but an ancient Roman one.

#!/usr/bin/perl

use integer;($a,$b)=@ARGV;while($a){$a%2and$r+=$b;$a/=2;$b*=2;}print $r;

I admit that this takes a bit of a shortcut: it checks each pair of numbers as it comes up, and adds the second to the result if necessary at that time, rather than saving them all and waiting for the end.

For anyone who really likes whitespace:

#!/usr/bin/perl

use integer;

($a, $b) = @ARGV;

while ($a) {

  $a % 2 and $r += $b;

  $a /= 2;

  $b *= 2;

}

print $r;

let peasant a b =
let rec peasant a b acc =
if a = 1 then b + acc else
match a%2 with
| 0 -> peasant a/2 b*2 acc
| 1 -> peasant a/2 b*2 acc+b
in peasant a b 0

ruby:

class Fixnum



  def *(num)

    cols = Array.new

    cols.push([self, num])

    while cols.last[0] != 1 do

      cols.push([cols.last[0] / 2, cols.last[1] + cols.last[1]])

    end

    cols.inject(0) { |sum, n| (n[0] % 2 == 1) ? sum + n[1] : sum }

  end

end

Well, that's freakishly easy.

public class RussianPeasantMultiplication {

    public static int multiply(int left, int right) {

        int sum = 0;

        while (left > 0) {

            System.out.println("left=" + left + " right=" + right);

            if ((left & 1) == 1) { // if odd

                sum += right; // collect this row

            }

            left >>= 1; // divide by two

            right <<= 1; // multiply by two

        }

        return sum;

    }



    public static void main(String[] args) {

        int left = Integer.parseInt(args[0]);

        int right = Integer.parseInt(args[1]);

        int result = multiply(left, right);

        System.out.println("result=" + result);

    }

}



left=18 right=23

left=9 right=46

left=4 right=92

left=2 right=184

left=1 right=368

result=414

Here, for the sake of it, is a Sinclair BASIC version.

10 LET a=18: LET b=23

20 LET tot=0

30 IF a<0 THEN LET a=0-a: LET b=0-b

40 IF (a/2) <> INT (a/2) AND a>0 THEN LET tot=tot+b

50 LET a= INT (a/2)

60 LET b=b*2

70 IF a>0 THEN GO TO 40

80 PRINT tot

Is this the first entry to feature line numbers?

An F# quicky:

let rec RussianPeasantMultiplication a b = 

  if a < 0 then -(RussianPeasantMultiplication (-a) b) 

  else (if a % 2 = 1 then b else 0) + (if a > 1 then RussianPeasantMultiplication (a / 2) (b * 2) else 0)

untested Java, quick and dirty...

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

Integer x1 = new Integer(x);
int result = 0;

for(int i = 0; i < Integer.toBinaryString(x1).length(); i++){
if(Integer.toBinaryString(x1).endsWith("1"))
result += y * (int)Math.pow(2, i);
x1 = Integer.rotateRight(x1, 1);
}
return result;
}

Extrapolated from discussion with Josh Bohde:

m=lambda a,b:b*(a&1)+m(a>>1,b<<1) if abs(a)>1 else a*b

55 chars... not as short but handles all integers.

Haskell:

let peasantMultiply a b = f a b 0 

    where f a b s | a < 0 = f (negate a) (negate b) s 

                  | a == 0 = s 

                  | otherwise = 

                       let (a',r) = a `divMod` 2 in 

                       f a' (2*b) (if r == 1 then s + b else s)

Accounts for either argument being zero, also throws an exception if trying to multiply a negative number. Tested with given main() method

    public static long multiply(long first, long second) {

        if(first < 0 || second < 0) {

            throw new IllegalArgumentException("May only multiply positive numbers");

        } else if(first == 0 || second == 0) {

            return 0;

        } else if(first == 1) {

            return second;

        } else if(first % 2 == 1) {

            return second + multiply(first / 2, second * 2);

        } else {

            return multiply(first / 2, second * 2);

        }

    }

    

    public static void main(String[] args) {

        Random r = new Random();

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

            long first = (long)Math.abs(r.nextInt());

            long second = (long)Math.abs(r.nextInt());

            if((first * second) != multiply(first,second)) {

                System.out.println("Failed for " + first + " * " + second + "\t" + (first * second) + "\t" + multiply(first,second));

            }

        }

    }

def russian_mult(l, r):

    """Use Russian-peasant multiplication method.  They don't understand zero

    or negative numbers very well, according to the description.  We fix that 

    with simple rules.  If left side has negative sign, change sign of result.   tdwtf at chad org

    """



    rows = list()

    rows.append((l, r))

    while abs(l) > 1:

        l = l // 2

        r = r * 2

        rows.append((l, r))

        

    if l < 0:

        return 0 - sum(r for l, r in rows if l%2==1)

    else:

        return sum(r for l, r in rows if l%2==1)

So many nice solutions, yet nobody has offered a solution using XSLT yet.

So here is mine. The xsl and xml code can be seen here:
http://damastabrain.mine.nu/RPA/highlight.php
For a better highlight function (at least Firefox), view the xsl itself:
http://damastabrain.mine.nu/RPA/russianPeasantAlgorithm.xsl
And ofcourse to show the outcome:
http://damastabrain.mine.nu/RPA/russianPeasantAlgorithm.xml

Note: it Does work with negative numbers, on either one of the two or both sides. (Integer only)

function russian_multiply_true_lookup (left, right) {



	if (left == 0) return 0;

	if (left == 1) return right;

	

	var lookup = [{left: left, right: right}];



	while (left > 1) {

		left = Math.floor(left / 2);

		right = right * 2;

		lookup.push({left: left, right: right});

	}



	var result = 0;



	for (var index = 0; index < lookup.length; index++)

		if (lookup[index].left % 2 == 1)

			result += lookup[index].right;



	return result;

}

Forget about the sticker, I played a lot with F# today. Thanks for the motivation.

let russianMultiplication x y =

    let rec l a b = seq { yield (a, b); yield! l (a>>>1) (b<<<1) }

    l x y |> Seq.takeWhile (fun c -> fst c > 0) |> Seq.fold (fun acc (x,y) -> 

        if x % 2 = 1 then acc + y else acc

    ) 0

Accounts for 0 and negative numbers, tested with main
//Earlier posted as guest, now posting as member}

package com.timepass;



public class RussianMultiply {



	private int mulTotal = 0;

	private boolean isMulTotalNegative = false;

	RussianMultiply(){

      super();

	}

	private void multiply(int first,int second, boolean isFirstTime){

		// if any number 0 return

		if(first == 0 || second ==0){

			return;

		}

		//check for negative numbers

        if(isFirstTime){



        	if(first < 0 && second < 0) {

        		isMulTotalNegative = false;

        		first = first*-1;

        		second = second * -1;

        	}

        	if(first < 0){

        		isMulTotalNegative = true; first = first*-1;

        	}

        	if(second < 0){

        		isMulTotalNegative = true;second = second * -1;

        	}        	

        }

        // first time and odd number add to total

		if(isFirstTime && first%2!=0){

			mulTotal = mulTotal + second;

		}

		

		// 1st column not even , add to total

		int tempFirst = first/2;

		int tempSecond = second*2;

		if(tempFirst%2!=0){

			mulTotal = mulTotal + tempSecond;

		}

		// first colum not 1, do it again

		if(tempFirst != 1){

			multiply(tempFirst,tempSecond,false);

		}	

	}

	public void multiply(int first,int second){

		multiply(first,second,true);

	}

	

	public void clearMulTotal(){

		setMulTotal(0);

	}



	public int getMulTotal() {

		if(isMulTotalNegative()){

			return -1*this.mulTotal;

		}

		return this.mulTotal;

	}

	public void setMulTotal(int mulTotal) {

		this.mulTotal = mulTotal;

	}

	

	

	/**

	 * @param args

	 */

	public static void main(String[] args) {

		RussianMultiply rm = new RussianMultiply();

		

		rm.clearMulTotal();

		rm.multiply(18, 23);

		System.out.println("Multiplication of 18 and 23:" + rm.getMulTotal());

		

		rm.clearMulTotal();

		rm.multiply(13, 12);

		System.out.println("Multiplication of 13 and 12:" + rm.getMulTotal());

		

		rm.clearMulTotal();

		rm.multiply(12, 12);

		System.out.println("Multiplication of 12 and 12:" + rm.getMulTotal());

		

		rm.clearMulTotal();

		rm.multiply(-12, -12);

		System.out.println("Multiplication of -12 and -12:" + rm.getMulTotal());		



		rm.clearMulTotal();

		rm.multiply(-12, 12);

		System.out.println("Multiplication of -12 and 12:" + rm.getMulTotal());		

		

	}

	public boolean isMulTotalNegative() {

		return isMulTotalNegative;

	}

//	public void setMulTotalNegative(boolean isMulTotalNegative) {

//		this.isMulTotalNegative = isMulTotalNegative;

//	}

	 



}

Multiplication of 18 and 23:414
Multiplication of 13 and 12:156
Multiplication of 12 and 12:144
Multiplication of -12 and -12:144
Multiplication of -12 and 12:-144

Yet another Linq solution:
public static int rpm(int a, int b)
{
return Enumerable.
Range(0, a < 2 ? 1 : (int)Math.Ceiling(Math.Log(a % 2 == 0 ? a + 1 : a, 2)))
.Select(i => new { L = a / (1 << i), R = b * (1 << i) })
.Where(x => x.L % 2 != 0).Sum(x => x.R);
}