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 14:43 • by samanddeanus
Scheme with fold and unfold:

(define (mul a b)
(fold +
0
(unfold (lambda (x)
(zero? (car x)))
(lambda (x)
(if (odd? (car x))
(cdr x)
0))
(lambda (x)
(cons (quotient (car x) 2)
(+ (cdr x) (cdr x))))
(cons (abs a)
(if (negative? a)
(- b)
b)))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 14:43 • by Maks Verver (unregistered)
278272 in reply to 278262
moltonel:
#!/bin/sh
grep -q '^1\*' <<< $1 && echo $(( $1 )) || $0 "$(( $(sed 's/\*.*//' <<< $1)/2 ))*$(( $(sed 's/.*\*//;s/+.*//' <<< $1)*2 ))$(grep -oE '[13579]\*[0-9]+' <<< $1| sed 's/.*\*/+/')$(grep -o '\+.*' <<< $1)"

I can't get this to work properly. With BSD sh it doesn't parse, with Bash it runs, but produces incorrect answers for the simplest arguments (and when the first argument is 1, it doesn't produce a result at all).

Any explanation? Maybe some of the code got mangled while posting, or you're using yet a different shell?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 14:45 • by Ingo (unregistered)
278275 in reply to 277848
I can beat that...

int RussianPeasantMultiplyFor18And23( )
{
return 414;
}

OMG.. my code is fastest?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 14:51 • by moltonel
278282 in reply to 278272
Maks Verver:
moltonel:
#!/bin/sh
grep -q '^1\*' <<< $1 && echo $(( $1 )) || $0 "$(( $(sed 's/\*.*//' <<< $1)/2 ))*$(( $(sed 's/.*\*//;s/+.*//' <<< $1)*2 ))$(grep -oE '[13579]\*[0-9]+' <<< $1| sed 's/.*\*/+/')$(grep -o '\+.*' <<< $1)"

I can't get this to work properly. With BSD sh it doesn't parse, with Bash it runs, but produces incorrect answers for the simplest arguments (and when the first argument is 1, it doesn't produce a result at all).

Any explanation? Maybe some of the code got mangled while posting, or you're using yet a different shell?


Yes, bash, sorry.
You'll have to give it two numbers, without space, and the multiplication sign must be an actual '*'.

eg:
$ ./russian.sh 19*29
551
$ ./russian.sh 18*23
414

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 14:51 • by newlisp.org (unregistered)
278283 in reply to 277861
improvement for some problems starting with even number:


(define (rmul x y , (s 0))
(until (= x 1)
(unless (zero? (% x 2))
(inc s y))
(setq x (>> x) y (<< y)))
(+ y s)
)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 14:52 • by MG (unregistered)
Why recurse when you can use a linked list?


#include <stdio.h>
#include <stdlib.h>

struct rus_row {
long left;
long right;
struct rus_row *next;
};
int main(int, char **);
long rus_multiply(long, long, int);
struct rus_row *make_row(long, long, struct rus_row *);
void rus_freemem(struct rus_row *);

int main(int argc, char *argv[]) {
if (argc != 3) {
printf("Usage: %s <num> <num>\n", argv[0]);
exit(1);
}
long a = atol(argv[1]);
long b = atol(argv[2]);
long result = rus_multiply(a, b, 1);
return 0;
}

long rus_multiply(long a, long b, int print) {
long total = 0;

struct rus_row *head = make_row(a, b, NULL);
struct rus_row *tail = head;
while(tail->left > 1) {
struct rus_row *new_row = make_row(tail->left / 2, tail->right * 2, NULL);
tail->next = new_row;
tail = tail->next;
}
struct rus_row *curr = head;
while (curr) {
if (curr->left & 1) {
// odd
if (print) {
printf ("%ld\t%ld\t+ %ld\n", curr->left, curr->right, curr->right);
}
total = total + curr->right;

} else {
// even
if (print) {
printf ("%ld\t%ld\n", curr->left, curr->right);
}
}
curr = curr->next;
}
if (print) {
printf ("\t\t-----\n\t\t= %ld\n", total);
}
rus_freemem(head);
return total;
}

struct rus_row *make_row(long left, long right, struct rus_row *next) {
struct rus_row *row = (struct rus_row *) malloc(sizeof(struct rus_row)); //todo: check for malloc failure
row->left = left;
row->right = right;
row->next = next;
return row;
}

void rus_freemem(struct rus_row *head) {
struct rus_row *next = head;
while (next) {
struct rus_row *curr = next;
next = curr->next;
free(curr);
}
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 14:56 • by Will (unregistered)
Nice callback to the futility closet article from last week. It is interesting to see how many different languages / methods people found for executing this procedure.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 14:59 • by blueberry (unregistered)
Here is my solution in C#:


static int PeasantMult(int x, int y)
{
switch (x)
{
case -1: return -y;
case 0: return 0;
case 1: return y;
default: return PeasantMult(x % 2, y) + PeasantMult(x / 2, y + y);
}
}


-Works with negative values on any or both operands
-No multiplication

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:00 • by Alan Woodland (unregistered)
278287 in reply to 278284
MG:
Why recurse when you can use a linked list?


You could always recurse over linked lists and get the best of both worlds :P

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:03 • by Osno (unregistered)
I think everybody misrepresented my comment on using multiplication/division instead of bitshifting being fail as a performance comment. What I was aiming at is that if you're defining multiplication, multiplying is kind of lame. Then, I changed my mind and started using ( left & 1 ) * right, but that was just a shortcut :). Also, bitshifting was closer to the original demonstration in the "spec".

I agree with all that multiplying here is safer and probably close in performance. I doubt most of the compilers present (python, java, c#, vb.net, javascript, etc) will optimize it to the same thing, but who cares? (btw, I do think C, C++, Delphi, Scheme, Haskell and a few others may optimize).

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:05 • by Osno (unregistered)
Google Search (by far the most commonly used programming language):

http://lmgtfy.com/?q=russian+peasant+multiplication

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:07 • by VirtualBlackFox (unregistered)
C#, just for fun :

namespace Test

{
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
class Elem
{
public int Left { get; set; }
public int Right { get; set; }
}

static IEnumerable<Elem> DivideUntilOneOnLeft(Elem e)
{
while (e.Left != 1)
{
e = new Elem() { Left = e.Left / 2, Right = e.Right * 2 };
yield return e;
}
}

static int Mutiply(int left, int right)
{
return DivideUntilOneOnLeft(new Elem() { Left = left, Right = right })
.Where(e => e.Left % 2 != 0)
.Aggregate(0, (accum, e) => accum + e.Right);
}

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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:08 • by nine (unregistered)
C# Recursive solution. Handles edge cases (negative integers, 0). Focus is on readability/clarity and not performance:

public static int RussianMultiply(int x, int y)
{
if (x < 0) return RussianMultiply(-x, -y);
else if (x == 0) return 0;
else if (x == 1) return y;
else if (x % 2 == 1) return y + RussianMultiply(x/2, y*2);
else return RussianMultiply(x/2, y*2);
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:09 • by Scott (unregistered)
Here is an interesting javascript version

function russia(a,b){ return new (function(){
while(a&1?((this.c?this.c+=b:this.c=b),a=a>>1,b=b<<1,(a==0?false:true)):(a=a>>1,b=b<<1,true)){};
})().c;}


The reason for the anonymous function is because of a variable scope issue that occurs when the function is called multiple times.

Matlab

2009-07-22 15:18 • by darkscout (unregistered)
function [c] = rpm(a,b)

while (a(end)~=1)
a(end+1)=floor(a(end)/2);
b(end+1)=b(end)*2;
end
c=sum(b(logical(mod(a,2))));

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:19 • by ikorb (unregistered)
Yet another Haskell version. Distinguishing features: No indented lines, overly verbose

peasant_step :: (Int, Int) -> (Int, Int)
peasant_step (x,y) = (div x 2, y + y)

first_is_positive :: (Int, Int) -> Bool
first_is_positive (x,y) = x > 0

peasant_list :: (Int, Int) -> [(Int, Int)]
peasant_list args = takeWhile first_is_positive $ iterate peasant_step args

first_is_odd :: (Int, Int) -> Bool
first_is_odd (x,y) = (mod x 2) == 1

peasant_filter :: [(Int, Int)] -> [(Int, Int)]
peasant_filter = filter first_is_odd

accumulate_second :: (Int, Int) -> Int -> Int
accumulate_second (x,y) a = y + a

peasant_sum :: [(Int, Int)] -> Int
peasant_sum = foldr accumulate_second 0

peasant_multiply :: Int -> Int -> Int
peasant_multiply x y = peasant_sum $ peasant_filter $ peasant_list (x,y)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:23 • by treyb (unregistered)
In excel:

Column A:
A1: number_1
A2: =rounddown(A1/2,0)
A3: =rounddown(A2/2,0)
A4: and so on

Column B:
B1: number_2
B2: =if(A2,B1*2,0)
B3: =if(A3,B2*2,0)
B4: and so on

Column C:
C1: =if(mod(A1,2)=0,0,1)
C2: =if(mod(A2,2)=0,0,1)
C3: and so on

Column D:
D1: =sumproduct(B:B,C:C)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:26 • by iMalc (unregistered)
Anyone done is using a .BAT script yet?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:27 • by TNProgrammer (unregistered)
//C#
public static void Go()
{
Console.WriteLine(PraxisMultiply(18, 23).ToString());
}

public static int PraxisMultiply(int number1, int number2)
{
List<PraxisPair> pairs = new List<PraxisPair>();
pairs.Add(new PraxisPair(number1, number2));
while(number1 > 1)
{
number1 = number1 / 2;
number2 = number2 * 2;
pairs.Add(new PraxisPair(number1, number2));
}
int result = 0;
foreach(PraxisPair p in pairs)
{
if(p.Left % 2 == 0)
{
p.Right = 0;
}
result += p.Right;
}
return result;
}

public class PraxisPair
{

public PraxisPair(int left, int right)
{
Left = left;
Right = right;
}


public int Left{ get; set; }
public int Right{ get; set; }
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:28 • by Josue Chi (unregistered)
Short as can be

public static int russian(int multiplier1, int multiplier2) {
int result = 0;
while (multiplier1 >= 1) {
result += (multiplier1 % 2 == 1)? multiplier2: 0;
multiplier2 *= 2;
multiplier1 /= 2;
}
return result;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:32 • by SoaperGEM (unregistered)
I'm not going to read through all the 400+ comments to see if this exact version's been done yet, but here's an implementation in Python:

def multtwo(one, two):

result = 0
while (one >= 1):
if (one & 1):
result += two
one >>= 1
two <<= 1
return result


I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad. Don't they teach kids anything about bitwise operators anymore?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:35 • by blueberry (unregistered)
278307 in reply to 278305
SoaperGEM:

I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad. Don't they teach kids anything about bitwise operators anymore?


See post #278250
Maybe it's time to go back to school :P

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:51 • by asdfghj (unregistered)
recursive scheme solution:

(define (russian_m a b) (if (= b 1)
a
(russian a b)
)
)

(define (russian a b)
(if (= a 1)
b
(+
(if (= (remainder a 2) 0) 0 b)
(russian (/ a 2) (* b 2))
)
)
)

not tested

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:52 • by Josue Chi (unregistered)
278313 in reply to 278307
blueberry:
SoaperGEM:

I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad. Don't they teach kids anything about bitwise operators anymore?


See post #278250
Maybe it's time to go back to school :P


As long as we don't multiply directly A * B, we are not violating any of the "original requirements". Of course using bit shifting can give you points, if we were at school (and may give you points here too :), but if it is not part of the requirements, I don't think we should feel forced to use it.

Cheers and good luck (I want my Sticker!)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:54 • by Alvie (unregistered)
278314 in reply to 277827
You win so far :) As long as that works, obviously.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:57 • by guille_ (unregistered)

(defun rmul (x y)
(let ((l (truncate x 2))
(r (* y 2)))
(reduce '+ (do ((sums '())
(l l (truncate l 2))
(r r (* r 2)))
((< l 1) sums)
(when (oddp l)
(push r sums))))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:57 • by ZzzZZZz (unregistered)
Recursive Python. Pretty disappointed with my work after seeing some of the others!

def peasant(x, y): 

n = 1
m = n
while (n < y):
m = n
n = n * 2
out = m * x
d = y - m
if (d == 0):
return out
else:
return peasant(x, d) + out

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 15:58 • by Beat by the system (unregistered)
anyone done this in javascript?
function multiply (x, y, total)
{
(x == 0) ? alert(total) : multiply (Math.floor(x/2),Math.floor(y*2),(x % 2 == 0) ? total : total+y);
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:00 • by Resistance
In spite of being epic late, here's mine:

#include <stdio.h>

int main() {
int a;
int b;
int c;

printf("A = ");
scanf("%d", &a);
printf("B = ");
scanf("%d", &b);

asm(
"movl $0, %%ecx\n\t"
"loop:\n\t"
"shrl $1, %%eax\n\t" // divide left side by 2
"jnc skip_add\n\t" // carry is set if eax was odd
"addl %%ebx, %%ecx\n\t" // accumulate right side
"skip_add:\n\t"
"shll $1, %%ebx\n\t" // multiply right side by 2
"cmpl $0, %%eax\n\t"
"jne loop" // equal if left side was 1
: "=c" (c) // out: ecx - result
: "a" (a), "b" (b) // in: eax - left side, ebx - right side
);

printf("A * B = %d\n", c);

return 0;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:01 • by Dave Havlicek (unregistered)
how about PL/pgSQL?

DECLARE

tmp1 INTEGER;
tmp2 INTEGER;
BEGIN
CREATE TEMPORARY TABLE tmp_columns ( "left_col" INTEGER NOT NULL, "right_col" INTEGER NOT NULL );
tmp1 := $1;
tmp2 := $2;
INSERT INTO tmp_columns (left_col, right_col) VALUES (tmp1, tmp2);
WHILE tmp1 != 1 LOOP
tmp1 := tmp1 / 2;
tmp2 := tmp2 + tmp2;
INSERT INTO tmp_columns (left_col, right_col) VALUES (tmp1, tmp2);
END LOOP;
return ( SELECT SUM(right_col) FROM tmp_columns WHERE (left_col % 2) = 1 );
END

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:02 • by dontera

private static int CalculateLikeRussianPeasant(int a, int b, List<int[]> lines)
{
if (lines == null)
{
lines = new List<int[]>();
int[] lr = new int[2];
lr[0] = a;
lr[1] = b;
lines.Add(lr);
CalculateLikeRussianPeasant(-1, -1, lines);
}

int[] lastLr = lines[lines.Count - 1];
if (lastLr[0] != 1)
{
int[] lr = new int[2];
lr[0] = lastLr[0] / 2;
lr[1] = lastLr[1] * 2;
lines.Add(lr);
if (lr[0] != 1)
CalculateLikeRussianPeasant(-1, -1, lines);
}

int result = 0;
lines.ForEach(delegate(int[] lr)
{
if (lr[0] % 2 != 0)
result += lr[1];
});

return result;
}


call into it with CalculateLikeRussianPeasant(101, 202, null);

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:05 • by AshG (unregistered)
I'm at the end of the third page of comments and have yet to see an Objective C solution.

What, no Apple/iPhone developers here? WTF?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:11 • by The Answer + 2 (unregistered)
278328 in reply to 278017
C# (assumes a,b,c are defined and assigned elsewhere)

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

44 characters

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:15 • by Rob Hulswit (unregistered)
Arrgh, some challenges are just too challenging...
35 characters, freestanding, no need to declare and assign delegates ;-)

C++, supports negative (at least the C++ dialect of Borland C++ Builder 5, the sign of (negative number % another number) is implementation defined in C++... sigh).
int r=0;for(;b;r+=b%2*c;b/=2;c*=2;}

Or a recursive version in 42 characters:
int a(b,c){return b?a(b/2,c*2)+(b%2)*c:0;}

C++ template meta programming:
template <int b, int c>
struct r
{
static const int s = b?r<b/2,c*2>::s+b%2*c:0;
};

Javascript 35 characters (works in firefox 3.0.11 and IE6). Damn, difficult to do integer division by 2 that also works good for negative numbers.
for(r=0;b/=2;b-=d=b%1,r+=d*(c*=2));

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:21 • by Rob Hulswit (unregistered)
278331 in reply to 278329
Oops, copy-paste for the fail.

Real C++ version:
int r=0;for(;b;r+=b%2*c,b/=2,c*=2);

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:25 • by Unlabeled Meat (unregistered)
Shifty recursive Scala


def rusMult(x: Int, y: Int): Int =
rusMult(x, y, 0)

def rusMult(x: Int, y: Int, sum: Int): Int =
if ((x == 0) || (y == 0)) 0
else
x match {
case 1 =>
sum + y
case _ =>
rusMult(x >> 1, y << 1, (if (x % 2 == 0) sum else sum + y))
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:28 • by Talks Funny (unregistered)
278333 in reply to 278283
newlisp.org:
improvement for some problems starting with even number:


(define (rmul x y , (s 0))
(until (= x 1)
(unless (zero? (% x 2))
(inc s y))
(setq x (>> x) y (<< y)))
(+ y s)
)


If you're gonna do it in good LISP, don't use setq so much.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:30 • by Anti-Ruski (unregistered)
Hell with them, just do:

Function mult (a,b)
mult = a*b
end


Screw the Russians

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:38 • by Roger (unregistered)
Free format RPGLE

SOURCE FILE . . . . . . . QRPGLESRC
MEMBER . . . . . . . . . RUSPEASANT
SEQNBR*...+... 1 ...+... 2 ...+... 3 ...+... 4 ...+... 5 ...+... 6 ...+... 7 ...+... 8
100 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
200 H DEBUG OPTION(*SRCSTMT:*NODEBUGIO) DFTACTGRP(*NO)
300 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
400 Fqsysprt O F 85 printer OFLIND(*INOF)
500 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
600 D A S 10I 0
700 D B S 10I 0
800 D DIV S 10I 0
900 D REM S 10I 0
1000 D RESULT S 10I 0
1100 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1200 D RUSPEASANT PR
1300 D IN_A 15P 5
1400 D IN_B 15P 5
1500 D RUSPEASANT PI
1600 D IN_A 15P 5
1700 D IN_B 15P 5
1800 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1900 /FREE
2000 A = IN_A ;
2100 B = IN_B ;
2200 RESULT = A * B ;
2300 except head ;
2400 except detail1 ;
2500 dow A > 1 ;
2600 A = %div(A:2) ;
2700 REM = %REM(A:2) ;
2800 B = B * 2 ;
2900 if rem > 0 ;
3000 RESULT += B ;
3100 endif ;
3200 except detail2 ;
3300 if *INOF ;
3400 except head ;
3500 endif ;
3600 enddo ;
3700 except total ;
3800 *INLR = *on ;
3900 return ;
4000 /END-FREE
4100 Oqsysprt E head 1 1
4200 O 20 'Russian Peasant '
4300 O 34 'Multiplication'
4400 O E detail1 1
4500 O A Z 15
4600 O 20 '*'
4700 O B Z 35
4800 O 40 '='
4900 O RESULT ZB 55
5000 O E detail2 1
5100 O A Z 15
5200 O B Z 35
5300 O E total 1
5400 O RESULT Z 55
* * * * E N D O F S O U R C E * * * *

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:41 • by bluebearr (unregistered)
278338 in reply to 278305
SoaperGEM:
I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad.

Alex Papadimoulis:
Your challenge: write a function that multiplies two numbers using the Russian peasant algorithm.


I didn't see anything in the original article about the peasants using bit shifting. I did see information about the peasants multiplying by two, and dividing by two and dropping the remainder.

But hey, maybe I missed something.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:44 • by hornet (unregistered)
Threaded solution for maximum performance on a multicore system - not yet capable of negative or zero first multiplicand:


using System;
using System.Collections.Generic;
using System.Text;
using System.ComponentModel;
using System.Threading;

namespace RussianMultiply
{
struct Multiplicands
{
public ManualResetEvent waitHandle;
public int a;
public int b;
}

class RussianMultiplyData
{
public volatile int result;
public RussianMultiplyData()
{
result = 0;
}
public void PartialCalculateMultiplication(object o, DoWorkEventArgs dwea)
{
Multiplicands mp = (Multiplicands)dwea.Argument;
if ((mp.a % 2) == 1) result += mp.b;
mp.waitHandle.Set();
}
};

class Program
{
static int MultiplyMultiCore(int a, int b)
{
List<BackgroundWorker> multiplicationWorkers = new List<BackgroundWorker>();
List<ManualResetEvent> threadCompletedEvents = new List<ManualResetEvent>();
RussianMultiplyData rmd = new RussianMultiplyData();
while (a > 0)
{
BackgroundWorker bw = new BackgroundWorker();
Multiplicands mps;
mps.waitHandle = new ManualResetEvent(false);
mps.a = a;
mps.b = b;
threadCompletedEvents.Add(mps.waitHandle);
bw.DoWork += rmd.PartialCalculateMultiplication;
bw.RunWorkerAsync(mps);
multiplicationWorkers.Add(bw);

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

WaitHandle.WaitAll(threadCompletedEvents.ToArray());
return rmd.result;
}

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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:44 • by Bodestone
I happened to be in SQL server at the the time so...


DECLARE @factor1 INT, @factor2 INT SET @factor1 =18 SET @factor2 = 23

SELECT SUM(rightCol)
FROM (SELECT @factor1/POWER(2,N) AS leftCol, @factor2*POWER(2,N) AS rightCol
FROM Tally
WHERE N < cast(log10(@factor1)/log10(2) as int) +1) таблица
WHERE leftCol%2=1


This does require that you have a Tally table with the integers 0 to x where x is big enough to do any calculation that won't overflow.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:45 • by mxsscott
A solution in C that must be given the input as English transliterations of Russian numbers, in case voice input is used [a must for all future programs]. e.g. 18x23 is
./russianmultiply AdeenDva TriVosyem

It outputs in a similar form, as well as digits.


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Must be 1+7 (not 8 or 7+1) */
#define MAGIC_LEN 1+7
const char* numerals[] =
{
"Nol","Adeen","Dva","Tri","Chetyre","Pyat’","Shest","Syem","Vosyem","Dyeviat"
};

char* intToRussian(unsigned int num)
{
char b[11];
sprintf(b,"%lu",num);
/* Allocate enough for longest string int and one terminating character */
char* russian = calloc(MAGIC_LEN * 10, sizeof(char));
for (int i = 0; i < 10 && b[i]; ++i)
{
strcat(russian, numerals[b[i] - '0']);
}
return russian;
}

unsigned int russianToInt(const char *russian)
{
int i,j,num;
num = j - j;
for (i = num ; i < strlen(russian); ++i)
{
for (j = i - i; j < 0x0A; ++j)
{
if ((j - j) == strncmp(russian + i, numerals[j], strlen(numerals[j])))
{
num *= 10;
num += j;
}
}
}
return num;
}

char *multiply(const char* a, const char* b)
{
unsigned int a1 = russianToInt(a);
unsigned int b1 = russianToInt(b);

unsigned int answer = 0;
while (a1 > 0)
{
a1 = a1 >> 1;
b1 = b1 << 1;
if (a1 & 0x01)
answer += b1;
}
return intToRussian(answer);
}

int main (int argc, const char * argv[]) {
char *answer = multiply(argv[1], argv[2]);
printf("%s\n", answer);
printf("%lu\n", russianToInt(answer));
return 0;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:45 • by astonerbum
278343 in reply to 278319
Beat by the system:
anyone done this in javascript?
function multiply (x, y, total)
{
(x == 0) ? alert(total) : multiply (Math.floor(x/2),Math.floor(y*2),(x % 2 == 0) ? total : total+y);
}


http://thedailywtf.com/Comments/Programming-Praxis-Russian-Peasant-Multiplication.aspx?pg=8#278264

Also an inefficiency I had was not using shift for multiply by two. I added the y to itself. Also I coulda removed one comparison. Hey we want ultimate efficiency.

I still wonder if this algorithm is what is used for doing multiplication internally in the processor. Seems a WHOLE lot more efficient than doing addition a whole lota times, or even doing times tables or whatever... Those brilliant russian peasents :)


function rpmult(x, y){
if (x === 0) {
return 0;
}
if (x === 1) {
return y;
}

var flip = false;
if (x < 0) {
x = -x;
flip = true;
}
var added = (((0x1 & num) === 0x1) ? 0 : y);
var recurse = rpmult(x >> 1, y << 1);
return flip ? - (added + recurse) : added + recurse;
}

a simple newLISP one-liner

2009-07-22 16:46 • by Ted Walther, newLISP fan (unregistered)
Unlike the perl one-liner, this newlisp one-liner is actually readable!

(define (rmul x y) (if (= x 1) y (+ (if (zero? (% x 2)) 0 y) (rmul (>> x) (<< y)))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:46 • by Jeb Walter Strate (unregistered)
My javascript version uses no multiplication, division, nor bit-shifting. Handles decimals, but negatives are left as an exercise for the reader.
<html><head><title>Multiply WFT</title><script>

double={0:0,1:2,2:4,3:6,4:8,'.':'.'};
doubleNeedsCarry={5:0,6:2,7:4,8:6,9:8};
carriedDouble={0:1,1:3,2:5,3:7,4:9};
carriedDoubleNeedsCarry={5:1,6:3,7:5,8:7,9:9,'.':'.'};
halve={0:0,2:1,4:2,6:3,8:4,'.':'.'}
halveHasRemainder={1:0,3:1,5:2,7:3,9:4};
RemainderedHalve={0:5,2:6,4:7,6:8,8:9};
RemainderedHalveHasRemainder={1:5,3:6,5:7,7:8,9:9,'.':'.'};
function halveRow(row){
var cells=row.cells;
var out=document.createElement('tr');
var remaindered=false;
var leading=true;
var visible='hidden';
for(var cellIndex=0;cellIndex<cells.length;cellIndex++){
var cell=cells[cellIndex];
var cellValue=cell.innerHTML;
var newCell=document.createElement('td');
if(remaindered==false){
if(cellValue in halve){
newCell.innerHTML=halve[cellValue];}
if(cellValue in halveHasRemainder){
newCell.innerHTML=halveHasRemainder[cellValue];}}
else if(remaindered=true){
if(cellValue in RemainderedHalve){
newCell.innerHTML=RemainderedHalve[cellValue];}
if(cellValue in RemainderedHalveHasRemainder){
newCell.innerHTML=RemainderedHalveHasRemainder[cellValue];}}
if(!remaindered && cellValue in halve || remaindered && !(cellValue in RemainderedHalveHasRemainder)){
remaindered=false;}
else{
remaindered=true;}
if(leading==true){
if(newCell.innerHTML=='0'){
newCell.style.visibility=visible;}
else if(newCell.innerHTML=='.'){
visible='';}
else
leading=false;}
out.appendChild(newCell);}
if(newCell.innerHTML in halve){
out.style.textDecoration='line-through';}
row.parentNode.appendChild(out);
if(leading==true){
out.style.visibility='hidden';
return false;}
else{
return !leading;}}
function doubleRow(row){
var cells=row.cells;
var cellIndex=cells.length;
var out=document.createElement('tr');
var carried=false;
while(cellIndex--){
var cell=cells[cellIndex];
var cellValue=cell.innerHTML;
var newCell=document.createElement('td');
if(carried==false){
if(cellValue in double){
newCell.innerHTML=double[cellValue];}
if(cellValue in doubleNeedsCarry){
newCell.innerHTML=doubleNeedsCarry[cellValue];}}
else if(carried=true){
if(cellValue in carriedDouble){
newCell.innerHTML=carriedDouble[cellValue];}
if(cellValue in carriedDoubleNeedsCarry){
newCell.innerHTML=carriedDoubleNeedsCarry[cellValue];}}
if(!carried && cellValue in double || carried && !(cellValue in carriedDoubleNeedsCarry)){
carried=false;}
else{
carried=true;}
out.insertBefore(newCell,out.firstChild);}
if(carried!=false){
var newCell=document.createElement('td');
newCell.innerHTML=carriedDouble['0'];
out.insertBefore(newCell,out.firstChild);}
var tb=row.parentNode;
tb.appendChild(out);
if(row.cells.length==out.cells.length){}
else{
for(var i=0;i<tb.rows.length;i++){
while(tb.rows[i].cells.length<out.cells.length){
var blank=document.createElement('td');
blank.innerHTML='0';
blank.style.visibility='hidden';
tb.rows[i].insertBefore(blank,tb.rows[i].firstChild);}}}}
function multiply(form){
var a=form.inta.value;
var b=form.intb.value;
if(a.charAt(a.length-1)=='.'){a+='0'}
if(b.charAt(b.length-1)=='.'){b+='0'}
var row=document.getElementsByTagName('tr')[0];
var t=document.createElement('table');
t.cellSpacing=0;
var tb=document.createElement('tbody');
var tr=document.createElement('tr');
t.appendChild(tb).appendChild(tr);
var digits=a.split('');
for(var i=0;i<digits.length;i++){
var td=document.createElement('td');
td.innerHTML=digits[i];
tr.appendChild(td);}
if(digits[digits.length-1] in halve){
tr.style.textDecoration='line-through';}
row.cells[0].innerHTML='';
row.cells[0].appendChild(t);
row.cells[1].innerHTML='<table cellSpacing=0><tbody><tr><td>&nbsp;X</td></tr></tbody></table>';
t=document.createElement('table');
t.cellSpacing=0;
tb=document.createElement('tbody');
tr=document.createElement('tr');
t.appendChild(tb).appendChild(tr);
if(digits.pop() in halve){
tr.style.textDecoration='line-through';}
digits=b.split('');
for(var i=0;i<digits.length;i++){
var td=document.createElement('td');
td.innerHTML=digits[i];
tr.appendChild(td);}
row.cells[2].innerHTML='';
row.cells[2].appendChild(t);
while(halveRow(row.cells[0].firstChild.firstChild.lastChild) ){
doubleRow(row.cells[2].firstChild.firstChild.lastChild);
row.cells[2].firstChild.firstChild.lastChild.style.textDecoration=row.cells[0].firstChild.firstChild.lastChild.style.textDecoration
row.cells[1].firstChild.firstChild.insertRow(-1).insertCell(0).innerHTML='&nbsp;';}
row.cells[1].firstChild.firstChild.insertRow(-1).insertCell(0).innerHTML='&nbsp;';
row.cells[2].firstChild.firstChild.insertRow(-1).insertCell(0).innerHTML='&nbsp;';
row.cells[1].firstChild.cellSpacing=0;
t=document.createElement('table');
t.cellSpacing=0;
tb=document.createElement('tbody');
tr=document.createElement('tr');
t.appendChild(tb).appendChild(tr);
row.cells[3].innerHTML='';
row.cells[3].appendChild(t);
var decimala=0;
for(var i=0;i<row.cells[0].firstChild.firstChild.firstChild.cells.length;i++){
if(row.cells[0].firstChild.firstChild.firstChild.cells[i].innerHTML=='.'){
decimala=row.cells[0].firstChild.firstChild.firstChild.cells.length-i;
break}}
var decimalb=0;
for(var i=0;i<row.cells[2].firstChild.firstChild.firstChild.cells.length;i++){
if(row.cells[2].firstChild.firstChild.firstChild.cells[i].innerHTML=='.'){
decimalb=row.cells[2].firstChild.firstChild.firstChild.cells.length-i;
break}}
var r=row.cells[2].firstChild.firstChild.lastChild;
while(r=r.previousSibling){
var newRow=tb.insertBefore(r.cloneNode(true),tb.firstChild);
if(tb.firstChild.style.textDecoration){
tb.firstChild.style.visibility='hidden';}
if(decimala && decimalb){
var dec=newRow.removeChild(newRow.cells[newRow.cells.length-decimalb]);
newRow.insertBefore(dec, newRow.cells[newRow.cells.length-decimalb-decimala+2]);}
if(decimala && !decimalb){
var dec=document.createElement('td');
dec.innerHTML='.';
newRow.insertBefore(dec, newRow.cells[newRow.cells.length-decimala+1]);}}
var carry=0;
for(var i=tb.rows[0].cells.length;i;){
--i;
var t=carry*1;
carry=0;
for(var j=0;j<tb.rows.length-1;j++){
if(tb.rows[j].style.visibility=='hidden') continue;
if(tb.rows[j].cells[i].innerHTML=='.'){
carry=t;
t='.';
break;}
t+=parseInt(tb.rows[j].cells[i].innerHTML);}
if(t>9){
var s=t.toString().split('');
t=s.pop();
carry=s.join('');}
tb.lastChild.insertCell(0).innerHTML=t;}
if(carry!='0'){
for(j=0;j<tb.rows.length;j++){
var blank=document.createElement('td');
blank.innerHTML='0';
blank.style.visibility='hidden';
tb.rows[j].insertBefore(blank,tb.rows[j].firstChild);}
blank.innerHTML=carry;
blank.style.visibility='visible';}
row.cells[3].getElementsByTagName('tr')[row.cells[3].getElementsByTagName('tr').length-1].style.textDecoration='overline';}
</script>
</head><body><form action="javascript:multiply(document.forms[0])"><br>
<input name=inta><br>
<input name=intb><br>
<input type=submit value=multiply><br>
<table cellspacing=5><tbody><tr><td></td><td></td><td></td><td></td></tr></tbody></table>
</body></html>

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:46 • by Roger (unregistered)
278346 in reply to 278337
The program listed above produces this output

Russian Peasant Multiplication
18 * 23 = 414
9 46
4 92
2 184
1 368
414

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:51 • by WTF! (unregistered)
My WTF is that I'd just create a huge times-table in MS Access and use DAO calls to read it back.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:54 • by Tom Medley - www.tommedley.com (unregistered)
This problem is trivial in ML (4 lines):

fun peasant (1,r,q) = sum(r::q)
| peasant (l,r,q) = if(l mod 2 = 1)
then peasant((l div 2),(r*2),(r::q))
else peasant((l div 2),(r*2),q);

...a wrapper function to make it nice:

fun russian(x,y) = peasant(x,y,[]);

...and in case you need a sum function (most ml versions come with standard functions such as sum):

fun sum [] = 0
| sum (x::xs) = x + sum(xs);

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:55 • by Rob H (unregistered)
In C, C++, C#, taking zeros and negative numbers into account:

Recursive (not tested):
INT Multiply(INT a, INT B)

{
INT c, PosNeg = 1;

// first, deal with zeros
if ((a == 0) || (b == 0))
return 0;

// now, deal with negative numbers
if (a < 0)
{
a = -a;
PosNeg = -PosNeg;
}
if (b < 0)
{
b = -b;
PosNeg = -PosNeg;
}

// now, the meat of the problem
if (a == 1)
return b;
else
return (b * (a & 1) + Multiply(a / 2, b * 2)) * PosNeg;
}
Alternatively, if you use the following as the last line, you accomplish this using only one multiplication (the one dealing with +/-) and one division per step:
    return ((a & 1) ? b : 0) + Multiply(a / 2, b + b)) *

PosNeg;

Non-recursive (also not tested):
INT Multiply(INT a, INT B)

{
INT c = 0, PosNeg = 1;

// first, deal with zeros
if ((a == 0) || (b == 0))
return 0;

// now, deal with negative numbers
if (a < 0)
{
a = -a;
PosNeg = -PosNeg;
}
if (b < 0)
{
b = -b;
PosNeg = -PosNeg;
}

// now, the meat of the problem
while (a > 0)
{
if (a & 1)
c += b;
a /= 2;
b *= 2; // or b += b; if you want to get rid of a multiplication
}
return c * PosNeg;
}

(Of course, in C++ and C#, you would probably move the declarations for c and PosNeg down closer to where they're actually used.)
« 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