Comment On Russian Peasant Multiplication

Ever since the first OMGWTF Programming Contest, I've always wanted to bring back some element of "coding challenges" to the site. Ideally, this would be in the form of a second contest... but considering that contests require a ton of work, and the fact that interns around town have come to learn that interning at Inedo basically mean means shipping mugs, mailing stickers, testing contest entries, and acting as human ottomans, we'll have to go with something a bit scaled back. And that's where Programming Praxis will come in. [expand full text]
« PrevPage 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9 | Page 10 | Page 11 | Page 12 | Page 13 | Page 14 | Page 15 | Page 16Next »

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:59 • by qoo3h (unregistered)
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" );

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:03 • by Lee Crabtree (unregistered)
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)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:04 • by J.I. (unregistered)
278356 in reply to 277798
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?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:09 • by ajp
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)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:10 • by Andrew Rodland (unregistered)
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;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:11 • by sdeek (unregistered)
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])

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:13 • by Michael Clark (mjac.co.uk) (unregistered)
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:15 • by opussf (unregistered)
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)) ])

Python Solution with some lambda

2009-07-22 17:25 • by KukkerMan (unregistered)

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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:26 • by Jimmy Selgen (unregistered)
(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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:29 • by Tiogshi (unregistered)
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:31 • by 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.


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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:31 • by Eric (unregistered)
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)))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:31 • by Yorick (unregistered)
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))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:35 • by mol1111
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)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:36 • by Edinburgh Mike (unregistered)
#!/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()

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:42 • by Lernin ur codez (unregistered)
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);
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:47 • by Redredredredredred (unregistered)
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)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:48 • by Kevin Kofler (unregistered)
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:52 • by Rasmus (unregistered)
def Mul(a,b):
return DirectionsFromLeaders( "mul", a, b )


example:

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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:58 • by H2 (unregistered)
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";

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:59 • by Ben (unregistered)
278389 in reply to 277789
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:07 • by Sam (unregistered)

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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:08 • by PatrickBeebe
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;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:11 • by mwchase
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:11 • by LeCoyote
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 ;)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:17 • by AshG (unregistered)
278398 in reply to 278370
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:24 • by Florent (unregistered)
$ 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
$

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:29 • by Adrian (unregistered)
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])

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:34 • by dee
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:35 • by Florent (unregistered)
278404 in reply to 278401
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
$

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:37 • by valderman (unregistered)
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)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:38 • by valderman (unregistered)
278406 in reply to 278405
Oops, that second | a < 0 ... should be | b < 0 ...!

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:47 • by RayS
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:55 • by Fred Dagg (unregistered)
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;
}
}

}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:55 • by DFHawthorne
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:00 • by Jukka (unregistered)
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:04 • by mjomble
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:14 • by spiderlama (unregistered)
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;
}

clisp implementation

2009-07-22 19:23 • by unit3 (unregistered)
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. :)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:24 • by Gumpy Guss (unregistered)
278418 in reply to 278416
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:29 • by Crindigo (unregistered)
Sloppy JS version with animated step-by-step output: http://crindigo.com/stuff/praxis.html

Final "No Math" Perl Version

2009-07-22 19:30 • by Warr (unregistered)
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;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:48 • by Paul N (unregistered)
--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;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:53 • by Wheaties (unregistered)
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:56 • by Paul N (unregistered)
--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

ocaml version

2009-07-22 19:59 • by yowzer (unregistered)
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]

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:12 • by Veryth
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();
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:12 • by Mike McNally (unregistered)
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).

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:19 • by bd_ (unregistered)
; 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
« PrevPage 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9 | Page 10 | Page 11 | Page 12 | Page 13 | Page 14 | Page 15 | Page 16Next »

Add Comment