• (cs)

    This is my quick hack using VBScript.

    I don't feel it fully implements the algorithm (no "maintaining two columns"), or is as efficient as it could be.... but, it's a start of what your code should NOT end up like...

    Function Mult( a, b ) While a > 1 a = a \ 2 ' Surprise: "" is Int division! b = b * 2
    If a Mod 2 = 1 Then Mult = Mult + b Wend End Function

  • Tim (unregistered) 
    int Multiply(int a, int b)
{
	int c = 0;
	do
	{
		if (a & 1)
			c += b;
		a >>= 1;
		b <<= 1;
	} while (a > 0);
	return c;
}

    Untested, might not work for negative numbers.

  • Tim (unregistered)

    Actually not sure why I did do..while instead of just while... Oh well.

  • Cookie (unregistered)

    Cheeky Java solution..

    private int multiple(int a, int b) {

    int rtn = 0;  
while (a > 0) {

    if (a % 2 != 0) {
        rtn += b;
    }

    a = a / 2;
    b = b * 2;
}

return rtn;

    }

    :-) http://www.supercookie.co.uk

  • Jay (unregistered)

    public static int multiply(int first, int second){ if(first == 1){ return second; }

    int result = 0;

if(first%2 != 0){
	result += second;
}
result += multiply(first/2, second * 2);
return result;

    }

  • (cs)

    And in PHP:

    <?php
	
	function russian($x, $y) {
		$left = array();
		$right = array();
		
		while ($x > 1) {
			$left[] = $x;
			$right[] = $y;
			
			$x = floor($x / 2);
			$y *= 2;
		}
		
		$left[] = $x;
		$right[] = $y;
		$result = 0;
		
		foreach ($left as $index => $x) if ($x % 2) {
			$result += $right[$index];
		}
		
		return $result;
	}
	
	echo russian(41238, 193625);
	
?>
  • The Dopefish (unregistered)

    A recursive C# solution:

        static int Multiply(int a, int b)
    {
        if (a < 2)
            return (a == 1 ? b : 0);
        if (a % 2 == 1)
            return b + Multiply(a / 2, b * 2);
        return Multiply(a / 2, b * 2);
    }
  • ath (unregistered)

    Same thing in python:

    def is_odd(n):
    return (n % 2) != 0

def rmul(x, y):
    s = 0
    while(x != 1):
        if is_odd(x):
            s += y
        x /= 2
        y *= 2
    return y + s
  • (cs)

    Waiting for a solution in brainfuck...

  • mat (unregistered)

    This is my implementation of the algorithm using standard *nix bash script (with the addition of awk):

    #!/bin/bash

    X="$1" Y="$2"

    if [ $X -lt 0 ] then SIGN=-1 X=$(( X * -1 )) else SIGN=1 fi

    LEFT="$X" RIGHT="$Y"

    while [ "$X" -ne 1 ] do X=$(( X / 2 )) Y=$(( Y * 2 )) LEFT="$LEFT $X" RIGHT="$RIGHT $Y" done

    L=echo $LEFT | wc -w RESULT=0 for I in seq 1 $L do X=echo $LEFT | awk "{print $"$I"}" Y=echo $RIGHT | awk "{print $"$I"}" if [ $(( X % 2 )) -ne 0 ] then RESULT=$(( RESULT + Y )) fi done

    RESULT=$(( RESULT * SIGN ))

    echo "$1 x $2 = $RESULT"

  • hydrus (unregistered)

    Obligatory Clojure entry:

    (defn rmult 
  ([x y] (rmult x y 0))
  ([x y p]
     (if (= x 1)
       (+ y p)
       (recur (quot x 2) (* y 2) (if (odd? x) (+ p y) p)))))
  • Dascandy (unregistered)

    X86:

    ; assumption: eax contains arg1, ebx contains arg2
mov edx, eax
next:
shr ebx, 1
cmovc ecx, edx
cmovnc ecx, 0
jz end
lea eax, [eax*2 + ecx]
jmp next

end:
ret

    ARM:

    	mov r2, r0
next    test r1, 1
	mov r1, #0, r1 shr 1
	addc r0, r0, r2
	movz pc, lr
	add r0, r0, r0
	b next

    Both approximated. Appreciate comments.

  • (cs)

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

  • SQLDork (unregistered)

    And a SQL implementation...

    create function wtf.RussianMultiply(@m1 bigint, @m2 bigint) returns bigint as begin declare @out bigint set @out =0 while @m1 > 1 select @m1 = @m1 / 2, @m2 = @m2 * 2, @out = @out + case when @m1 & 1 = 1 then @m2 else 0 end return(@out) end go

  • Z (unregistered)

    function ruM (left, right) { var route = '', remainder = 0; while (left>1) { if (left % 2 != 0) { remainder += right; left -= 1; //route += 'remainder: ' + remainder + '\n'; } left /= 2; right *= 2; //route += left + 'x' + right + '\n'; } return right + remainder; }

  • Erin (unregistered)

    A simpler PHP version:

    <?php function in_mother_russia($x, $y) { $z = 0; while ($x) { if ($x % 2) $z += $y; $x = floor($x / 2); $y *= 2; } return $z; } echo 'In mother Russia, 18 x 23 = '.in_mother_russia(18, 23);
  • Larry H. (unregistered) 
    unsigned russian(unsigned a, unsigned b) 
{ 
   return ((a & 1) ? b : 0) + ((a & ~1) ? russian(a>>1, b<<1) : 0);
}

    Not tested.

  • (cs) in reply to The Wolf

    Not sure why I used that array bullcrap, too used to string manipulation I guess. Here's a better version for PHP:

    <?php
	
	function russian($x, $y) {
		$result = 0;
		
		while ($x > 1) {
			if ($x % 2) $result += $y;
			
			$x = floor($x / 2);
			$y *= 2;
		}
		
		return $y + $result;
	}
	
	echo russian(41238, 193625);
	
?>
  • dv (unregistered)

    using ABAP (only a bit esoteric:-))

    FORM multiply USING   a TYPE I
                      b TYPE I
             CHANGING c TYPE I.
  CLEAR c.
  WHILE a GT 0.
    IF ( a MOD 2 EQ 1 ).
      ADD b TO c.
    ENDIF.
    DIVIDE a BY 2.
    MULTIPLY b BY 2.
  ENDWHILE.
ENDFORM.
  • Paula (unregistered)

    public class Paula extends WTF { public static string Paulabean = "brillant!"; }

  • Mat Rantell (unregistered)

    A short recursive Java version:

    public static long multiply( long left, long right ) { return ( ( left % 2 ) == 0 ? 0 : right + ( left == 1 ? 0 : multiply( left / 2, right * 2 ) ); }

  • Kees (unregistered)

    Function Diederick ( Jan, Piet ) While Jan > 1 Jan = Jan \ 2 Piet = Piet * 2 If Jan Mod 2 = 1 Then Diederick = Diederick + Piet Wend End Function

  • Bosshog (unregistered) 
    	;  6502 Assembler (4-bit operands only)
	;  $0001 should contain operand 1 (not preserved)
	;  $0002 should contain operand 2 (not preserved)

	LDA #0		
 	LDX #0		
loop:	
	CPX $02		
        BEQ done	
	CLC		
	LSR $02	 	
	BCC skip 	
        CLC		
	ADC $01  	
skip:
	ASL $01  	
	JMP loop	

done:
	STA $00
  • ath (unregistered)

    Another Python version. This time it handles zero and negative numbers properly... Floats works as second arg but not as first. Seems like too much work to fix it though...

    def is_odd(n):
    return (n % 2) != 0

def rmul(x, y):
    if(x < 0):
        sgn = -1
        x = -x
    else:
        sgn = 1
        
    s = 0
    while(x >= 1):
        if is_odd(x):
            s += y
        x /= 2
        y *= 2
    return sgn*s
  • Me (unregistered)

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

  • Anonymous (unregistered) in reply to Paula

    Win!

  • (cs)

    In Soviet Russia, peasants multiply you.

  • phihag (unregistered)

    Various iterative solutions in python:

    # python3 only, one-liner!
def mul3(a,b):
	return sum(b << i if (a>>i)&1 else 0 for i in range(a.bit_length()))

def bits(value):
	while value > 0:
		yield value & 1
		value = value // 2

def mul1(a,b):
	res = 0
	for a in bits(a):
		if a:
			res += b
		b *= 2
	
	return res

def mul2(a,b):
	return sum(b << i if abit else 0 for i,abit in enumerate(bits(a)))

try:
	mul = mul3
except AttributeError:
	mul = mul2
  • (cs)

    Ta for the teaser, well back to my reports :(

            static void Main(string[] args)
        {
            Console.WriteLine(RM(18, 23, 0));
            Console.ReadLine();
        }

        public static int RM(int val1, int val2, int rem)
        {
            int mod = val1 % 2;
            int _rem = (mod * val2) + rem;
            int _v1 = val1 / 2;
            int _v2 = val2 * 2;
            if (val1 != 1)
            {
               return RM(_v1, _v2, _rem);
            }
            return _v1 + _rem;
        }

    Addendum (2009-07-22 09:01): Condensed version:

            public static int RM(int val1, int val2, int rem)
        {
            if (val1 != 1)
            {
               return RM((val1 / 2), val2 * 2, ((val1 % 2) * val2) + rem);
            }
            return (val1 / 2) + ((val1 % 2) * val2) + rem;
        }
  • Stefan (unregistered)

    simple c with a little optimization

    unsigned int mul(unsigned int x, unsigned int y)
{
    unsigned int r = 0;
    unsigned int t;   
    if (y > x)
    {
        t = y;
        y = x;
        x = t;
    }
    while(x)
    {
        if (x & 1)
            r += y;
        x >>= 1;
        y <<= 1;
    }
    return r;
}
  • Takis (unregistered)

    VB.Net

    Private Function Russiply(ByVal a As Long, ByVal b As Long) As Long

  Do
    If (a And 1) = 1 Then Russiply += b
    a = a >> 1
    b = b << 1
  Loop Until a <= 1

  If (a And 1) = 1 Then Russiply += b

End Function
  • Zombywuf (unregistered) 
    template<int x, int y, int accum, int mutliple>
struct multiply_ {
  static const int value = multiply_<x / 2, y * 2, accum, (x / 2) & 1>::value;
};

template<int x, int y, int accum>
struct multiply_<x, y, accum, 1> {
  static const int value = multiply_<x / 2, y * 2, accum + y, (x / 2) & 1>::value;
};

template<int y, int accum>
struct multiply_<0, y, accum, 0> {
  static const int value = accum;
};

template<int x, int y>
struct multiply : multiply_<x, y, 0, x & 1> {};
  • KnowOracle (unregistered)

    Oracle SQL version:

    14:55:42 SQL> set echo on
SQL> @russian_mult 18 23
SQL> select sum(b)
  2  from (select floor(a / power(2, rn)) as a,
  3               b * power(2, rn) as b
  4        from (select &1 as a,
  5                     &2 as b,
  6                     rownum as rn
  7              from dual
  8              connect by level < log(2, 18)))
  9  where mod(a, 2) <> 0
 10  /
old   4:       from (select &1 as a,
new   4:       from (select 18 as a,
old   5:                    &2 as b,
new   5:                    23 as b,

    SUM(B)
----------
       414

1 row selected.
  • Captain Obvious (unregistered)

    I haven't done APL in a LONG time...

         Z <- A RUSSIAN B
[1]  Z <- 0
[2] TOP:
[3]  Z <- Z + A * 0 = 2 | B
[4]  A <- |_ A (divide) 2
[5]  B <- B x 2
[6]  -> (A>0) / TOP
  • phihag (unregistered)

    An addition to my solution (see above): The python3 version is not only one line, but only one statement! Is there any other language where you can implement it in one statement without recursion?

  • freakpants (unregistered)

    seems like you killed esolangs :D

  • SR (unregistered) in reply to Alex Papadimoulis

    Bah. Looks like we've bost the esolangs.org server.

    esolangs.org:
    Esolang has a problem

    Sorry! This site is experiencing technical difficulties.

    Try waiting a few minutes and reloading.

    (Can't contact the database server: Can't connect to local MySQL server through socket '/tmp/mysql.sock' (61) (localhost))

    Anyone know if ColdFusion was on there? ;o)

  • KnowOracle (unregistered)

    log(2, 18) should read log (1, &1)

  • Fenris (unregistered)

    Handle Negs

    def mult(a,b): ... neg = (a < 0) ... if neg: ... a *= -1 ... res = 0 ... while a >= 1: ... if a % 2 != 0: ... res += b ... a /= 2 ... b *= 2 ... if neg: ... return res * -1 ... else: ... return res ...

  • KnowOracle (unregistered)

    Correct Oracle SQL

    select sum(b)
from (select floor(a / power(2, rn)) as a,
             b * power(2, rn) as b
      from (select &1 as a,
                   &2 as b,
                   rownum as rn
            from dual
            connect by level < log(2, &1)))
where mod(a, 2) <> 0
/
  • arnemart (unregistered)

    Here's a recursive version in Ruby:

    class Integer
  def russianmultiply num
    return num if self == 1
    return num + (self/2).russianmultiply(num*2) if self%2 == 1
    (self/2).russianmultiply(num*2)
  end
end

puts 18.russianmultiply(23)
  • Herman (unregistered) in reply to Alex Papadimoulis

    As this is the exact implementation of the multiply function on binary computing hardware, a simple

    int Mult(int a, int b)
{
  return a * b;
}

    should do for most platforms :)

  • Matthew Verleger (unregistered)

    int RussianSum( int A, int B ){ return A ? RussianSum(A>>2,B<<2) + (!!(A&1))*(B): 0;
    }

  • (cs)

    Without reading the comments.

    public static int russianMultiplication(int left, int right) {
	int result = 0;
	
	while(left > 1) {
		result += left%2==1?right:0;
		
		left /= 2;
		right *= 2;
	}
	return result + right;
}
  • Mike Dotterer (unregistered)

    A ruby version:

    def russian_peasant_multiply(numerator, denomenator) table = [[numerator, denomenator]] while table.last[0] != 1 (n, d) = table.last table << [n / 2, d * 2] end table.reject { |r| r[0] % 2 != 1 }. inject(0) { |sum, r| sum + r[1]} end

  • gosse (unregistered)

    // todo: implement russian algorithm #define multiply(a, b) ((a)*(b))

  • Will (unregistered)

    Java

    public int mult(int a, int b){ return (b*(a%2)) + (a==1?0:mult(a/2,b*2)); }

  • darkwraith (unregistered)

    My solutions with unit testing goodness:

    #include <iostream>

    using namespace std;

    void assert_equals(unsigned long a, unsigned long b) { if (a != b) { cerr << a << " != " << b << endl; exit(1); } }

    unsigned long russianMult(unsigned a, unsigned b) { unsigned long ret = 0; while (a > 0) { if (a % 2) ret += b; a >>= 1; b <<= 1; } return ret; }

    int main() { assert_equals(414, russianMult(18, 23)); assert_equals(0, russianMult(0, 2)); assert_equals(0, russianMult(2, 0));

    return 0;

    }

  • (cs) in reply to Matthew Verleger
    Matthew Verleger:
    int RussianSum( int A, int B ){ return A ? RussianSum(A>>2,B<<2) + (!!(A&1))*(B): 0; }

    Whoops... Shoulda logged in first. :)

  • Dan (unregistered)

    Non-recursive C#:

    public int PeasantMul(int i, int j) { int accum = 0;

    while (i != 0) { accum += (i / Math.Abs(i)) * ((0 - (i & 1)) & j); i /= 2; j *= 2; }

    return accum; }

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article