• (cs)

    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
  • Quxxy (unregistered)

    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);
}
  • f3nd3r (unregistered) in reply to The Wolf

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

  • Amadan (unregistered)

    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
  • Northpole (unregistered)

    Ruby, one line, non-recursive:

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

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

  • (cs)

    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)
  • (cs) in reply to Josh Bohde
    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.

  • (cs)

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

  • Floyd (unregistered) 
    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 };
            }
        }
    }
}
  • Alex Guzman (unregistered) 
            int first = 18;
        int second = 23;

        int result = 0;

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

            if (first % 2 != 0)
                result += second;
        }
  • (cs) in reply to Rootbeer
    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

  • Jürgen (unregistered)

    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
  • Bryan (unregistered)

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

  • Alex Muscar (unregistered)

    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)))
  • Josh Bohde (unregistered) in reply to halber_mensch
    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
  • Sal (unregistered)

    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

  • AdT (unregistered) in reply to Osno
    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.

  • Alex Muscar (unregistered)

    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)))))
  • Murray (unregistered)

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

  • PopeHappyCat (unregistered) in reply to JaguarOne

    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

  • Fooba (unregistered)

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

  • (cs)

    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]])
  • Bosshog (unregistered) 
    
;  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:
  • (cs) in reply to Josh Bohde
    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

    =(

  • Timepass (unregistered) 
    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

  • (cs)

    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;
            }
        }
    }
}
  • Jürgen (unregistered) in reply to Alex Muscar

    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.

  • Anonymous (unregistered) in reply to PopeHappyCat

    NO U!

  • Rob W. (unregistered)

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

  • serg (unregistered)

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

  • Jannik Jochem (unregistered)

    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);
}
  • Osno (unregistered) in reply to AdT
    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).

  • wolf550e (unregistered)

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

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

  • (cs) 
    #!/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;
  • SimonY (unregistered)

    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 b2 acc | 1 -> peasant a/2 b2 acc+b in peasant a b 0

  • Dave Havlicek (unregistered)

    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
  • (cs)

    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

  • JoLoCo (unregistered)

    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?

  • Patrick Simpson (unregistered)

    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)
  • idle (unregistered)

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

  • (cs)

    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.

  • Noah Easterly (unregistered)

    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)
  • klagdon (unregistered)

    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));
            }
        }
    }
  • Chad M (unregistered) 
    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)
  • Dave van der Brugge (unregistered)

    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)

  • jjs105 (unregistered) 
    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;
}
  • (cs)

    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
  • (cs)

    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

  • Codism (unregistered)

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

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #278079:

Log Out

« Return to Article