Comment On Russian Peasant Multiplication

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

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.

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

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

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

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

	

?>

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

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

Waiting for a solution in brainfuck...

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"

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

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.

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

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

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

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

unsigned russian(unsigned a, unsigned b) 

{ 

   return ((a & 1) ? b : 0) + ((a & ~1) ? russian(a>>1, b<<1) : 0);

}

Not tested.

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

	

?>

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.

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

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

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

	;  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

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 

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

Win!

In Soviet Russia, peasants multiply you.

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

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;

        }

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;

}

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

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

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.

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

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?

seems like you killed esolangs :D

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)

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

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

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

/

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)

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 :)

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

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;

}

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

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

Java

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

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

Matthew Verleger:

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

Whoops... Shoulda logged in first. :)

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