Comment On Russian Peasant Multiplication

Is anyone reading this far?

In Perl, implementing the algorithm as described, showing working:

#!/usr/bin/perl -w

use strict;

my $a = shift or die( "need arg 1" );
my $b = shift or die( "need arg 2" );
my $neg = ($a < 0 xor $b < 0) ? -1 : 1;
my @nums;
for ($a = abs $a, $b = abs $b; $a > 0; push(@nums,{'a'=>$a, 'b'=>$b}), $a >>= 1, $b <<= 1) {}
map {print "$_->{'a'} + $_->{'b'}\n" } @nums;
print( "###\n" );
@nums = grep {$_->{'a'} % 2} @nums;
map {print "$_->{'a'} + $_->{'b'}\n" ;$a += $_->{'b'} } @nums;
print( 'sum: ', $a * $neg, "\n" );

A Python solution. It could definitely be done in less code, but I'd rather be able to understand it.

import math



def russian_multiply(x, y):

    cols = [(x, y)]

    

    while True:

        x = int(math.floor(x / 2))

        y = int(math.floor(y * 2))



        cols.append((x, y))



        if x <= 1:

            break



    col_sum = sum([c[1] for c in cols if c[0] % 2 != 0])



    return col_sum



print russian_multiply(18, 23)

Pretty similar in C;

int l(int l1, int ll) { return l1&-2?l1%2*ll+l(l1/2,ll*2):ll; }

Looks kind of like a traffic accident, doesn't it?

I didn't check to see if there was an F# one done yet or not. But here is my attempt.

F# Version 1.9.6.16, compiling for .NET Framework Version v4.0.20506

#light

let isOdd x = 

  (x%2) = 1



let rec mult x y = 

  match x with

  | 1 -> y

  | _ when isOdd x -> y + mult (x/2) (y*2)

  | _ -> mult (x/2) (y*2)

I was disturbed by the fact that the Perl uses the multiplication operator when it doesn't need to, so I offer:

sub rp_mult {

  my ($i, $j) = @_;

  my $r = 0;

  do {

    $r += ($j & 1) && $i;

    $i <<= 1;

    $j >>= 1;

   } while ($i);

   $r;

}

Or, moderately golfed:

sub rpmul{($r,$i,$j)=(0,@_);$r+=$j&1&&$i,$i<<=1,$j>>=1while$i;$r;}

Or, from a slightly different angle:

use List::Util 'sum';

sub rp_mult {

  my ($i, $j) = @_;

  sum map $j >> $_ & 1 && $i << $_,

    0 .. log $j / log 2;

}

python. Gratuitous use of list comprehensions and generators.
Doesn't work for negative numbers. Patches welcome ;-)

a=22

b=66

import math

def half():

    aa=a

    while aa >=1:      

        yield aa

        aa= aa/2 

print sum([y for (x,y) in zip([x for x in half()],[b*(2**(x)) for x in range(0,len([x for x in half()])+1)]) if x%2==1])

fun pmulti 1 r t = t + r
| pmulti l r t = pmulti (l div 2) (r * 2) (t + r * (l mod 2))

pmulti 3 4 0 will give you 3 * 4, t is just an accumulator

In Python:

a,b = 190, 232
if a<0: a=-a; b=-b
print sum([b<<s for s in xrange(0,int(math.log(a,2)+1)) if ((a>>s>0) and ((a>>s)%2)) ])

def rpmult(a, b):

   rows = []

   while a > 1:

      rows.append( (a, b) )

      a, b = a >> 1, b << 1

   rows.append( (a, b) )

   return reduce(lambda (_, b1), (__, b2): b1 + b2, filter(lambda (a, _): a & 1, rows))

(Readable) Ruby version
Handles negative numbers (and unlike some of the examples i read, returns correct signs)

class Rpm

  def self.multiply(x1,x2)

    ret = 0

    is_neg = false



    if x1 < 0

      is_neg = true

      x1 = -x1

    end



    if x2 < 0

      is_neg = !is_neg

      x2 = -x2

    end

  

    return 0 if x1 == 0

    

    begin

      ret += x2 if x1 % 2 != 0

      x1 = (x1 / 2).floor

      x2 = x2 * 2

    end while( x1 >= 1)

    

    ret = -ret if is_neg

    return(ret)

  end

end

For maximum speed, I pre-allocate the tables I use for storage, and avoid all floating-point multiplies and divides. A complete executable program in Lua; run with an argument (any argument) for the peasant-product, without to use the baseline-for-testing "Gold" function.

function Gold(a, b)

	return a * b

end



function DivideByTwo(n)

	local m = n

	while m + m > n do

		m = m - 1

	end

	return m

end



function AllocateTable(a)

	local t = {}

	while a >= 1 do

		a = DivideByTwo(a)

		t[#t + 1] = {}

	end

	return t

end



function AllocateColumnTable(t)

	for i = 1, #t do

		t[i].aColumn = 0

		t[i].bColumn = 0

	end

end



function AllocateValidTable(t)

	for i = 1, #t do

		t[i].truth = false

	end

end



function TestIsOdd(n)

	n = math.abs(n)



	while n > 1 do

		n = n - 2

	end

	

	if n == 0 then

		return false

	elseif n == 1 then

		return true

	else

		print("unknown failure")

		os.exit(-1)

	end

end



function PopulateTable(t, a, b)

	for i = 1, #t do

		local j = i - 1

		local aC, bC = a, b

		while j > 0 do

			if TestIsOdd(aC) then

				aC = DivideByTwo(aC - 1)

			else

				aC = DivideByTwo(aC)

			end

			

			bC = bC + bC

			

			j = math.floor(j - 1)

		end

		

		t[i].aColumn = aC

		t[i].bColumn = bC

	end

end



function CollectValidRows(t, v)

	local n = math.min(#t, #v)

	for i = 1, n do

		if TestIsOdd(t[i].aColumn) then

			v[i].truth = true

		end

	end

end



function SumValidRows(t, v)

	local n = math.min(#t, #v)

	local sum = 0

	for i = 1, n do

		if v[i].truth == true then

			sum = sum + t[i].bColumn

		end

	end

	return sum

end



function PeasantProduct(a, b)

	local columTable = AllocateTable(a)

	local validTable = AllocateTable(a)

	

	AllocateColumnTable(columTable)

	AllocateValidTable(validTable)

	

	PopulateTable(columTable, a, b)

	CollectValidRows(columTable, validTable)

	

	return SumValidRows(columTable, validTable)

end



function DoTest(f)

	-- Generated by fair dice roll. Guaranteed to be random.

	math.randomseed(4)

	

	for n = 1, 1000 do

		local a = math.random(1, 200)

		local b = math.random(1, 200)

		print( string.format("%d * %d = %d", a, b, f(a,b)))

	end

end



local args = {...}



if args[1] then

	print("Peasant")

	DoTest(PeasantProduct)

else

	print("Baseline")

	DoTest(Gold)

end

As a circuit diagram



(Handles 4-bit unsigned integers)

The selection of input wires for AND gates perform the right shifts.
The AND gates perform the oddness test.
The selection of input wires for the adders perform the left shifts.


Addendum (2009-07-22 23:27):
I forgot to mention this was done in MS Paint

Take your pick:

(defun multiply (x y)

  (loop

    with result = 0

    for first = x then (floor first 2)

    for second = y then (* second 2)

    if (oddp first)

    do (incf result second)

    if (= first 1)

    do (return result)))



(defun trmultiply (x y)

  (labels

    ((inner

       (x y acc)

       (if (> x 0)

     (inner (floor x 2)

            (* y 2)

            (if (oddp x) (+ y acc) acc))

     acc)))

    (inner x y 0)))

Speccy basic, recursive:

  10 DEF FN m(a,b)=VAL ((("FN m(

"+STR$ a+"*2,INT ("+STR$ b+"/2))

+("+STR$ b+"-2*INT ("+STR$ b+"/2

))*"+STR$ a) AND b<>1)+(STR$ a A

ND b=1))

Originally I thought about sending 1235th boring C# version or 436th Python version but then I realized that there is no GUI version (except for few PHP or JS versions with HTML WUI [Web User Interface :-) ]). So I created one using my all-time favourite library: Turbo Vision (so it's really TUI and not GUI). Tested with BP7 and recent FreePascal.

program RussianMultiplicationTV;



uses App, Dialogs, Drivers, Menus, MsgBox, Objects, Validate, Views;



const

  cmCalculate = 1001;



type

  TRussMultApp = object(TApplication)

    procedure InitMenuBar; virtual;

    procedure HandleEvent(var Event: TEvent); virtual;

    procedure ExecuteMainDlg;

  end;



  PMainDlg = ^TMainDlg;

  TMainDlg = object(TDialog)

    ResultListBox: PListBox;

    FirstInputLine: PInputLine;

    SecondInputLine: PInputLine;

    constructor Init;

    procedure HandleEvent(var Event: TEvent); virtual;

  end;



function Calculate(x, y: longint): PCollection;

type

  TFormatRec = record

    Line, X, Y, Extra: longint;

  end;

var

  List: PStringCollection;

  TempStr: String;

  FormatRec: TFormatRec;

begin

  New(List, Init(10, 10));

  List^.Insert(NewStr(#0 + 'Step    First   Second    Extra'));

  FormatRec.Line := 1;

  FormatRec.Extra := 0;

  while (x > 0) do begin

    FormatRec.X := x;

    FormatRec.Y := y;

    Inc(FormatRec.Extra, (x mod 2) * y);

    FormatStr(TempStr, '%5d %8d %8d %8d', FormatRec);

    List^.Insert(NewStr(TempStr));

    x := x shr 1;

    y := y shl 1;

    Inc(FormatRec.Line);

  end;

  List^.Insert(NewStr(' ------'));

  Str(FormatRec.Extra, TempStr);

  List^.Insert(NewStr(' Result = ' +  TempStr));

  Calculate := List;

end;



procedure TRussMultApp.ExecuteMainDlg;

var

  Dlg: PMainDlg;

begin

  New(Dlg, Init);

  ExecuteDialog(Dlg, nil);

end;



procedure TMainDlg.HandleEvent(var Event: TEvent);

var

  x, y: longint;

  code: integer;

begin

  inherited HandleEvent(Event);

  if (Event.What = evCommand) and (Event.Command = cmCalculate) then begin

    Val(FirstInputLine^.Data^, x, code);

    if code <> 0 then begin

      MessageBox('Please put valid number into the first input field.', nil,

        mfError or mfOKButton);

      exit;

    end;

    Val(SecondInputLine^.Data^, y, code);

    if code <> 0 then begin

      MessageBox('Please put valid number into the second input field.', nil,

        mfError or mfOKButton);

      exit;

    end;

    ResultListBox^.NewList(Calculate(x, y));

    ClearEvent(Event);

  end;

end;



procedure TRussMultApp.HandleEvent(var Event: TEvent);

begin

  inherited HandleEvent(Event);

  if ((Event.What = evCommand) and (Event.Command = cmNew)) then begin

    ExecuteMainDlg;

    ClearEvent(Event);

  end;

end;



procedure TRussMultApp.InitMenuBar;

var

  R: TRect;

begin

  GetExtent(R);

  R.B.Y := R.A.Y + 1;

  MenuBar := New(PMenuBar, Init(R, NewMenu(

    NewItem('~C~alculator', '', kbNoKey, cmNew, 0,

    NewItem('E~x~it', 'Alt+X', kbAltX, cmQuit, hcExit,

    nil)))));

end;



constructor TMainDlg.Init;

var

  R: TRect;

  ScrollBar: PScrollBar;

  S: String[8];

begin

  R.Assign(0, 0, 60, 20);

  inherited Init(R, 'Russian Multiplication');

  Options := Options or ofCentered;



  R.Assign(2, 2, 12, 3);

  New(FirstInputLine, Init(R, 8));

  FirstInputLine^.SetValidator(New(PRangeValidator, Init(1, 1000)));

  Str(Random(9999) + 1, S);

  FirstInputLine^.SetData(S);

  Insert(FirstInputLine);

  R.Assign(14, 2, 26, 3);

  New(SecondInputLine, Init(R, 8));

  SecondInputLine^.SetValidator(New(PRangeValidator, Init(1, 1000)));

  Str(Random(999) + 1, S);

  SecondInputLine^.SetData(S);

  Insert(SecondInputLine);

  R.Assign(27, 2, 45, 4);

  Insert(New(PButton, Init(R, 'Calculate!', cmCalculate, bfDefault)));

  R.Assign(57, 4, 58, 19);

  New(ScrollBar, Init(R));

  Insert(ScrollBar);

  R.Assign(2, 4, 57, 19);

  New(ResultListBox, Init(R, 1, ScrollBar));

  Insert(ResultListBox);



  { Selects first input box }

  SelectNext(False);

end;



var

  RussMultApp: TRussMultApp;



begin

  Randomize;

  RussMultApp.Init;

  RussMultApp.Run;

  RussMultApp.Done;

end.

Addendum (2009-07-22 21:05):
Download (Source+binaries for DOS and Windows)

#!/usr/bin/env python

def rus_mult(A, B):
if A == 1:
return B
else:
return rus_mult(A / 2, B * 2) + (A % 2) * B

def run_tests():
tests = [(18, 23), (12, 3), (1, 1), (15, 2), (8, 22), (7, 13), (9, 20)]

for (A, B) in tests:
print "Test", A, "*", B, "Result:", rus_mult(A, B) == A * B

if __name__ == "__main__":
run_tests()

C#, handles negative numbers 0, 1.

And, as usual, the most elegant solution is the recursive one.

private int RussianPeasant(int a, int b)

{

    int c;

    if (a < 0)

    {

        a = -a;

        b = -b;

    }

    for (c = (a & 1) * b; (a > 1); c += ((a >>= 1) & 1) * (b <<= 1)) ;

    return c;

}



private int RecursiveRussianPeasant(int a, int b)

{

    if (a < 0)

        return RecursiveRussianPeasant(-a, -b);

    return (a == 0) ? 0 : ((a & 1) * b) + RecursiveRussianPeasant(a >> 1, b << 1);

}

theres some ruby code for you

def rmul(a,b)

  ret = 0

  begin

    ret = (a<0) ? ret-b : ret+b if a%2==1 or a%2==-1

    a = (a<0) ? a/2 + a%2 : a/2

    b = b*2

  end while a != 1 and a != -1 and a != 0 

  ret = (a<0) ? ret-b : ret+b if a%2==1 or a%2==-1

  ret

end



puts rmul(-10,20)

puts rmul(10,20)

puts rmul(-3,500)

puts rmul(1002,343)

Here's one in Motorola 68000 assembly:

.xdef __mulsi3

__mulsi3:

move.l 4(%a7),%d1

move.l 8(%a7),%d2

moveq.l #0,%d0

0:

lsr.l #1,%d1

bcc.s 1f

add.l %d2,%d0

1:

add.l %d2,%d2

tst.l %d1

bne.s 0b

rts

Note that this one is actually useful, it can be used if you don't have a working libgcc for your target. :-) Though that one is faster. ;-)

That said, on CPUs like the Z80 which don't have a native multiplication instruction, Russian Peasant is actually extremely useful.

def Mul(a,b):
return DirectionsFromLeaders( "mul", a, b )


example:

> Mul(3,56)
: Illegal Question, Caller terminated

My Perl-solution with optimization, a bit of math and several tests. It also handles negative numbers.

#/usr/bin/perl

use strict;

use warnings;



if ((@ARGV != 2) || ($ARGV[0]!~m/\d/) || ($ARGV[1]!~m/\d/)) {

	print "Missing or wrong arguments! Need two integers\n";

	exit(0);

}



my ($left,$right)=@ARGV;



if ($right lt $left) {

	my $temp=$right;

	$right=$left;

	$left=$temp;

}



my $negative=1;



if ($left==1) {

	print $right."\n";

	exit(0);

}

elsif ($left==0) {

	print "0\n";

	exit(0);

}

elsif (($left lt 0) && ($right lt 0)) {

	$left*=-1;

	$right*=-1;

}

elsif (($left lt 0) || ($right lt 0)) {

	$left=abs($left);

	$right=abs($right);

	$negative=-1;

}



my $result=0;

for (my $iteration=int(log($left)/log(2));$iteration>=0;$iteration--) {

	if ($left%2!=0) {

		$result+=$right;

	}

	$left=int($left/2);

	$right*=2;

}

print $negative*$result."\n";

ath:

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

Funnily enough, I did the same thing... then realized that is_odd() can be superseded by the simple statement "if (num%2)".
Mine prints output, but it's basically the same. I wasn't aware that Python supported +=, though.

#include <libgen.h>

#include <stdio.h>

#include <stdlib.h>



int main(int argc, char **argv)

{

    int lhs, rhs;

    int res;



    if (argc != 3) {

        printf("usage: %s <lhs> <rhs>\n", basename(argv[0]));

        return (1);

    }



    lhs = atoi(argv[1]);

    rhs = atoi(argv[2]);



    res = 0;

    while (lhs > 1) {

        if (lhs % 2 == 1) {

            res += rhs;

        }

        lhs /= 2;

        rhs *= 2;

    }



    res += rhs;



    printf("result: %d\n", res);



    return (0);

}

In c#

public static int RussianMultiplication(int x, int y)
{
if ((y >> 31 | 1) * y < (x >> 31 | 1) * x)
y = (x + y) - (x = y);

int result = 0;
for (result = 0; x != 0; x /= 2, y >>= 1)
result += ((x >> 31) | 1) * ((0 - (x & 1)) & y);

return result;
}

Handles 0, negatives, and optimizes which digits to place in which column.

And. Fast.


Addendum (2009-07-23 13:39):
Whoops, that should have been:

public static int RussianMultiplication(int x, int y)
{
if ((y >> 31 | 1) * y < (x >> 31 | 1) * x)
y = (x + y) - (x = y);

int result = 0;
for (result = 0; x != 0; x /= 2, y += y)
result += ((x >> 31) | 1) * ((0 - (x & 1)) & y);

return result;
}

Bah, one-liners. I figured I'd write my code in true WTF style.

#!/usr/bin/env python



def mult(a, b):

   d = {a: b}

   if d.keys() == [0] or d.values() == [0]:

       return 0

   if d.keys() < [0]:

       return mult(*(increment(~d.keys()[0]), increment(~d.values()[0])))

   extend(d)

   [d.__delitem__(k) for k in d.keys() if not k&1]

   return sum(d.values())



def extend(d):

   d[min(d.keys())>>1] = (d[min(d.keys())])<<1

   if min(d.keys()) != 1 and min(d.keys()) != 0:

       extend(d)

   return



def increment(x, p=0):

   if x & (1<<p):

       return increment(x^(1<<p), increment(p))

   return x | (1<<p)

Note that I only used arithmetic-related stuff on the lists. Everything else is done bit-wise. See if you can spot the weird abuses and seemingly-random edge cases! (Hint: if there's code that doesn't seem to serve much of a purpose, especially in an if-statement, it's probably deflecting execution around an infinite loop. Either that or I thought it would be funny.)

Addendum (2011-01-30 17:48):
Looking back on this, it turns out I could have made parts of it even worse. The if-statement in extend, for example, could use instead "min(d.keys())&-2" (or ~1, if you like. The values are equivalent)

I think the lesson to take away from this is, if any potential employers decided to see if Google knew about my python experience, this is all a joke.

Two PHP functions in there: the first one does the maths, the second one displays a (very) barren page detailing the steps.

<?php

function motherland($a,$b)

{

  $r=0 ;

  while($a)

  {

    ($a%2) && $r+=$b ;

    $a>>=1 ;

    $b<<=1 ;

  }

  return $r ;

}



function motherland2($a,$b)

{

  $r = 0 ;

  $o = "<table>";

  while($a)   

  {  

    $t = " text-decoration: line-through" ;

    $o .= "<tr style='text-align: right;";   

    ($a % 2) && list($r,$t) = array($r+$b,"") ;

    $o .= "$t'><td>$a</td><td>x</td><td>$b</td></tr>";

    $a >>= 1 ;   

    $b <<= 1 ;

  }

  $o .= "<tr><td></td><td></td><td>$r</td></table>";

  return $o ;

}

echo motherland2(167, 24);

echo motherland(167, 24);

?>

Fun :-)
Syntax highlighting was just ... too much free time ;)

ikegami:

As a circuit diagram



(Handles 4-bit unsigned integers)

The selection of input wires for AND gates perform the right shifts.
The AND gates perform the oddness test.
The selection of input wires for the adders perform the left shifts.

This one rocks! But you need to expand adders as well, either on a separate sheet or the same one. Also show the transistor logic for each AND gate and adders.

$ perl -E'($i,$j)=@ARGV;while($i){($i!=int($i/2)*2||!int($i/2))&&($k+=$j);$j*=2;$i=int($i/2)}say$k' 18 23
414
$

Here's my code in python:

def mul(a,b):

 	m=[(a,b)]

 	while(m[-1][0]<>1):

 		m.append((m[-1][0]/2, m[-1][1]*2))

 	return sum([x[1] for x in m if x[0]%2==1])

I'm a little disappointed that I haven't seen any submissions in the language actually used to perform Important tasks involving numbers: COBOL.

       IDENTIFICATION DIVISION.

       PROGRAM-ID.  RussianPeasantMultiplication.



       DATA DIVISION.

       WORKING-STORAGE SECTION.

       01 FirstNumber    PIC S9(18).

       01 SecondNumber   PIC S9(18).

       01 Result         PIC S9(18) VALUE 0.

       01 ResultFormat   PIC ------------------9.



       PROCEDURE DIVISION.

       MAIN.

           PERFORM DATA-ACQUISITION.

           PERFORM PEASANT-MULTIPLICATION-PROCEDURE.

           STOP RUN.



       DATA-ACQUISITION.

           DISPLAY "First number: " WITH NO ADVANCING.

           ACCEPT FirstNumber.

           DISPLAY "Second number: " WITH NO ADVANCING.

           ACCEPT SecondNumber.

            

       PEASANT-MULTIPLICATION-PROCEDURE.

           IF FirstNumber IS NEGATIVE THEN

               COMPUTE FirstNumber = - FirstNumber

               COMPUTE SecondNumber = - SecondNumber

           END-IF.



           PERFORM UNTIL FirstNumber IS ZERO 

               IF FUNCTION MOD(FirstNumber 2) = 1 THEN

                   ADD SecondNumber TO Result

               END-IF

               DIVIDE FirstNumber BY 2 GIVING FirstNumber

               ADD SecondNumber TO SecondNumber GIVING SecondNumber

           END-PERFORM.



           MOVE Result TO ResultFormat.

           DISPLAY 'Result: ' ResultFormat.

Tested with OpenCobol 1.0.

Or shorter :
$ perl -E'($i,$j)=@ARGV;while($i){($i%2||!$i/2)&&($k+=$j);$j*=2;$i=int($i/2)}say$k' 18 23
414
$

IMO, the peasants aren't actually multiplying and dividing by two, rather, they're doubling and halving numbers, a less generic but far simpler operation, that's why using * and / is cheating.

Anyway, some more Haskell. This one handles negative numbers (don't think any Haskell entry so far does that,) is tail recursive AND uses type classes!

import Data.Bits (shiftL, shiftR, Bits)



rmult :: (Integral a, Bits a) => a -> a -> a

rmult a b | a < 0     = - (rmult (-a) b)

          | a < 0     = - (rmult a (-b))

          | otherwise = go 0 a b where

                go acc 0 b = acc

                go acc a b = go (acc + if odd a then b else 0)

                                (a `shiftR` 1)

                                (b `shiftL` 1)

Oops, that second | a < 0 ... should be | b < 0 ...!

Updated from earlier post that I never bothered to updeate correctly.

done in wonderful VBA, and just like in the article, shows full manual working out table in the debug window. Works with negatives, zeros, hopefully everything really. I stuck to the principle and process of the manual process instead of taking shortcuts.

Public Function RussianMultiply(x As Long, y As Long) As Long

    Dim vals() As Long

    ReDim vals(1 To Round(Sqr(Abs(x)), 0) + 1, 1 To 2) As Long

    Dim i As Long, j As Long, c As Long, Msg As String, s As Long

    s = Sgn(x) * Sgn(y)

    i = 1

    Do Until x = 0

        vals(i, 1) = x

        vals(i, 2) = y

        i = i + 1

        x = x \ 2

        y = y * 2

    Loop

    For j = 1 To i - 1

        If vals(j, 1) / 2 = vals(j, 1) \ 2 Then

            Msg = " X"

        Else

            c = c + (s * Abs(vals(j, 2)))

            Msg = s * Abs(vals(j, 2))

        End If

        Debug.Print vals(j, 1) & vbTab & vals(j, 2) & vbTab & Msg

    Next

    Debug.Print vbCrLf & "=" & vbTab & c

    RussianMultiply = c

End Function

Sample output

>RussianMultiply 18,23



18  23   X

9   46  46

4   92   X

2   184  X

1   368 368



=   414

package test;

import java.util.ArrayList;
import java.util.List;

public class RussianMultiplication {

public RussianMultiplication() {}

public long multiply(long parameter1, long parameter2) {
if (parameter2 < parameter1) {
return handleMultiplication(parameter2, parameter1);
} else {
return handleMultiplication(parameter1, parameter2);
}
}

private long handleMultiplication(long lhs, long rhs) {
List<RussianNumber> numberList = new ArrayList<RussianNumber>();
numberList.add(new RussianNumber(lhs, rhs));
while (lhs > 1) {
lhs = lhs / 2;
rhs = rhs * 2;
numberList.add(new RussianNumber(lhs, rhs));
}
long result = 0;
for (RussianNumber number : numberList) {
if (number.getLhs() % 2 != 0) {
result = result + number.getRhs();
}
}
return result;
}

public static void main(String[] args) {
RussianMultiplication rm = new RussianMultiplication();
long result = rm.multiply(23, 18);
System.out.println("Result: " + result);
}

private class RussianNumber {
private long lhs;
private long rhs;

public RussianNumber(long lhs, long rhs) {
this.lhs = lhs;
this.rhs = rhs;
}

public long getLhs() {
return lhs;
}

public void setLhs(long lhs) {
this.lhs = lhs;
}

public long getRhs() {
return rhs;
}

public void setRhs(long rhs) {
this.rhs = rhs;
}

public String toString() {
return lhs + "::" + rhs;
}
}

}

Another Oracle SQL Example:

SQL> VARIABLE left_num NUMBER

SQL> VARIABLE right_num NUMBER

SQL> BEGIN

   :left_num := 18;

   :right_num := 23;

END;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.06

SQL> SELECT     SUM (DECODE (MOD (TRUNC (:left_num / POWER (2, ROWNUM - 1), 0), 2),

                        1, :right_num * POWER (2, ROWNUM - 1)

                       )

               ) AS RESULT

      FROM DUAL

CONNECT BY TRUNC (:left_num / POWER (2, ROWNUM - 1), 0) > 0



    RESULT

----------

       414





1 row selected.

Elapsed: 00:00:00.06

In Python, aiming for readability.

def russian_peasant(x,y):

    steps=[(x,y)]

    while x>1 or x<-1:

        x/=2

        y*=2

        steps.append((x,y))

    return sum([y for x,y in steps if x % 2 == 1]) * x # * x is there to give the correct sign for the result



# Test it    

print russian_peasant(18,23), 18*23 

print russian_peasant(18,0), 18*0

print russian_peasant(-2,400), -2*400

print russian_peasant(40,-30), 40*-30

print russian_peasant(40,30), 40*30

How about a good dose of OOM?

The code's too long to post here, but beyond this link you can enjoy it in fully highlighted PHP syntax: http://justas.ggcmedia.com/MultiplicationFramework.html (usage example at the end of the file)

Sample output:

Multiplying 18 by 23 Russian peasant style:



Numeric result: 414



Full result:

18 x  23 |   0 +

 9 x  46 |  46 +

 4 x  92 |   0 +

 2 x 184 |   0 +

 1 x 368 | 368 =

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

    Total: 414

...hmm, I need to go clean my hands now.

int mul_rus(int a, int b)
{
int c = 0;

while (a != 1)
{
if (a & 1)
c += b;

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

return b + c;
}

Here's a fairly straightforward implementation in common lisp:

(defun mult (x y)

  (if (= x 1)

    y

    (+ (if (= (rem x 2) 0) 0 y) (mult (floor (/ x 2)) (* y 2)) )

  )

)

It could be all on one line, but that'd be harder to read. If someone has suggestions on how to simplify it, that'd be great. :)

In PDP-8 assembly language. Untested



X, 0
Y, 0
Z, 0

RUSMUL, 0 // entry point
CLA
DCA Z / clear total

LP, TAD X
SNA
JMP DONE

ROR
DCA X
SZL CLA
TAD Y
TAD Z
DCA Z
TAD Y
ROL
DCA Y
JMP LP

DONE, TAD Y
TAD Z
JMP I RUSMUL

Sloppy JS version with animated step-by-step output: http://crindigo.com/stuff/praxis.html

Uses NO math operations, only regex and string operations. Almost all major work is kept in the global $_ variable. Numbers are represented internally using a base-30-like system, then converted directly back to decimal at the end of each operation. Some assumptions about collating sequence were made (e.g. \d == [0-9]).

#!/usr/bin/perl

$_ = join(' ', @ARGV);

m#^\s*-?\d+\s*x\s*-?\d+\s*# or die('Input should be in "#### x ####" format.');

$sign = '+'; while(s#-##) { $sign =~ tr#+-#-+#; }

s#\s##g;

s#$#=0#;

while(!m#^0*x#)

	{

	s#(?<!\d)(\d)#0$1#g;

	if(m#\d+[13579]x#)

		{

		s#(.*x)(.*)(=.*)#$1$2$3+$2#;

		while(m#(.*)(\d)([a-jA-J]?)([a-jA-J]*\+\d*)(\d)(.*)#)

			{

			my($a, $b, $c, $d, $e, $f);

			$a = $1; $b = $2; $c = $3; $d = $4; $e = $5; $f = $6;

			while($e =~ m#[^a0]#)

				{

				$e =~ tr#1-9#a1-8#;

				$b =~ tr#0-9a-jA-I#b-jAb-jA-J#;

				}

			$e =~ tr#0#a#; $b =~ tr#0-9#a-j#;

			$c =~ m#[A-J]# and $b =~ tr#0-9a-jA-J#b-jAb-jA-J#;

			$_ = $a . $b . $c . $d . $e . $f;

			s#=(?!0)#=0#;

			}

		while(m#(.*)(\d)([A-J].*\+)#)

			{

			$x = $2;

			$x =~ tr#0-9#b-jA#;

			$_ = $1 . 0 . $x . $3;

			}

		tr#a-jA-J#0-90-9#;

		s#\+.*##;

		}

	if(m#^(\d)(.*)#)

		{

		$x = $1;

		$x =~ tr#0-9#aAbBcCdDeE#;

		$_ = $x . $2;

		}

	while(m#^([A-Ja-j]*?)([A-Ja-j]?)(\d)(.*)#)

		{

		my($a, $b, $c, $d);

		$a = $1; $b = $2; $c = $3; $d = $4;

		$b =~ m#[a-j]# and $c =~ tr#0-9#aAbBcCdDeE#

			or $c =~ tr#0-9#fFgGhHiIjJ#;

		$_ = $a . $b . $c . $d;

		}

	tr#A-Ja-j#0-90-9#;

	if(m#^(.*)(\d)(=.*)#)

		{

		$x = $2;

		$x =~ tr#0-9#acegiACEGI#;

		$_ = $1 . $x . $3;

		}

	while(m#(.*?)(\d)([A-Ja-j]?)([A-Ja-j]*=.*)#)

		{

		my($a, $b, $c, $d);

		$a = $1; $b = $2; $c = $3; $d = $4;

		$c =~ m#[a-j]# and $b =~ tr#0-9#acegiACEGI#

			or $b =~ tr#0-9#bdfhjBDFHJ#;

		$_ = $a . $b . $c . $d;

		}

	tr#A-Ja-j#0-90-9#;

	s#(?<!\d)0+(?=\d|0(?!\d))##g;

	}

s#.*=##;

s#^#$sign#;

s#^\+##;

s#$#\n#;

print;

--SQL Server using Common Table Expression

DECLARE @number1 int;
DECLARE @number2 int;

SET @number1 = 18;
SET @number2 = 23;

WITH Multiplication (Row, Factor1, Factor2) AS
(
SELECT 1, @number1, @number2
UNION ALL
SELECT Row + 1, Factor1 / 2, Factor2 * 2
FROM Multiplication
WHERE Factor1 > 1
)
SELECT SUM(Factor2) FROM Multiplication
WHERE Factor1 % 2 = 1;

func(a, b):
if(a == 1)
return b
if(a%2 == 1)
return b*2 + func(a/2, b*2)
else
return func(a/2, b*2)

Had to do it with recursion. I can't think of a reason why not to do it that way. I also haven't looked at the comments. Someone probably came up with this solution or it has already been shown to be wrong. I could also shrink it to be a single line but then it wouldn't be nearly as readable.

--It works better as a stored procedure

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
-- =============================================
-- Author: Paul N
-- Create date: 7/22/2009
-- Description: multiplies two numbers using
-- Russian Peasant Multiplication
-- =============================================
CREATE PROCEDURE dbo.[Russian Peasant Multiplication]
-- Add the parameters for the stored procedure here
@number1 int,
@number2 int
AS
BEGIN
-- SET NOCOUNT ON added to prevent extra result sets from
-- interfering with SELECT statements.
SET NOCOUNT ON;

-- Insert statements for procedure here
WITH Multiplication (Row, Factor1, Factor2) AS
(
SELECT 1, @number1, @number2
UNION ALL
SELECT Row + 1, Factor1 / 2, Factor2 * 2
FROM Multiplication
WHERE Factor1 > 1
)
SELECT SUM(Factor2) FROM Multiplication
WHERE Factor1 % 2 = 1;
END
GO

open List

let oddcar (n, _) = (n land 1) = 1
let sum = fold_left (+) 0

let rec do_mul = function
| (x,_) :: _ as lst when x == 1 ->
sum (map snd (filter oddcar lst))
| (x,y) :: _ as lst ->
do_mul ((x / 2, y * 2) :: lst)

let mul x y =
do_mul [x,y]

C# + LINQ

int Multiply(int x, int y)

{

	return Enumerable.Range(0, (int)(1.0 + Math.Log(x)/Math.Log(2)))

		.Select(i => new {x = x >> i, y = y << i})

		.Where(p => p.x > 0 && p.x % 2 == 1)

		.Sum(p => p.y);	

}

Addendum (2009-07-23 01:23):
More LINQ-ish:

int Multiply(int x, int y)

{

	return (

		from i in Enumerable.Range(0, (int)(1.0 + Math.Log(x)/Math.Log(2)))	

		where (x >> i) % 2 == 1

		select y << i

	).Sum();	

}

simple erlang:

-module(rmult).

-export([rmult/2]).



rmult(M1, M2) -> rmult(M1, M2, [{M1, M2}]).



rmult(1, _, P) -> rsum(P, 0); 

rmult(M1, M2, P) ->

  M1n = M1 div 2, M2n = M2 * 2,

  rmult(M1n, M2n, [{M1n, M2n} | P]).



rsum([], S) -> S;

rsum([{M, _} | P], S) ->

  rsum(P, S + case M rem 2 of 0 -> 0; 1 -> M end).

; Rabbit 2000 assembler

; Inputs in A, B

; Result in HL



    	ld d, 0

    	ld e, b 		;; DE = second operand

    	ld hl, 0		;; accum = 0

    	or a

    	;; For the first iteration, we need to just test whether the second

    	;; operand is even, rather than using a side effect of the rotate

    	bit 0, a

..mul_loop:

    	jr nc, ..odd

    	add hl, de

..odd:

    	or a			;; CF = 0

    	jr z, ..done	;; A = 0?

    	rl de			;; DE *= 2

    	rr a			;; A /= 2. CF can't be nonzero as that would imply overflow

    	jr ..mul_loop	;; CF from A is used on next iteration

..done:

    	;; result in HL